Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

Code in JAVA:

public static ArrayList<Integer> spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
   return new ArrayList<Integer>();
  }
  return spiralOrder(matrix, 0, 0, matrix.length, matrix[0].length);
    }
 public static ArrayList<Integer> spiralOrder(int [][] matrix, int x, int y, int m, int n){
  ArrayList<Integer> result = new ArrayList<Integer>();
  if (m <= 0 || n <= 0) {return result;}
  if (m == 1 && n == 1) {
   result.add(matrix[x][y]);
   return result;
  }
  for(int i = 0;i < n-1;i++){
            result.add(matrix[x][y++]);
        }
        for(int i = 0;i < m-1;i++){
            result.add(matrix[x++][y]);
        }
  if (m > 1) {
   for (int i = 0; i < n - 1; i++) {
    result.add(matrix[x][y--]);
   }
  }
  if (n > 1){  
   for (int i = 0; i < m - 1; i++) {
    result.add(matrix[x--][y]);
   }
  }
  if (m == 1 || n == 1) {
   result.addAll(spiralOrder(matrix, x, y, 1, 1));
  } else {
   result.addAll(spiralOrder(matrix, x + 1, y + 1, m - 2, n - 2));
  }
  return result;

 }

Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Code in JAVA:

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public static ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        ArrayList<Interval> result = new ArrayList<Interval>();
  for (Interval interval: intervals) {
   if (interval.end < newInterval.start) {
    result.add(interval);
   } else if (interval.start > newInterval.end) {
    result.add(newInterval);
    newInterval = interval;
   } else if (interval.end >= newInterval.start || interval.start <= newInterval.end) {
    newInterval = new Interval(Math.min(interval.start, newInterval.start), 
             Math.max(newInterval.end, interval.end));
   }
  }
  result.add(newInterval);
  return result;
    }
}

Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

Code in JAVA:

public static int[] plusOne(int[] digits) {
   int carry = 0; 
   int i = digits.length - 1;
   digits[i] += 1;
   while (digits[i] >= 10) {
     digits[i--] -= 10;
     if (i >= 0) {
      digits[i] += 1;
     } else {
       carry = 1;
       break;
     }
  }
  if (carry == 0) {return digits;}

  int[] result = new int[digits.length + 1];
  for (i = 0; i < digits.length; i++) {
     result[i + 1] = digits[i];
  }
  result[0] = 1;
  return result;
}

Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time


2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.


• All words have the same length.


• All words contain only lowercase alphabetic characters.

Code in JAVA:

public static int ladderLength(String start, String end, HashSet dict) {
    if (dict.size() == 0) {return 0;}
    LinkedList wordQueue = new LinkedList(); //store the words
    LinkedList distanceQueue = new LinkedList(); //store the change steps
    wordQueue.add(start);
    distanceQueue.add(1);

    while (!wordQueue.isEmpty()) {
      String currWord = wordQueue.pop();
      Integer currDistance = distanceQueue.pop();

      if (currWord.equals(end)) {
          return currDistance;
      }

      for (int i = 0; i < currWord.length(); i++) {
          char[] currChar = currWord.toCharArray();
          for (char c = 'a'; c <= 'z'; c++) {
              currChar[i] = c;
              String newWord = new String(currChar);
              if (dict.contains(newWord)) {

                  wordQueue.add(newWord);
                  distanceQueue.add(currDistance + 1);
                  dict.remove(newWord);
              }
          }
       }
    }
     return 0;
}

Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.
Code in Java:

public class Rmove_Nth_Node_From_End_of_List {
 //Definition for singly-linked list.
  public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
      val = x;
      next = null;
    }
  }
  public ListNode removeNthFromEnd(ListNode head, int n) {
    /*
     * 1. two start points: head and prev
     * 2. Node n2 move N steps first
     * 3. then n1, n2, head move (L-N) steps together
     * 4. return head.next
     */
    ListNode prev, n1, n2;
    prev = new ListNode(0);
    prev.next = head;
    head = prev;
    n1 = head.next;
    n2 = head.next;
    while (n2 != null && n > 0) {
      n2 = n2.next;
      n--;
    }
    /*
     * Runtime Error Message: Line 28: java.lang.NullPointerException
     * Last executed input: {1}, 1
     */
    if (n > 0) {return n1;}
    while (n2 != null) {
      n2 = n2.next;
      n1 = n1.next;
      prev = prev.next;
    }
    prev.next = n1.next;
    return head.next;
  }
}

The same thought can deal with the question "Rotated List".

Merge K Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Merge Tow Sorted Lists is quiet easy to implement, but how to merge k sorted list? I have searched several methods for this questions in Google, I think the best method to implement this question is to use the PriorityQueue, so now let's discuss it in detail:

Solution:
First, the steps of this method is:
1. Build up a min heap of the k head nodes of given lists.
2. Create a ListNodeComparator to make sure the smallest one(the head of the minHeap) and add its next to heap.
3. Repeat until all nodes in lists have been merged into one list.

And here are some details to notice:

1. Since ListNode doesn't have its compare method, we need to provide our own comparator and pass it in during construction time.(return -1 for less-than; return 1 for greater-than; return 0 for equal.)

2. PriorityQueue is an unbounded queue based on heap.

Bottom-Line: we should master how to use the minHeap and how to write a comaprator

Code in JAVA:

public class Merge_k_Sorted_Lists {
 public static class ListNode{
  public int val;
  ListNode next;
  ListNode(int x) {
   val = x;
   next = null;
  }
 }
 //Build a comparator
 private static Comparator listNodeComparator = 
   new Comparator(){

    @Override
    public int compare(ListNode o1, ListNode o2) {
     if (o1.val < o2.val) {
      return -1;
     } else if (o1.val > o2.val) {
      return 1;
     } else {
      return 0;
     }
     
    }
  
 };
 
 public static ListNode mergeKLists(ArrayList lists) {
  if (lists == null || lists.size() == 0) {
   return null;
  }
  Queue heap = new PriorityQueue(lists.size(), listNodeComparator);
  // add element to heap
  for (int i = 0; i < lists.size(); i++) {
   if (lists.get(i) != null) {
    // put the head of each list into heap
    heap.add(lists.get(i));
   }
  }
  
  ListNode dummy = new ListNode(0);
  ListNode tail = dummy;
  while (!heap.isEmpty()) {
   ListNode head = heap.poll();
   tail.next = head;
   tail = head;
   if (head.next != null) {
    heap.add(head.next);
   }
  }
  return dummy.next;
 }
 
}

Analysis and Comparison:

In mergeSort solution, each original list has been touched O(logk) times, where k is the number of lists. That said, each node has been touched O(logk) times. So the total running time is O(Nklogk), where N is the number of each lists.
Note that, for odd cases, as shown above, some list(s) may be touched more than logktimes, but still O(logk) times.

In heapSort solution, only head nodes of lists are kept in the min-heap.
Building up such a heap takes time O(klogk), each following insertion requires O(logk) time and there are at most Nk insertions in total. So the total running time is also O(Nklogk). And space compexity using minHeap reduce from O(n) to O(1).