Leetcode: Next Permutation

implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Understand the problem:
The problem is a little a bit harder to understand. So you must first understand what is the lexicographical order. Basically, the lexicographic or lexicographical order (also known as lexical order, dictionary order, alphabetical order or lexicographic(al) product) is a generalization of the way the alphabetical order of words is based on the alphabetical order of their component letters.

The next permutation means the next greater permutation of numbers according to the lexicographical order. For example, for the input 1 2 3, its permutations according to the lexicographical order is
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
So its next permutation is 1 3 2. Since list in decreasing order is already the greatest, its next available permutation will be wrapped around to 1 2 3.

Solution:
Since we know at for a words in ascending order must be the smallest lexicographical order, while in descending order is the greatest lexicographical order. 

So we can iterate through the input string from end in reverse order, and find the first descending number. Mark that index. Then scan through the numbers after the number we found, until we find the smallest number which is still greater than the number we found. Since the string after the number is in descending order, it is pretty easy to find this number. We then swap this numbers. At least, we make all numbers behind the first number we found as in ascending order. 

Code (Java):

public class Solution {
    public void nextPermutation(int[] num) {
        if (num == null || num.length == 0) {
            return;
        }
        
        int i, j;
        for (i = num.length - 2; i >= 0; i--) {
            if (num[i] < num[i + 1]) {
                break;
            }
        }
        
        // for the case where the num[] is in descending order
        if (i >= 0) {
            for (j = i + 1; j < num.length; j++) {
                if (num[j] <= num[i]) {
                    break;
                }
            }
            j = j - 1;
            swap(num, i, j);
        }
        reverse(num, i + 1);
    }
    
    private void swap(int[] num, int i, int j) {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
    
    private void reverse(int[] num, int start) {
        int end = num.length - 1;
        while (start < end) {
            int temp = num[start];
            num[start] = num[end];
            num[end] = temp;
            
            start++;
            end--;
        }
    }
}

Discussion:
We scan the array three times, so the time complexity is still O(n). Space complexity is O(1) since we don't use additional space. 

Summary:
The crux of the problem is to figure out what is the lexicographical order. After we know this, we scan from the end in reverse order. We scan from end because we wanna get the next greater permutation. We wanna find the ascending order numbers because if we get that, we know that the next permutation will be after that number.  We also need to figure out the smallest number which is greater than the number we found, and swap them. At least, we shall sort the numbers after i in ascending order. 

Leetcode: Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

Understand the problem:
The problem gives a string S and a list of words L, find all string indices of substrings in S such that the substring is a concatenation of each word in L exactly once without any intervening characters. 

Native Solution:
A very straight-forward solution is check each substring with the length of the word in L existed in the dictionary. If yes, we continue to search next until find all words in the dictionary. But how to guarantee that each word appears only once at the concatenation. We can use a hash set to add all visited words into the set. Then the next question is how could we know that we visited all words in the dictionary. We can use a counter, each time wee see a substring in the dictionary, we increase the counter. If the counter equals to the number of elements of the dictionary, we know that we visited all words. 


Wrong Answer:

public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (S == null || S.length() == 0 || L == null || L.length == 0)
            return result;
        
        HashSet<String> hashSet = new HashSet<String>();
        
        int num = L.length;
        int len = L[0].length();
        
        int start = 0;
        int count = 0;
        for (int i = 0; i < S.length(); i += len) {
            if (i + len > S.length()) break;
            if (!hashSet.contains(S.substring(i, i + len)) && isDictWords(S.substring(i, i + len), L)) {
                hashSet.add(S.substring(i, i + len));
                count++;
                if (count == num) {
                    result.add(start);
                    hashSet.clear();
                    count = 0;
                    start = i;
                }
            } else if (hashSet.contains(S.substring(i, i + len)) && isDictWords(S.substring(i, i + len), L)) {
                start = i;
            } else {
                start = i + len;
                count = 0;
                hashSet.clear();
            }
        }
        return result;
    }
    
    private boolean isDictWords(String str, String[] dict) {
        for (int i = 0; i < dict.length; i++) {
            for (int j = 0; j < str.length(); j++) {
                if (str.charAt(j) != dict[i].charAt(j)) {
                    break;
                } else if (str.charAt(j) == dict[i].charAt(j) && j == str.length() - 1) {
                    return true;
                }
            }
        }
        return false;
    }
}

So why the solution above is wrong? That is because we iterate through the input string with stride equals to the length of the word in the dictionary. However, the matched substring may not start from that strided point, e.g. 

Input:	"lingmindraboofooowingdingbarrwingmonkeypoundcake", ["fooo","barr","wing","ding","wing"]
Output:	[]
Expected:	[13]

So after fixing that bug, the code becomes below:

public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (S == null || S.length() == 0 || L == null || L.length == 0)
            return result;
        
        HashSet<String> hashSet = new HashSet<String>();
        
        int num = L.length;
        int len = L[0].length();
        
        int start = 0;
        int count = 0;
        int i = 0;
        while (i < S.length() - len + 1) {
            if (!hashSet.contains(S.substring(i, i + len)) && isDictWords(S.substring(i, i + len), L)) {
                hashSet.add(S.substring(i, i + len));
                count++;
                if (count == num) {
                    result.add(start);
                    hashSet.clear();
                    count = 0;
                    start = i + len;
                }
                i += len;
            } else if (hashSet.contains(S.substring(i, i + len)) && isDictWords(S.substring(i, i + len), L)) {
                start = i;
                i += len;
            } else if (!isDictWords(S.substring(i, i + len), L)) {
                start = i + 1;
                count = 0;
                hashSet.clear();
                i++;
            }
        }
        return result;
    }
    
    private boolean isDictWords(String str, String[] dict) {
        for (int i = 0; i < dict.length; i++) {
            for (int j = 0; j < str.length(); j++) {
                if (str.charAt(j) != dict[i].charAt(j)) {
                    break;
                } else if (str.charAt(j) == dict[i].charAt(j) && j == str.length() - 1) {
                    return true;
                }
            }
        }
        return false;
    }
}

But the code above still failed the test case above. Why? Look carefully of the dictionary in the test case above, it contains duplicated word "wing", although I don't think a dictionary should contain duplicated words. So we must modify the code to reflect this property. 

Correct Code:

public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        
        if (S == null || S.length() == 0 || L == null || L.length == 0) {
            return result;
        }
        
        HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
        
        for (int i = 0; i < L.length; i++) {
            if (hashMap.containsKey(L[i])) {
                hashMap.put(L[i], hashMap.get(L[i]) + 1);
            } else {
                hashMap.put(L[i], 1);
            }
        }
        
        int i = 0;
        int size = L[0].length();
        while (S.length() - i >= L.length * size) {
            HashMap<String, Integer> dict = new HashMap<String, Integer>(hashMap);
            
            for (int j = 0; j < L.length * size; j += size) {
                if (j + size > L.length * size) break;
                String sub = S.substring(i + j, i + j + size);
                if (dict.containsKey(sub)) {
                    if (dict.get(sub) == 1) {
                        dict.remove(sub);
                    } else {
                        dict.put(sub, dict.get(sub) - 1);
                    }
                } else {
                    break;
                }
            }
            if (dict.isEmpty()) {
                result.add(i);
            }
            i++;
        }
        return result;
    }
}

Discussion:
The pitfall of this problem is dictionary may contain duplicated keys. To avoid this, we used a hash map to note the number of times each dictionary word occurs. If we found one word, we decrease the counter for the word in dictionary. If the counter is 1, we delete the word. So the time complexity is O(n * m * l), where n is the length of the string, m is the number of elements in the dictionary, and l is the length of the dictionary word. The space complexity is O(m * l). 

Summary:
This problem can be categorized as the same group of substring problem, where the basic idea is to maintain two pointers, one points to the string, another one points to the dictionary. The mainly thing to note is the pointers points to the string can move only one step at a time. 

Update on 11/19/2014:

public class Solution {
 public List<Integer> findSubstring(String S, String[] L) {
  List<Integer> result = new ArrayList<Integer>();
  if (S == null || S.length() == 0 || L == null || L.length == 0) {
   return result;
        }

        int m = L[0].length();
        Map<String, Integer> map = new HashMap<String, Integer>();
        for (String str : L) {
         if (map.containsKey(str)) {
             int count = map.get(str) + 1;
             map.put(str, count);
            } else {
             map.put(str, 1);
            }
        }

        for (int start = 0; start < S.length(); start++) {
         if (S.length() - start < (L.length * m)) {
             break;
            }
            
            Map<String, Integer> curMap = new HashMap<String, Integer>(map);
            for (int end = start; end < S.length(); end += m) {
                if (S.length() - end < (curMap.size() * m)) {
                    break;
                }
                String token = S.substring(end, end + m);
                if (curMap.containsKey(token)) {
              int count = curMap.get(token);
              if (count == 1) {
                     curMap.remove(token);
                    } else {
                     count--;
                     curMap.put(token, count);
                    }
                } else {
                 break;
                }
                if (curMap.isEmpty()) {
                 result.add(start);
                 break;
                }
            } 
        }
        return result;
    }
}

Leetcode: Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

Understand the problem:
The problem gives a dividend and divisor, of which are integer types. Return the division result with int type as well. Note that the problem does not allow to use multiplication, division and mod operator. 

Several special cases need to think about:
For dividend is 0, return 0.
For divisor equals to 0, we check if the dividend is positive or negative, and return the Integer.MAX_VALUE, and Integer.MIN_VALUE, respectively. 
For negative numbers. If either is negative, the result is negative. If both are negative, result is positive. 

Solution:

public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == 0) return 0;
        if (divisor == 0 && dividend > 0) return Integer.MAX_VALUE;
        if (divisor == 0 && dividend < 0) return Integer.MIN_VALUE;
        if (divisor == 1) return dividend;
        if (divisor == -1) return -dividend;
        
        boolean isDividendNeg = false;
        boolean isDivisorNeg = false;
        if (dividend < 0) {
            isDividendNeg = true;
            dividend = -dividend;
        }
        if (divisor < 0) {
            isDivisorNeg = true;
            divisor = -divisor;
        }
        
        int result = 0;
        while (dividend > divisor) {
            dividend = dividend - divisor;
            result++;
        }
        
        if ((isDividendNeg == true && isDivisorNeg == false) || 
            (isDividendNeg == false && isDivisorNeg == true))
            result = -result;
            
        return result;
    }
}

The code above has one bug: It does not handle negative number overflow problem. Consider the input -1010369383, -2147483648. The divisor is Integer.MIN_VALUE. When we flip it, it is overflowed. Consider the integer number ranges from -2^31 to 2^31 - 1. 

It is a very common bug in doing integer math arithmetic. The common approach to handle this is to convert the integer to long first. We actually have seen this situation many times before. So the correct code is:

Code (Java):

public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == 0) return 0;
        if (divisor == 0 && dividend > 0) return Integer.MAX_VALUE;
        if (divisor == 0 && dividend < 0) return Integer.MIN_VALUE;
        if (divisor == 1) return dividend;
        if (divisor == -1) return -dividend;
        
        long dividendL = (long) dividend;
        long divisorL = (long) divisor;
        
        boolean isDividendNeg = false;
        boolean isDivisorNeg = false;
        if (dividendL < 0) {
            isDividendNeg = true;
            
            dividendL = -dividendL;
        }
        if (divisor < 0) {
            isDivisorNeg = true;
            divisorL = -divisorL;
        }
        
        int result = 0;
        while (dividendL > divisorL) {
            dividendL = dividendL - divisorL;
            result++;
        }
        
        if ((isDividendNeg == true && isDivisorNeg == false) || 
            (isDividendNeg == false && isDivisorNeg == true))
            result = -result;
            
        return result;
    }
}

Discussion:
The implementation above is very inefficient especially when divisor is relative small compared to the dividend. Note that the solution above we deduct the divisor once a time. If we can deduct the divisor in exponential rate, the algorithm could be much faster.  For example, 16 / 3 = 5. In the naive solution, 
16 - 3 = 13
13 - 3 = 11
11 - 3 = 8
8 - 3 = 5
5 - 3 = 2 

We can increase the rate of divisor in exponential rate. 
16 - 3 * 2^1 = 7
16 - 3 * 2^2 = 4
16 - 3 * 2^3 < 0 
So in this case, we can see that the total number of times to shift is 3. We stop at when b is just greater than a, then go back one step where b is just less than a. Then we can calculate the partial result, in this case is 2^2 = 4. We deduct a from b,  and update a. Then we repeat the process again until a is less than b. 

Code (Java):

public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == 0) return 0;
        
        boolean isNeg = false;
        if ((dividend > 0 && divisor < 0) || 
            (dividend < 0 && divisor > 0))
            isNeg = true;
        
        long a = Math.abs((long)dividend);
        long b = Math.abs((long)divisor);
        
        int ans = 0;
        
        while (a >= b) {
            int shift = 0;
            while (a >= (b << shift)) {
                shift++;
            }
            
            ans += (1 << (shift - 1));
            a -= b << (shift - 1);
        }
        
        if (isNeg) ans = -ans;
        return ans;
    }
}

Summary:
This is a very interesting problem, but tricky. Two things you must be careful: Integer overflow, and we usually use a longer data type to avoid that. Secondly, the O(logn) solution is very tricky. Do understand the details.

Leetcode: Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Understand the problem:
The problem gives an array and a value, remove all instances of that value in-place and return the new length. 

Several special requirements for this question: The order of elements can be changed. It doesn't matter what you leave beyond the new length. 

Naive Solution:
Since the problem only asks about the new length of the array. The most straight-forward solution is to traverse the array. For the element equals to the input value, we deduct the length. In this way, we actually did not remove the desired elements in the array.

Code (Java):

public class Solution {
    public int removeElement(int[] A, int elem) {
        if (A == null || A.length == 0) return 0;
        
        int len = A.length;
        
        for (int i = 0; i < A.length; i++) {
            if (A[i] == elem) len--;
        }
        return len;
    }
}

However, it failed on the OJ test. 
Input:[4,5], 4
Output:[4]
Expected:[5]

So it looks like that OJ does check the final array. We must come out a new solution with changing to the output array.

Wrong Solution:
Iterate through the array from left, if found a target value, move all the elements behind one step left. The code is as below:

Code (Java):

public class Solution {
    public int removeElement(int[] A, int elem) {
        if (A == null || A.length == 0) return 0;
        
        int len = A.length;
        
        for (int i = 0; i < A.length; i++) {
            if (A[i] == elem) {
                for (int j = i + 1; j < A.length; j++) {
                    A[j - 1] = A[j];
                }
                len--;
            }
        }
        return len;
    }
}

Why it is wrong. If the target elements are at head of tail of the array, it will get the wrong result. 

Input:	[2,2,3], 2
Output:	[2,3]
Expected:	[3]

Correct Solution:
The correct solution is traverse the array backward. 

public class Solution {
    public int removeElement(int[] A, int elem) {
        if (A == null || A.length == 0) return 0;
        
        int len = A.length;
        
        for (int i = A.length - 1; i >= 0; i--) {
            if (A[i] == elem) {
                for (int j = i + 1; j < A.length; j++) {
                    A[j - 1] = A[j];
                }
                len--;
            }
        }
        return len;
    }
}

Discussion:
The time complexity of the solution is O(n^2), since we need to move the elements. The space complexity is O(1). 
A Better Solution:
Does there exist an O(n) time solution? The answer is yes. We can iterate the array, for the element not equal to the target value, we increase a counter and overwrite the element of i to counter. For the equal element, we don't increase the counter. As a result, the removed elements will be overwritten by its following elements. 

Code (Java):

public class Solution {
    public int removeElement(int[] A, int elem) {
        if (A == null || A.length == 0) return 0;
        
        int counter = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] != elem) {
                A[counter++] = A[i];
            }
        }
        return counter;
    }
}

Summary:
Take away message from this problem: This is a classical removing elements in an array problem. Using two pointers is a common idea where one points to the overwritten element, one points to the reading element. 

Leetcode: Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Understand the problem:
The problem is an extension of last problem, where now k is an input along with the linked list. Again, the solution needs to be in-place and only nodes itself may be changed.

Solution:
The basic idea is to iterate the linked list and increase a counter. If the counter equals to the times of k, we reverse the range of linked list. 

Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k == 1)
            return head;
        
        ListNode helper = new ListNode(0);
        helper.next = head;
        
        ListNode pre = helper;
        ListNode cur = head;
        
        int counter = 0;
        
        while (cur != null) {
            counter++;
            
            if (counter % k == 0) {
                pre = reverseRange(pre, cur.next);
                cur = pre.next;
            } else {
                cur = cur.next;
            }
        }
        
        return helper.next;
    }
    
    // Reverse the linked list from pre to end, exclusively
    private ListNode reverseRange(ListNode prev, ListNode end) {
        ListNode head = prev.next;
        ListNode curr = head.next;
        
        while (curr != end) {
            ListNode temp = curr.next;
            curr.next = prev.next;
            prev.next = curr;
            
            curr = temp;
        }
        
        head.next = end;
        return head;
    }
}

Summary:
Take away message from this problem. Reversing the linked list in-place is very basic and important. Make sure you can do it with and without using a dummy head node. 

Update on 9/21/15:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k <= 1) {
            return head;
        }
        
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        
        ListNode prev = dummyNode;
        ListNode curr = head;
        
        int count = 0;
        while (curr != null) {
            count++;
            if (count % k != 0) {
                curr = curr.next;
            } else {
                ListNode next = curr.next;
                
                // Reverse the list
                curr.next = null;
                List<ListNode> result = reverseList(prev.next);
                
                prev.next = result.get(0);
                ListNode tail = result.get(1);
                tail.next = next;
                prev = tail;
                curr = next;
            }
        }
        
        return dummyNode.next;
    }
    
    private List<ListNode> reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        ListNode tail = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        List<ListNode> result = new ArrayList<>();
        result.add(prev);
        result.add(tail);
        
        return result;
        
    }
}

Leetcode: Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Understand the problem:
The problem gives a linked list, swap every two adjacent nodes and return its head. For e.g. For 1->2->3->4, swap 1 and 2, 3 and 4, return 2->1->4->3. There are two requirements in the problem: you could only use constant space. You cannot modify the value in the list, just change the nodes. 

Let's take several examples to show the problem.
For a single node list, 1, return 1
For 1->2, return 2->1
For 1->2->3, return 2->1->3.
For 1->2->3->4->5, return 2->1->4->3->5

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode helper = new ListNode(0);
        helper.next = head;
        
        ListNode pre = helper;
        ListNode p = null;
        ListNode q = null;
        ListNode post = head;
        
        while (post != null) {
            p = post;
            q = post.next;
            if (q == null) break;
            
            post = post.next.next;
            pre.next = q;
            q.next = p;
            p.next = post;
            
            pre = p;
        }
        
        return helper.next;
    }
}

A Neat Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode helper = new ListNode(0);
        helper.next = head;
        
        ListNode pre = helper;
        ListNode cur = pre.next;
        
        while (cur != null && cur.next != null) {
            pre.next = cur.next;
            cur.next = cur.next.next;
            pre.next.next = cur;
            
            pre = cur;
            cur = pre.next;
        }
        
        return helper.next;
    }
}

Update on 9/21/15:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        
        ListNode prev = dummyNode;
        ListNode curr = head;
        
        int count = 0;
        
        while (curr != null) {
            count++;
            if (count % 2 == 1) {
                curr = curr.next;
            } else {
                ListNode next = curr.next;
                curr.next = prev.next;
                prev.next.next = next;
                prev.next = curr;
                
                prev = curr.next;
                curr = next;
            }
        }
        
        return dummyNode.next;
    }
}

Leetcode: 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.

Understand the problem:
This is a classical two-pointer problem of linked list. One thing needs to handle is deleting the head node. 

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || head.next == null) return null;
        
        ListNode slow = head;
        ListNode fast = head;
        
        // move fast pointer n steps ahead of slow
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        
        // move slow and fast pointer one step a time
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        
        // delete the node
        if (fast == null) {
            head = head.next;
        } else {
            slow.next = slow.next.next;
        }
        return head;
    }
}

Summary:
This is an easy question. However, when deal with linked list problem, make sure you cover all the corner cases. 

Leetcode: Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Understand the problem:
The problem gives a digit string, return all possible letter combination that the number could represent. Note the the relative order of the number should be reflated in the corresponding strings. For instance, "23", 2 is ahead of 3, so abc should be in front of def as well. For a brute force solution, we can iterate all possible combinations, with the time complexity of O(n^m), where n is the number of characters for each digit, m is the length of the digit string. 

Recursive Solution:
It is a typical recursive problem, you can mimic the solution of Subset. 

Code (Java):

public class Solution {
    public ArrayList<String> letterCombinations(String digits) {
        ArrayList<String> result = new ArrayList<String>();
        
        if (digits == null) return result;
        
        String[] dict = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        
        StringBuilder sb = new StringBuilder();
        letterCombinationsHelper(digits, 0, sb, dict, result);
        
        return result;
    }
    
    private void letterCombinationsHelper(String digits, int start, StringBuilder temp, String[] dict, ArrayList<String> result) {
        if (start >= digits.length()) {
            result.add(temp.toString());
            return;
        }
        
        // char to int
        int num = digits.charAt(start) - '0';
        for (int i = 0; i < dict[num].length(); i++) {
            temp.append(dict[num].charAt(i));
            letterCombinationsHelper(digits, start + 1, temp, dict, result);
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}

Summary:
This is a very classical permutation and combination problem. All P&C problems share the similar idea of using DFS. Be cautious about that. 

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

Understand the problem:
The question asks for finding the longest common prefix (LCP) string among an array of strings. We can take an example to illustrate this problem. For the array of strings
a
bc
cd
The LCP string is empty as there is no common prefix at all.

For the array of strings
a
ab
abc
The LCP string is "a" since a is the longest common prefix string

For an array of strings
abc
abd
abfghi
The LCP string is "ab" since it is the longest common prefix string.

Solution:
Based on the analysis above, we can come up a solution. We compare the character with the same index for each of the string. If the same, we go to the next. There are two termination conditions:
a. the LCP is the shortest string, as in the example 2. 
b. the LCP is the substring of a string, we continue until we found the character is different. 

Code (Java):

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        
        for (int i = 0; i < strs[0].length(); i++) {
            for (int j = 0; j < strs.length - 1; j++) {
                if (i >= strs[j].length() || i >= strs[j + 1].length() || strs[j].charAt(i) != strs[j + 1].charAt(i)) {
                    return strs[j].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}

Discussion:
The time complexity of this solution is O(m * n), where m is the length of the LCP string, n is the number of strings in the array.

Summary:
It is not a very difficult question, but requires careful implementation. Note the outer loop, where i < strs[0].length(). Think about why we choose to use strs[0].length() ? Actually what we wanna find is the LCP string. So if strs[0] itself is the LCP string, it is fine. If strs[0] is not, we have other conditions inside of the loop to terminate the loop. How about we choose strs[1]? It is basically correct, however be careful about the size of the array, which has only one element. So we must change the code slightly like this:

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        if (strs.length == 1) return strs[0];
        
        for (int i = 0; i < strs[1].length(); i++) {
            for (int j = 0; j < strs.length - 1; j++) {
                if (i >= strs[j].length() || i >= strs[j + 1].length() || strs[j].charAt(i) != strs[j + 1].charAt(i)) {
                    return strs[j].substring(0, i);
                }
            }
        }
        return strs[1];
    }
}

Update on 9/28/15:

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        StringBuffer sb = new StringBuffer();
        
        for (int i = 0; i < strs[0].length(); i++) {
            char curr = strs[0].charAt(i);
            int j = 1;
            for (j = 1; j < strs.length; j++) {
                String str = strs[j];
                if (str == null || str.length() == 0 || i >= str.length() || str.charAt(i) != curr) {
                    break;
                }
            }
            if (j == strs.length) {
                sb.append(curr);
            } else {
                break;
            }
        }
        
        return sb.toString();
    }
}

Leetcode: Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Understand the problem:
The problem is just as opposite to the last problem. The crux is to get each string and convert it to digits, then it is straight-forward to convert digits into integer.

Solution:
The most challenge part of this problem is to split the string into valid roman numerals. The special case is for 4, 40, 400, and 9, 90, 900. Consider the following string:
MXXIV. which is 1024. However, it could be wrongly calculated as 1000 + 10 + 10 + 1 + 5 = 1006. To handle this situation, we could scan two characters at a time and check the special case.

Code (Java):

public class Solution {
    public int romanToInt(String s) {
        if (s == null || s.isEmpty()) return 0;
        
        int i = 0;
        int num = 0;
        while (i < s.length()) {
            if (i <= s.length() - 2 && s.charAt(i) == 'I' && s.charAt(i + 1) == 'V') {
                num += 4;
                i += 2;
            } else if (i <= s.length() - 2 && s.charAt(i) == 'X' && s.charAt(i + 1) == 'L') {
                num += 40;
                i += 2;
            } else if (i <= s.length() - 2 && s.charAt(i) == 'C' && s.charAt(i + 1) == 'D') {
                num += 400;
                i += 2;
            } else if (i <= s.length() - 2 && s.charAt(i) == 'I' && s.charAt(i + 1) == 'X') {
                num += 9;
                i += 2;
            } else if (i <= s.length() - 2 && s.charAt(i) == 'X' && s.charAt(i + 1) == 'C') {
                num += 90;
                i += 2;
            } else if (i <= s.length() - 2 && s.charAt(i) == 'C' && s.charAt(i + 1) == 'M') {
                num += 900;
                i += 2;
            } else {
                num += toInteger(s.charAt(i));
                i++;
            }
        }
        return num;
    }
    
    private int toInteger(char roman) {
        int num = 0;
        switch(roman) {
            case 'I': num = 1;
                      break;
            case 'V': num = 5;
                      break;
            case 'X': num = 10;
                      break;
            case 'L': num = 50;
                      break;
            case 'C': num = 100;
                      break;
            case 'D': num = 500;
                      break;
            case 'M': num = 1000;
                      break;
        }
        return num;
    }
}

A better Solution:
Again, the solution above is self-explained, but look redundant. For the case where 4, 40, 400, 9, 90, 900, we can see that if the first character is less than second, e.g. 4 is IV, we know that it must be in either the case above. Else, VI, we know that it is 5 + 1 = 6. 
Consequently, we can use this property to shorten the code above.

Code (Java):

public class Solution {
    public int romanToInt(String s) {
        if (s == null || s.length() == 0) return 0;
        
        // create a hash table to store the dictorary
        HashMap<Character, Integer> hashMap = new HashMap<Character, Integer>();
        hashMap.put('I', 1);
        hashMap.put('V', 5);
        hashMap.put('X', 10);
        hashMap.put('L', 50);
        hashMap.put('C', 100);
        hashMap.put('D', 500);
        hashMap.put('M', 1000);
        
        int num = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (i <= s.length() - 2 && 
                hashMap.get(s.charAt(i)) < hashMap.get(s.charAt(i + 1))) {
                num -= hashMap.get(s.charAt(i));
            } else {
                num += hashMap.get(s.charAt(i));
            }
        }
        return num;
    }
}

Summary:
The problem is not hard. However, note that how 4, 40, 400, 9, 90, 900 are represented in the Roman numerals. 

Leetcode: Integer to Roman

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Understand the problem:
The crux of the problem is obviously to understand the roman numeral.
According to wiki, The numbers 1 to 10 can be expressed in Roman numerals as follows:

I, II, III, IV, V, VI, VII, VIII, IX, X.

Reading Roman numerals[edit]

MMXIV

"2014" as a Roman numeral

Roman Numerals, as used today, are based on seven symbols:^[1]

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1,000

Numbers are formed by combining symbols and adding the values. So II is two ones, i.e. 2, and XIII is a ten and three ones, i.e. 13. There is no zero in this system, so 207, for example, is CCVII, using the symbols for two hundreds, a five and two ones. 1066 is MLXVI, one thousand, fifty and ten, a five and a one.

Symbols are placed from left to right in order of value, starting with the largest. However, in a few specific cases,^[2] to avoid four characters being repeated in succession (such as IIII or XXXX) these can be reduced using subtractive notation as follows:^[3][4]

• the numeral I can be placed before V and X to make 4 units (IV) and 9 units (IX) respectively
• X can be placed before L and C to make 40 (XL) and 90 (XC) respectively
• C can be placed before D and M to make 400 (CD) and 900 (CM) according to the same pattern^[5]

An example using the above rules would be 1904: this is composed of 1 (one thousand), 9 (nine hundreds), 0 (zero tens), and 4 (four units). To write the Roman numeral, each of the non-zero digits should be treated separately. Thus 1,000 = M, 900 = CM, and 4 = IV. Therefore, 1904 is MCMIV.

Below are some examples of the modern use of Roman Numerals.

• 1954 as MCMLIV (Trailer for the movie The Last Time I Saw Paris)^[6]
• 1990 as MCMXC (The title of musical project Enigma's debut album MCMXC a.D., named after the year of its release.)
• 2014 as MMXIV - the year of the games of the XXII (22nd) Olympic Winter Games (in Sochi)

So the first problem to address is convert from digits from 1 - 10 to roman numerals. Since the ASCII coding table does not code for roman numerals, i.e, there is no direct mapping from digits to roman numerals, we must convert the manually. 

The second issue is to handle when the digit equals to 4 or 9, we must process it separately. 

Solution:
Based on the analysis above, the straight-forward solution is to parse the integer and get the digit and place value one-by-one. There are two ways to parse the integer, one is from right to left while the other is from left to right. In this problem, I choose left to right since append the string as tail is much efficient than append at head. Then we convert the digit into roman numeral and append it to the string. 

Code (Java):

public class Solution {
    public String intToRoman(int num) {
        if (num <= 10) return toString(num);
        
        // we first get the num of digits of the integer
        int temp = num;
        int nDigits = -1; // 1 less than actual number
        while (temp > 0) {
            nDigits++;
            temp /= 10;
        }
        
        // create an empty string
        StringBuilder sb = new StringBuilder();
        
        // parse the integer from left to right
        while (num > 0) {
            int place = (int) Math.pow(10, nDigits--);
            int digit = num / place;
            num -= digit * place;
            
            if (digit == 4 || digit == 9) {
                sb.append(toString(place));
                sb.append(toString((digit + 1) * place));
            } else if (digit == 5) {
                sb.append(toString(place * digit));
            } else if (digit < 4){
                for (int i = 0; i < digit; i++) {
                    sb.append(toString(place));
                }
            } else if (digit > 5) {
                sb.append(toString(5 * place));
                for (int i = 0; i < digit - 5; i++) {
                    sb.append(toString(place));
                }
            }
        }
        
        return sb.toString();
    }
    
    private String toString(int num) {
        String roman = "";
        switch(num) {
            case 1: roman = "I";
                    break;
            case 2: roman = "II";
                    break;
            case 3: roman = "III";
                    break;
            case 4: roman = "IV";
                    break;
            case 5: roman = "V";
                    break;
            case 6: roman = "VI";
                    break;
            case 7: roman = "VII";
                    break;
            case 8: roman = "VIII";
                    break;
            case 9: roman = "IX";
                    break;
            case 10: roman = "X";
                     break;
            case 50: roman = "L";
                     break;
            case 100: roman = "C";
                      break;
            case 500: roman = "D";
                      break;
            case 1000: roman = "M";
                       break;
            default: roman = "Invalid";
                     break;
        }
        return roman;
    }
}

A Neat Solution:
We can see that the crux of the solution above is to handle while digit < 4, digit = 4, digit = 5, digit > 5, digit = 9. There is a very neat solution below that does not need to handle those cases:

public class Solution {
    public String intToRoman(int num) {
        String[] str = new String[] {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int[] val = new int[] {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < val.length; i++) {
            while (num >= val[i]) {
                num -= val[i];
                sb.append(str[i]);
            }
        }
        return sb.toString();
    }
}

Summary:

The problem itself is not hard at all, but requires carefully handling all the corner cases. The second solution is very tricky but the code is neat. Make sure you understand it.

Leetcode: Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

Understand the problem:
The problem actually asks you to find out the maximum (j - i) * min(ai, aj). Therefore, the most straight-forward way is an O(n^2) solution which you iterate every possible pair of i and j, and calculate the (j - i) * min(ai, aj).

Solution:
Since the area is calculated as (j - i) * min(ai, aj), we can start with the maximum width. In other words, we use two pointers, low points to 0, and high points to length - 1. We calculate the area. If height of lo is smaller than the height of hi, move lo one right step. Else, move hi one step left. 

The algorithm works simply because we decrease the width, we must increase the height. Since the height is bounded by the minimum number of ai and aj, we must move the minimum height; otherwise, we can never ever get the maximum area. Moving the pointer with smaller height can make it possible to get the maximum area.

Code (Java):

public class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length <= 1) 
            return 0;
            
        int lo = 0;
        int hi = height.length - 1;
        int max = 0; 
        
        while (lo < hi) {
            max = Math.max(max, (hi - lo) * Math.min(height[lo], height[hi]));
            if (height[lo] < height[hi]) lo++;
            else hi--;
        }
        return max;
    }
}

Discussion:
Since we only iterate the array once, the time complexity is O(n). The space complexity is O(1).

Summary:
Take-away message of the problem is: first, understand the problem thoroughly. For such kind of application problems, it is key to generalize the problem in a programmer's perspective. For e.g. this problem actually asks you calculate the maximum area. 

Secondly, the two pointers solution can be commonly used in many other questions, such as 2 sum. Be familiar with this idea.

Leetcode: ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Understand the problem:
The crux of the problem is to understand what is the "zigzag" format. We can use examples to illustrate this. For number of rows is 2, 

0    A    C 
1    B    D

For nRows = 3,
0  A       E
1  B  D  F
2  C      G

For nRows = 4
0  A          G
1  B      F  H
2  C  E      I
3  D          M

It is actually easier to understand the problem putting the characters into a mesh grid.

Solution:
We can divide the zigzag format into several zigzags. For nRows = 4, 
1         | 7              |
2      6 | 8         12 |
3  5     | 9    11      |
4         | 10            |

So each zigzag has number of nRows * 2 - 2 elements. 

For each zigzag, the first row and last row, the distance between two indices is nRow * 2 - 2. For example, distance between 1 and 7 is 6, distance between 4 and 10 is 6, which  can be calculated as 4 * 2 - 2 = 6. 

For each other rows from 1 to nRows - 2, the distance between two indices is (nRows - i - 1 ) * 2 = nRows * 2 - 2 - 2 * i. Note that the distance between A to B is defined as [A, B). Also note that for each zigzag, there are at most two elements in a row. 

Based on the analysis above, we can come up the solution below:

Code (Java):

public class Solution {
    public String convert(String s, int nRows) {
        if (s == null || s.length() == 0 || nRows <= 0)
            return "";
        if (nRows == 1) return s;
        
        StringBuilder sb = new StringBuilder(); //non-thread safe
        int size = 2 * nRows - 2; // number of elements for each zigzag
        
        for (int i = 0; i < nRows; i++) {
            for (int j = i; j < s.length(); j += size) {
                sb.append(s.charAt(j));
                
                if (i != 0 && i != nRows - 1 && (j + size - 2 * i) < s.length()) {
                    sb.append(s.charAt(j + size - 2 * i));
                }
            }
        }
        return sb.toString();
    }
}

Discussion:
The time complexity is O(n) since we only traverse the string once. The space complexity is O(n) as well since we performed out-of-place transform.

Summary:
The crux of this problem is to convert the indices from zigzag-major to row-major. Be familiar with the zigzag-major format.