Leetcode: Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = "Hello World",
return 5.

Understand the problem:
The problem gives a string s consists of upper/lower-case alphabets and empty space characters, return the length of the last word in the string. If the last word does not exist, return 0. Note that a word is defined as a character sequence consist of non-space characters only.  Several cases need to think about.

• For empty string "", return 0;
• For string with one word, return the length of the word
• For string with trailing empty spaces, e.g. "Hello World     ", return the length of the last word, ie. World, which is 5.
• For string with leading empty spaces, e.g. "    Hello World", it does not matter since we only wanna the length of the last word.

Solution:
The easiest way we can use is to apply the Java regular expression, where we use the split method. 

Code (Java):

public class Solution {
    public int lengthOfLastWord(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        String delim = "[ ]+";
        String[] strs = s.split(delim);
        int length = 0;
        
        if (strs.length == 0) {
            return 0;
        } else {
            length = strs[strs.length - 1].length();
        }
        
        return length;
    }
}

A naive solution:
What if we are not allowed to use the Java split() method, can we manually solve this question without using any advanced language features? The answer is yes. We use two pointers, i, and j, starting from the end of the string. j points to the end of the word, while traverse the string in reverse order until reach to an empty space. Then the length of the last word is j - i. Be careful about the trailing spaces in the string.

Code (Java):

public class Solution {
    public int lengthOfLastWord(String s) {
        if (s == null || s.length() ==0) {
            return 0;
        }
        
        int end = s.length() - 1;
        // jump trailing empty spaces
        while (end >= 0 && s.charAt(end) == ' ') {
            end--;
        }
        
        int start = end;
        
        while (start >= 0 && s.charAt(start) != ' ') {
            start--;
        }
        
        return end - start;
    }
}

Leetcode: Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Understand the problem:
This question is similar to the last post, but requires minimum number of jumps. 

Solution:
The problem can be solved using recursion as well. It can be categorized the minimal depth of a tree, when we go from root to leaves, we find the minimum depth of the tree. This problem is similar, when we jump from first element to the last, we go through all probabilities and find the minimum number of jumps. 

Code (Java):

public class Solution {
    private int min = Integer.MAX_VALUE;
    public int jump(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        jumpHelper(A, 0, 0);
        
        return min;
    }
    
    private void jumpHelper(int[] A, int start, int depth) {
        if (start >= A.length - 1) {
            if (depth < min) {
                min = depth;
            }
            return;
        }
        int maxJump = A[start] + start;
        for (int i = start + 1; i <= maxJump; i++) {
            jumpHelper(A, i, depth + 1);
        }
    }
}

Discussion:
The time complexity for this solution is exponential. It got the TLE error at OJ. So we must find out another way.

A better solution:
It is natural to think about a DP solution. We can use an array dp[A.length], where dp[i] means the minimum steps from the first element to i. So we only need to check the dp[n - 1]. 

Code (Java):

public class Solution {
    public int jump(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int min = Integer.MAX_VALUE;
        int[] dp = new int[A.length];
        for (int i = 1; i < A.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;
        
        for (int i = 0; i < A.length; i++) {
            int maxReach = Math.min(A[i] + i, A.length - 1);
            for (int j = i + 1; j <= maxReach; j++) {
                if (dp[j] > dp[i] + 1) {
                    dp[j] = dp[i] + 1;
                }
            }
        }
        
        return dp[A.length - 1];
    }
}

Discussion:
The solution of DP has time complexity of O(n^2).
Summary:
There is another solution using greedy algorithms. We don't discuss it here. 


Update on 10/11/14:

public class Solution {
    public int jump(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        if (A[0] == 0 && A.length > 1) {
            return Integer.MAX_VALUE;
        }
        
        int[] dp = new int[A.length];
        
        // Initialization
        for (int i = 1; i < A.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        
        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] != Integer.MAX_VALUE && A[j] + j >= i) {
                    dp[i] = dp[j] + 1;
                    break;
                }
            }
        }
        
        return dp[A.length - 1];
    }
}

Leetcode: Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Understand the problem:
The problem gives an array of non-negative integers. Each element represents the maximum jump length you can reach. Determine if you can reach the last index. Besides the two normal examples shown above, we can take another several ones to illustrate the problem. 

For A= [0,1,1], return false, since the first element is false, you can never jump to the following elements. 

For A= [1, 1, 0, 2, 3], return false, because we stop at the 0. 

Solution:
Based on the analysis above, we can see that the basic idea is to iterate the array elements, note down the maximum steps we can reach for each index. Then determine if the maximum length is greater or equals to  the index of last element. 

Code (Java):

public class Solution {
    public boolean canJump(int[] A) {
        if (A == null || A.length == 0) {
            return false;
        }
        
        if (A[0] == 0 && A.length > 1) {
            return false;
        }
        
        int max = 0;
        for (int i = 0; i < A.length; i++) {
            if (i <= max && i + A[i] > max) {
                max = i + A[i];
            } else if (i > max) {
                return false;
            }
        }
        
        return max >= A.length - 1;
    }
}

Discussion:
The key of the problem is the if condition in the for loop. Make sure the current element is within the maximum length you can reach; else we can never ever reach that point. 

Summary:
Understand the problem correctly is the key to this problem. In such kind of abstracted question, make sure you can think of every corner cases. A rule of thrumb is to take examples, in normal, negative, and extreme cases. 

Update on 10/11/14:

public class Solution {
    public boolean canJump(int[] A) {
        if (A == null || A.length == 0) {
            return true;
        }
        
        return canJumpHelper(0, A);
    }
    
    private boolean canJumpHelper(int index, int[] A) {
        if (index >= A.length) {
            return true;
        }
        
        for (int i = 1; i <= A[index]; i++) {
            if (canJumpHelper(index + i, A) == true) {
                return true;
            }
        }
        
        return false;
    }
}

A DP Solution:

public class Solution {
    public boolean canJump(int[] A) {
        if (A == null || A.length == 0) {
            return true;
        }
        
        if (A[0] == 0 && A.length > 1) {
            return false;
        }
        
        boolean[] dp = new boolean[A.length];
        dp[0] = true;
        
        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] == true && j + A[j] >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[A.length - 1];
        
    }
}

Update on 9/22/15:
A Greedy algorithm with O(n) time complexity:

public class Solution {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return true;
        }
        
        int maxReach = 0;
        for (int i = 0; i <= maxReach && i < nums.length - 1; i++) {
            if (i + nums[i] > maxReach) {
                maxReach = i + nums[i];
            }
        }
        
        return maxReach >= nums.length - 1;
    }
}

Update on 2/12/16:

public class Solution {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return true;
        }
        
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) {
                return false;
            }
            
            if (i + nums[i] > maxReach) {
                maxReach = i + nums[i];
            }
        }
        
        return maxReach >= nums.length - 1;
    }
}

Leetcode: N-Queens

he n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Understand the problem:
It is a classic N-queue problem. The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n-queens problem of placing n queens on an n×n chessboard, where solutions exist for all natural numbers n with the exception of n=2 or n=3. 

Solution:
This is again a classic permutation and combination problem. So we can still apply the same recursive approach. 

Code (Java):

public class Solution {
    public List<String[]> solveNQueens(int n) {
        List<String[]> result = new ArrayList<String[]>();
        
        if (n == 0 || n == 2 || n == 3) {
            return result;
        }
        
        solveNqueensHelper(n, 0, new int[n], result);
        
        return result;
    }
    
    private void solveNqueensHelper(int n, int row, int[] cols, List<String[]> result) {
        if (row == n) {
            String[] solution = new String[n];
            for (int i = 0; i < n; i++) {
                StringBuilder temp = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    if (cols[i] == j) {
                        temp.append('Q');
                    } else {
                        temp.append('.');
                    }
                }
                solution[i] = temp.toString();
            }
            result.add(solution);
            return;
        }
        
        for (int j = 0; j < n; j++) {
            if (isValid(j, row, cols) == true) {
                cols[row] = j;
                solveNqueensHelper(n, row + 1, cols, result);
            }
        }
    }
    
    private boolean isValid(int col, int row, int[] cols) {
        for (int i = 0; i < row; i++) {
            if (col == cols[i] || row - i == Math.abs(col - cols[i])) {
                return false;
            }
        }
        return true;
    }
}

Leetcode: Anagrams

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Understand the problem:
As described in the problem, given an array of strings, return all groups of strings that are anagrams. Note that all inputs will be lower-case. 

First of all, we must understand what is anagrams? Any word or phrase that exactly reproduces the letters in another order is an anagram. For example, 
abcd, acbd, dcba are anagrams. 

We can take an example to illustrate this question. For the array S = {"abc", "bca", "ab", "acd", "ba"}, the result is ["abc", "bca", "ab", "ba"].

Solution:
To check if two words are anagram, there are usually two methods. The first method is to use a hash map. The first word is added into the map, and delete each character for the second word, if then the hash map becomes zero, the two words are anagrams. In the second method, we sort the two words and compare. If they are the same, they are anagrams. 

Back to this problem where we has a list of words with possible different length. The idea is to use a hash table, where the key store the sorted string, and the value stores the list of anagrams. At last, we copy all the anagrams into the list. 

Code (Java):

public class Solution {
    public List<String> anagrams(String[] strs) {
        List<String> result = new ArrayList<String>();
        if (strs == null || strs.length == 0) {
            return result;
        }
        
        Map<String, ArrayList<String>> hashMap = new HashMap<String, ArrayList<String>>();
        
        for (int i = 0; i < strs.length; i++) {
            char[] word = strs[i].toCharArray();
            
            Arrays.sort(word);
            String key = new String(word);
            
            if (hashMap.containsKey(key)) {
                hashMap.get(key).add(strs[i]);
            } else {
                ArrayList<String> value = new ArrayList<String>();
                value.add(strs[i]);
                hashMap.put(key, value);
            }
        }
        
        // dump the anagrams to the result list
        Set<String> keySet = hashMap.keySet();
        
        for (String key : keySet) {
            List<String> temp = hashMap.get(key);
            if (temp.size() > 1) {
                result.addAll(temp);
            }
        }
        
        return result;
    }
}

Discussion:
Now let's analyze the time complexity. For the string array with length n, each string has the complexity of O(mlogm), where m is the length of each word. So the total time complexity is O(nm logm). The space complexity is O(n).

Summary:
Take away message for this question:
1. Learn the two methods to check two words are anagrams. 
2. Learn how to iterate the hash map and dump the values out. 

Update on 9/29/15:

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<List<String>>();
        if (strs == null || strs.length == 0) {
            return result;
        }
        
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            String sorted = new String(arr);
            if (map.containsKey(sorted)) {
                List<String> anas = map.get(sorted);
                anas.add(str);
            } else {
                List<String> anas = new ArrayList<>();
                anas.add(str);
                map.put(sorted, anas);
            }
        }
        
        // Iterate the hashmap and output the results
        Iterator it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry pair = (Map.Entry) it.next();
            List<String> anas = (List<String>) pair.getValue();
            Collections.sort(anas, new LexComparator());
            result.add(anas);
        }
        
        return result;
        
    }
    
    class LexComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            for (int i = 0; i < a.length(); i++) {
                if (a.charAt(i) < b.charAt(i)) {
                    return -1;
                } else if (a.charAt(i) > b.charAt(i)) {
                    return 1;
                }
            }
            
            return 0;
        }
    }
}

Leetcode: Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

Understand the problem:
The problem gives two strings with numbers only, return the multiplication of the numbers as a string as well. Note that the two numbers are positive. Also note that the numbers can be arbitrarily large, so if you convert to a number then calculate, you must handle the overflow problem. In this question, it is even harder, since the two numbers could be arbitrarily large. So we must think of another way. 

Solution:
The basic idea is to mimic how we multiply two integers. 

Code (Java):

public class Solution {
    public String multiply(String num1, String num2) {
        if (num1 == null || num1.length() == 0 || num2 == null || num2.length() == 0) {
            return "";
        }
        
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        
        StringBuilder sb = new StringBuilder();
        int paddle = 0;
        
        for (int i = num1.length() - 1; i >= 0; i--) {
            StringBuilder temp = new StringBuilder();
            int carry = 0;
            for (int j = num2.length() - 1; j >= 0; j--) {
                carry += toNum(num1.charAt(i)) * toNum(num2.charAt(j));
                temp.insert(0, toChar(carry % 10));
                carry /= 10;
            }
            
            if (carry != 0) {
                temp.insert(0, toChar(carry));
            }
            
            if (sb.length() == 0) {
                sb.append(temp);
            } else {
                sb = new StringBuilder(addTwoStrings(sb, temp, ++paddle));
            }
        }
        
        return sb.toString();
    }
    
    private int toNum(char a) {
        return Character.getNumericValue(a);
    }
    
    private char toChar(int a) {
        return (char) (a + '0');
    }
    
    private StringBuilder addTwoStrings(StringBuilder str1, StringBuilder str2, int paddle) {
        for (int i = 0; i < paddle; i++) {
            str2.append("0");
        }
        
        // add integers of two strings 
        int i = str1.length() - 1;
        int j = str2.length() - 1;
        
        int carry = 0;
        StringBuilder result = new StringBuilder();
        while (i >=0 || j >= 0) {
            if (i >= 0) {
                carry += toNum(str1.charAt(i));
                i--;
            }
            
            if (j >= 0) {
                carry += toNum(str2.charAt(j));
                j--;
            }
            
            result.insert(0, toChar(carry % 10));
            carry /= 10;
        }
        
        if (carry != 0) {
            result.insert(0, toChar(carry));
        }
        
        return result;
    }
}

Leetcode: Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Understand the problem:
The problem asks for how much water can be trapped after raining. If you remember, there is another similar problem about container: Container with Most Water. 

Solution:
The trapped water for slot i is determined by min(leftMostHeight[i], rgithMostHeight[i]) - A[i], which means the most water trapped for slot i is determined by the highest block left to i (exclusive), and the highest block right to i, whichever is less, and subtract by the height of the block itself. So we can iterate through the array to get the left highest and right highest for i. Then the third loop is to calculate the trapped water. 

Code (Java):

public class Solution {
    public int trap(int[] A) {
        if (A == null || A.length <= 2) {
            return 0;
        }
        
        int[] maxLeft = new int[A.length];
        int[] maxRight = new int[A.length];
        int max = 0;
        int sum = 0;
        
        for (int i = 1; i < A.length; i++) {
            if (A[i - 1] > max) {
                max = A[i - 1];
            }
            maxLeft[i] = max;
        }
        
        max = 0;
        for (int i = A.length - 2; i >= 0; i--) {
            if (A[i + 1] > max) {
                max = A[i + 1];
            }
            maxRight[i] = max;
        }
        
        for (int i = 0; i < A.length; i++) {
            int water = Math.min(maxLeft[i], maxRight[i]) - A[i];
            if (water > 0) {
                sum += water;
            }
        }
        return sum;
    }
}

Discussion:
The time complexity is O(n). The space complexity is O(n) as well since we used two additional arrays.
Summary:
This problem is very similar to the most container water. But the container takes 1 unit. For these kind of application problems, it is very important to generalize it to a mathematical problem, especially a equation.  

Leetcode: First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

Understand the problem:
The problem gives an unsorted integer array, find the first missing positive integer. The problem requires that the runtime should be within O(n) and uses constant space. 

A naive approach:
A naive approach is first to sort the array. Then it is quite straightforward to solve the problem. Just compare each element with the result, if the difference is larger than 1, return the result + 1, else update the result as A[i]. If iterate the entire array and we did not find the result, return the last element of the array plus 1.

Code (Java):

public class Solution {
    public int firstMissingPositive(int[] A) {
        if (A == null || A.length == 0) {
            return 1;
        }
        
        Arrays.sort(A);
        int result = 0;
        
        for (int i = 0; i < A.length; i++) {
            if (A[i] <= 0) {
                continue;
            }
            
            if (A[i] - result > 1) {
                return result + 1;
            } else {
                result = A[i];
            }
        }
        return A[A.length - 1] + 1;
    }
}

A better Solution:
Since the problem requires for linear time complexity and constant space. We can think of using bucket sort idea. The idea is to check if the index i store the value i + 1, if not swap the the value A[i] to its desired index. After that, we iterate again the array and check the first position that i != A[i] + 1. 

Code (Java):

public class Solution {
    public int firstMissingPositive(int[] A) {
        if (A == null || A.length == 0) {
            return 1;
        }
        int n = A.length;
        int i = 0;
        while (i < n) {
            if (A[i] != i + 1 && A[i] >= 1 && A[i] <= n && A[i] != A[A[i] - 1]) {
                swap(A, i, A[i] - 1);
            } else {
                i++;
            }
        }
        
        for (i = 0; i < n; i++) {
            if (A[i] != i + 1) {
                return i + 1;
            }
        }
        
        return A[n - 1] + 1;
    }
    
    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

Summary:
The take-away message for this question is when the question asks for O(n) time solution, and you found that it must be beneficial to sort the input array, bucket sort is a way to think about. 

Leetcode: Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6] 

Understand the problem:
The problem is very similar to the last question, but each number in C can only be used once in the combination. So the solution is still DFS. 

Solution:

public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (num == null || num.length == 0) {
            return result;
        }
        
        Arrays.sort(num);
        
        combinationSumHelper(num, target, 0, 0, new ArrayList<Integer>(), result);
        
        return result;
    }
    
    private void combinationSumHelper(int[] num, int target, int start, int sum, 
　　　　　ArrayList<Integer> curr, ArrayList<ArrayList<Integer>> result) {
        if (sum == target) {
            result.add(new ArrayList<Integer>(curr));
            return;
        }
        
        if (sum > target) {
            return;
        }
        
        for (int i = start; i < num.length; i++) {
            if (i != start && num[i - 1] == num[i]) {
                continue;
            }
            if ((sum + num[i]) > target) {
                break;
            } 
            
            sum += num[i];
            curr.add(num[i]);
            
            combinationSumHelper(num, target, i + 1, sum, curr, result);
            
            sum -= num[i];
            curr.remove(curr.size() - 1);
        }
    }
}

Summary:
This question has a pitfall. For any permutation and combination problems in the code interview, you must first clarify with the interviewer that if the set contains duplicates. If yes, all duplicated numbers can be only traversed once. 

Leetcode: Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3] 

Understand the problem:
The problem asks for finding all unique combinations where the candidate numbers sums to the target. Note that same number can be used with unlimited number of times. There are also several special requirements in the problem. There are no negative numbers in the list, and the output should be in non-descending order. In addition, the solution set must not contain duplicate combinations. 

Solution:
This question could be categorized into permutation and combination problem, where DFS should be used to produce the solution. 

Code (Java):

public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (candidates == null || candidates.length == 0) {
            return result;
        }
        
        Arrays.sort(candidates);
        
        combinationSumHelper(candidates, target, 0, new ArrayList<Integer>(), 0, result);
        
        return result;
    }
    
    private void combinationSumHelper(int[] candidates, int target, int sum, 
　　　　　ArrayList<Integer> curr, int start, ArrayList<ArrayList<Integer>> result) {
        if (sum == target) {
            result.add(new ArrayList<Integer>(curr));
            return;
        }
        
        if (sum > target) {
            return;
        }
        
        for (int i = start; i < candidates.length; i++) {
            if (sum + candidates[i] > target) break;
            sum += candidates[i];
            curr.add(candidates[i]);
            
            combinationSumHelper(candidates, target, sum, curr, i, result);
            
            sum -= candidates[i];
            curr.remove(curr.size() - 1);
        }
    }
}

Discussion:
The time complexity for this question is exponential, since it is a NP problem. 

Summary:
This problem can be categorized into permutation and combination problems. Using the DFS is the key to solution. Draw a recursion tree will also help at understanding the idea as well.

Leetcode: Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

Understand the problem:
The problem is kind of tricky to understand. We can use some examples to illustrate it.
For input 1112, we "count-and-say", three 1s and one 2, so it is 3112
For input 112, two 1s and one 2, 2112
For input 1234, output is 11121314.

Actually this question is not very clear. The sequence starts from string "1", then the read of first string is the next string, which is 11, then 21, then 1211, ...., note that n start from 1, so i + 1 sequence is the read of sequence i, the nth sequence is the read of sequence n - 1. 

Code (Java):

public class Solution {
    public String countAndSay(int n) {
        if (n < 0) {
            return "";
        }
        
        String s = "1";
        
        for (int i = 0; i < n - 1; i++) {
            StringBuilder sb = new StringBuilder();
            int count = 1;
            
            int j = 0;
            while (j < s.length()) {
                while (j < s.length() - 1 && s.charAt(j) == s.charAt(j + 1)) {
                    count++;
                    j++;
                }
                sb.append(Integer.toString(count));
                sb.append(s.charAt(j));
                count = 1;
                j++;
            }
            
            s = sb.toString();
        }
        
        return s;
    }
}

Leetcode: Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

Understand the problem:
The problem asks for finding an unique solution for a sudoku solver. We assume that there is an unique solution existed in the sudoku solver. So the basic idea could be using DFS, very similar with permutation and combination problem. We search all valid numbers for a slot, apply DFS, and go to the next. 

Solution:

public class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length != 9 || board[0].length != 9) {
            return;
        }
        
        solveHelper(board);
    }
    
    private boolean solveHelper(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char k = '1'; k <= '9'; k++) {
                        if (isValid(i, j, k, board)) {
                            board[i][j] = k;
                            if (solveHelper(board) == true) {
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean isValid(int row, int col, char target, char[][] board) {
        // check the row and column
        for (int i = 0; i < 9; i++) {
            if ((board[row][i] == target) || (board[i][col] == target)) {
                return false;
            }
        }
        
        // check the block
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int x = row / 3 * 3 + i; // nth block * block_size  + offset
                int y = col / 3 * 3 + j;
                if (board[x][y] == target) {
                    return false;
                }
            }
        }
        return true;
    }
}

Discussion:
Now let's analyze the complexity. Suppose the sudoku size is n (although in reality it is 9). For each slot which could be filled, we could have at most O(n) different combinations. For each number, it takes O(n) time to determine if it is a valid number. So we have total number of n^2 numbers in the board, the overall time complexity is O(n^4). For the real case where n equals to 9, the complexity is acceptable. 


Summary:
The problem follows the same idea as permutation and combination problem, where DFS is widely used in searching problems. Draw a recursion tree will help you understand the problem.

Leetcode: Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

Understand the problem:
The problem asks for determining if a Sudoku is valid. Note that only the filled cells need to be validated. The rule of Sudoku is each row should only contains 1 - 9 of each number occurring only once, each column contains 1-9, and each 3 by 3 sub-matrix should contain 1 - 9.

Solution:
A straight-forward solution will be check each row, and then each column, and each block, respectively. Use hash set to store the visited numbers. In this method, we need to scan the matrix three times. Here we show a neat program which requires scanning the matrix only once. 

Code (Java):

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board == null || board.length != 9 || board[0].length != 9) {
            return false;
        }
        
        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][] blocks = new boolean[9][9];
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                
                int c = board[i][j] - '1';
                
                if (rows[i][c] == true || cols[j][c] == true || blocks[(i / 3) * 3 + j / 3][c] == true) {
                    return false;
                }
                
                rows[i][c] = true;
                cols[j][c] = true;
                blocks[(i / 3) * 3 + j / 3][c] = true;
            }
        }
        return true;
    }
}

Summary:
It is a relatively easy question, the solution above is very tricky. Try to fully understand what does the rows, cols, and blocks mean. 


Update on 9/29/15:

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][] grid = new boolean[9][9];
        
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                
                int num = board[i][j] - '1';
                int x = 3 * (i / 3) + num / 3;
                int y = 3 * (j / 3) + num % 3;
                if (rows[i][num] || cols[num][j] || grid[x][y]) {
                    return false;
                }
                
                rows[i][num] = true;
                cols[num][j] = true;
                grid[x][y] = true;
            }
        }
        
        return true;
    }
}

Leetcode: Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Understand the problem:
The problem gives a sorted array of integers, find the starting and ending position of a given target value. It requires the time complexity as O(logn), which indicates to use binary search. If not found, return [-1, -1]. 

Solution:
Since the problem asks for O(logn) solution, we can solve this problem by using the binary search for the first and last index of the target.

Code (Java):

public class Solution {
    public int[] searchRange(int[] A, int target) {
        if (A == null || A.length == 0) {
            int[] result = {-1, -1};
            return result;
        }
        int[] result = new int[2];
        // Find the first index of the target value
        result[0] = binarySearchFirstIndex(A, target);
        
        if (result[0] == -1) {
            result[1] = -1;
            return result;
        }
        
        // Find the last index of the target value
        result[1] = binarySearchLastIndex(A, target);
        
        return result;
    }
    
    private int binarySearchFirstIndex(int[] A, int target) {
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (A[mid] == target) {
                hi = mid;
            } else if (A[mid] > target) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        
        if (A[lo] == target) {
            return lo;
        }
        
        if (A[hi] == target) {
            return hi;
        }
        
        return -1;
    }
    
    private int binarySearchLastIndex(int[] A, int target) {
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (A[mid] == target) {
                lo = mid;
            } else if (A[mid] > target) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        
        if (A[hi] == target) {
            return hi;
        }
        
        if (A[lo] == target) {
            return lo;
        }
        
        return -1;
    }
}

Leetcode: Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Understand the problem:
The problem gives a sorted array which is rotated at some pivot, search for a target value. This problem clearly indicates that we do find the number in O(logn) time, just as binary search. 

One naive idea is to find the pivot and rotate the array back, then we can apply the binary search. But rotating the array would take on average O(n) time, which is not allowed in this problem. 

Solution:
The solution is very similar to binary search. Note that no matter how we rotated the array, there must be at least one part which is sorted. If the target is at the sorted part, we just search that part until we found; else we go the unsorted part. 

Code (Java):

public class Solution {
    public int search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return -1;
        }
        
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (A[mid] == target) {
                return mid;
            }
            
            if (A[lo] <= A[mid]) {
                if (target >= A[lo] && target < A[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (A[mid] < target && target <= A[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
}

Discussion:
Now let's analyze the complexity. If the target just falls into the sorted part, the complexity could be O(logn). How about the worst case, where target is always not in the sorted part, then we have to iterate all the data of the array, then the complexity becomes O(n). So on average, we can see that the complexity is O(logn).

Summary:
This is an extension of the binary search. So it is very important that you got familiar with the binary search. 

Update on 9/29/14:

public class Solution {
    public int search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return -1;
        }
        
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (A[mid] == target) {
                return mid;
            }
            
            if (A[lo] <= A[mid]) {
                if (A[lo] <= target && target < A[mid]) {
                    hi = mid;
                } else {
                    lo = mid;
                }
            } else {
                if (A[mid] < target && target <= A[hi] ) {
                    lo = mid;
                } else {
                    hi = mid;
                }
            }
        }
        
        if (target == A[lo]) {
            return lo;
        }
        
        if (target == A[hi]) {
            return hi;
        }
        
        return -1;
        
    }
}

Update on 7/13/18:

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int ans = -1;
        
        int lo = 0;
        int hi = nums.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return mid;
            } else {
                // case 1: left half is sorted
                //
                if (nums[lo] < nums[mid]) {
                    if (target >= nums[lo] && target < nums[mid]) {
                        hi = mid - 1;
                    } else {
                        lo = mid + 1;
                    }
                } else if (nums[mid] < nums[hi]) {
                    if (target > nums[mid] && target <= nums[hi]) {
                        lo = mid + 1;
                    } else {
                        hi = mid - 1;
                    }
                }
            }
        }
        
        if (nums[lo] == target) {
            return lo;
        }
        
        if (nums[hi] == target) {
            return hi;
        }
        
        return -1;
    }
}