Friday, August 29, 2014

Leetcode: Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
Understand the problem:
The problem asks to generate all combinations of well-formed parentheses. 
So the first question is what is a well formed parentheses? Basically, it must start from left parentheses and end with right parentheses. In addition, the number of left parentheses must be equal to right parentheses. Let's take several examples to illustrate this:
For n = 0, return empty
For n = 1, return ()
For n = 2, return ()(), (()).
For n = 3, return as above.

Solution:
The crux of the problem is for a valid parentheses, at any point the visited left parentheses should be greater or equal than the visited right parentheses. For example, ()()(),  at position 2, the number of left parentheses is 2 while the right one is 1. That helps to avoid the case such that () ), which could never be a valid parentheses. 
There is a good post illustrated the problem very well http://blog.csdn.net/fightforyourdream/article/details/14159435

For n = 3, we can draw a recursion tree to help understand the problem. Since the answer must start with left parentheses, the tree looks like:
  

So the solution could be recursive as well. We count the number of left and right parentheses visited. If both are equal to the n, we add the result into the result list. 

Code (Java):
public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> result = new ArrayList<String>();
        if (n <= 0) return result;
        
        StringBuilder sb = new StringBuilder();
        
        generateParenthesisHelper(n, 0, 0, sb, result);
        
        return result;
    }
    
    private void generateParenthesisHelper(int n, int left, int right, StringBuilder temp, ArrayList<String> result) {
        if (left < right) return;
        
        if (left == n && right == n) {
            result.add(temp.toString());
            return;
        }
        
        if (left < n) {
            temp.append('(');
            generateParenthesisHelper(n, left + 1, right, temp, result);
            temp.deleteCharAt(temp.length() - 1);
        }
        
        if (right < n) {
            temp.append(')');
            generateParenthesisHelper(n, left, right + 1, temp, result);
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}

Summary:
The take away message is for the recursion problem, drawing a recursion tree could be very helpful to understand the problem. 

Leetcode: Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.
For example,
If S = [1,2,2], a solution is:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]
Understand the problem:
This is an extension of the last problem. The major difference is the array contains duplicates. It asks for returning all distant subsets. 

For the input S = [1, 2, 2], if we use exactly the same approach as the last problem, what shall we get?

Solution:
Similar to the permutation II, we check the range from start to i contains duplicated numbers, if yes, simply jump to next iteration.

Code (Java):
public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (num == null || num.length == 0) return result;
        
        Arrays.sort(num);
        
        result.add(new ArrayList<Integer>());
        ArrayList<Integer> temp = new ArrayList<Integer>();
        
        subsetsHelper(num, 0, temp, result);
        
        return result;
    }
    
    private void subsetsHelper(int[] num, int start, ArrayList<Integer> temp, ArrayList<ArrayList<Integer>> result) {
        if (start >= num.length) return;
        
        for (int i = start; i < num.length; i++) {
            if (!isDup(num, start, i)) {
                temp.add(num[i]);
                result.add(new ArrayList<Integer>(temp));
                subsetsHelper(num, i + 1, temp, result);
                
                temp.remove(temp.size() - 1);
            }
        }
    }
    
    private boolean isDup(int[] num, int start, int end) {
        for (int i = start; i <= end - 1; i++) {
            if (num[i] == num[end]) return true;
        }
        return false;
    }
}

Discussion:
This problem has time complexity of O(2^n), since finding all subsets of a set is a NP problem.

Summary:
The take away message is all permutation and combination questions share very similar ways of solution. Make sure to understand the details.

Leetcode: Subsets

Given a set of distinct integers, S, return all possible subsets.
Note:
  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3], a solution is:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
Understand the problem:
As described in the problem, given a set of DISTINCT integers, S, return all possible subsets. Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. 


Recursive Solution:
public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (S == null || S.length == 0) return result;
        
        Arrays.sort(S);
        
        result.add(new ArrayList<Integer>());
        
        ArrayList<Integer> temp = new ArrayList<Integer>();
        subsetsHelper(S, 0, result, temp);
        
        return result;
    }
    
    private void subsetsHelper(int[] S, int start, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> temp) {
        if (start >= S.length) return;
        
        for (int i = start; i < S.length; i++) {
            temp.add(S[i]);
            result.add(new ArrayList<Integer>(temp));
            subsetsHelper(S, i + 1, result, temp);
            
            temp.remove(temp.size() - 1);
        }
    }
}

Leetcode: Pow(x, n)

Implement pow(xn).

Understand the problem:
This problem looks quite simple at the first glance, however requires considering many corner cases. As defined in the interface, x is a double type, n is int, the return is double. 
Consider when n is negative. 

Naive Solution:
A very straight-forward idea is noticing that x^n equals to x * x * x... x, so we just need to time them up. 

Code (Java):
public class Solution {
    public double pow(double x, int n) {
        double result = 1;
        for (int i = 0; i < n; i++) {
            result *= x;
        }
        return result;
    }
}


Discussion:
The solution has time complexity O(n). It got the TLE error on OJ. Thus we need to figure out a more efficient solution.

A better solution:
We can do it in O(logn) time, think about the reduction operations in logn time. We can do it similar. We can use a recursive solution:

Code (Java):
public class Solution {
    public double pow(double x, int n) {
        if (n < 0) {
            return 1 / powHelper(x, -n);
        } else {
            return powHelper(x, n);
        }
    }
    
    private double powHelper(double x, int n) {
        if (n == 0) return 1;
        
        double v = powHelper(x, n/2);
        
        if (n % 2 == 0) {
            return v * v;
        } else {
            return v * v * x;
        }
    }
}

Summary:
This problem is not hard naturally, but the O(logn) solution requires a bit more effort. Do consider recursion when you are found you can divide the problem into smaller problems.

Leetcode: Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

Understand the problem:
The problem asks for determining if an integer is a palindrome. In addition, it requires the in-place results. There are several points to consider:

  • For an positive number, e.g. 141, return true;
  • For an negative number, e.g. -141, return false, as required by the OJ.
  • For integer with single digit, return true
Naive Solution:
One naive solution is to first reverse the integer, and check if they are the same. If works, but at the cost of reversing the integer. Also you need to handle the overflow problem of the reversed integer.

A better Solution:
If an integer is a palindrome, it must be mirrored at the center pointer. So we can start from the beginning and end of the integer, parse the digit, and compare them. We have already know how to parse an integer from the end. But how to do it in forward order? For e.g., 123,
we can get 1 by 123 / 100 = 1, then 123 - 1 * 100  =23
23 / 10 = 2, then 23 - 2 * 10 = 3
3/ 1 = 3, 3 - 3 * 1 = 0

So we must first get the length of the number. In addition, we also need to mark down the current position of the pointer i and j. 

Code (Java):
public class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;

        // get length of the integer
        int len = 0;
        int temp = x;
        while (temp > 0) {
            len++;
            temp /= 10;
        }
        
        int i = 0;
        int j = len - 1;
        int xLeft = x;
        int xRight = x;
        int n = len;
        while (i < j) {
            // get digit from left
            int lDigit = (int)(xLeft / Math.pow(10, n - 1));
            xLeft -= lDigit * Math.pow(10, n - 1);
            n--;
            
            // get digit from right
            int rDigit = xRight % 10;
            xRight /= 10;
            
            if (lDigit != rDigit) return false;
            
            i++;
            j--;
        }
        return true;
    }
}

Discussion:
We can see that the solution above has time complexity O(n) and space complexity O(1).




Leetcode: Reverse Integer

Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
Have you thought about this?
Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).

Understand the problem:
The problem asks for reversing an integer. As suggested by the problem, there are several cases need to consider.

  • For an positive number, .e.g. 123, return 321
  • For a negative number, e.g. -123, return -321
  • For an integer ends with 0, e.g. 1230, return 321. 
  • Handle the reverse integer is overflowed. E.g. the Integer.MAX_VALUE, 2147483648, the reverse number is overflowed. One possible way is to use a long int to store the number, if it is overflowed, return the MAX_VALUE or MIN_VALUE, else cast back to integer. 
Solution:
The basic idea is to firstly parse the integer into digits and store them. We parse it from right to left, according to  the post of "convert string into integer". So for integer 123, the parsed digits would be 321. If there are leading zeros, we ignore it. Then we convert the digits into an integer, stored in the long format. 

Code (Java):
public class Solution {
    public int reverse(int x) {
        if (x < 10 && x > -10) return x;
        
        ArrayList<Integer> buf = new ArrayList<Integer>();
        boolean neg = false;
        long result = 0;
        
        // if x is negative, we turn it to postive in temporary
        if (x < 0) {
            neg = true;
            x = -x;
        }
        
        // parse the integer into digits and store into the buf
        while (x > 0) {
            int temp = x % 10;
            buf.add(temp);
            x /= 10;
        }
        
        // remove leading zeros
        int start = 0;
        for (int i = 0; i < buf.size(); i++) {
            if (buf.get(i) != 0) {
                start = i;
                break;
            }
        }
        
        // convert the digits back to reversed integer
        for (int i = start; i < buf.size(); i++) {
            result *= 10;
            result += buf.get(i);
        }
        
        // consider the negative value
        if (neg) result = -result;
        
        // handle the overflow
        if (result > Integer.MAX_VALUE) return Integer.MAX_VALUE;
        if (result < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        
        return (int)result;
    }
}

Discussion:
The code is correct but looks redundant. It need extra space to store the temporary string/list. 

A Better Solution:
A better way is when we get an integer from the end, we directly convert to the reverse integer. In this way we don't need to care about the leading zeros as well. 

Code (Java):
public class Solution {
    public int reverse(int x) {
        if (x < 10 && x > -10) return x;
        long result = 0;
        boolean neg = false;
        
        // consider the negative case
        if (x < 0) {
            neg = true;
            x= -x;
        }
        
        while (x > 0) {
            int digit = x % 10;
            x = x / 10;
            
            result = result * 10 + digit;
        }
        
        if (neg) result = -result;
        
        // handle the overflow issue
        if (result > Integer.MAX_VALUE) return Integer.MAX_VALUE;
        if (result < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        
        return (int) result;
    }
}

Summary:
This question is not difficult. But some take-away messages: 

  • Handle each corner cases well, e.g. negative, leading zeros, integer overflow, etc..
  • Convert integer to string, using %10,  and /10
  • Convert string to integer, using *10

Thursday, August 28, 2014

Leetcode: Permutation II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2][1,2,1], and [2,1,1].

Understand the problem:
The problem is an extension to Permutation I, the mainly difference is it exists the duplicated elements, and we return only unique permutations. 

Solution:
The solution is very similar to the permutation I, the only difference is before we swap the number start and i, we check if between start and i has duplicates. If yes, it indicates that we visited the number before, so simply jump to next iteration.

Code (Java):
public class Solution {
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        
        permuteUnique(num, 0, result);
        
        return result;
    }
    
    private void permuteUnique(int[] num, int start, ArrayList<ArrayList<Integer>> result) {
        if (start >= num.length) {
            ArrayList<Integer> temp = toArrayList(num);
            result.add(temp);
            return;
        }
        
        for (int i = start; i < num.length; i++) {
            if (!containsDup(num, start, i)) {
                swap(num, i, start);
                permuteUnique(num, start + 1, result);
                swap(num, i, start);
            }
        }
    }
    
    private void swap(int[] num, int i, int j) {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
    
    private ArrayList<Integer> toArrayList(int[] num) {
        ArrayList<Integer> temp = new ArrayList<Integer>(num.length);
        for (int i = 0; i < num.length; i++) {
            temp.add(num[i]);
        }
        return temp;
    }
    
    private boolean containsDup(int[] num, int start, int end) {
        for (int i = start; i <= end - 1; i++) {
            if (num[i] == num[end]) return true;
        }
        return false;
    }
}

Discussion:
Note the method on how to determine the duplicates. This the most tricky part of this problem.

Update on 07/29/18:
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        
        if (nums == null || nums.length == 0) {
            return ans;
        }
        
        Arrays.sort(nums);
        
        permuteHelper(0, nums, ans);
        
        return ans;
    }
    
    private void permuteHelper(int start, int[] nums, List<List<Integer>> ans) {
        if (start >= nums.length) {
            ans.add(new ArrayList<>(Arrays.stream(nums).boxed().collect(Collectors.toList())));
            return;
        }
        
        Set<Integer> set = new HashSet<>();
        for (int i = start; i < nums.length; i++) {
            if (set.add(nums[i])) {
                swap(nums, i, start);
                permuteHelper(start + 1, nums, ans);
                swap(nums, i, start);
            }
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Update 5/7/19:

public class Solution {
    /*
     * @param :  A list of integers
     * @return: A list of unique permutations
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        // write your code here
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            ans.add(new ArrayList<Integer>());
            return ans;
        }

        Arrays.sort(nums);

        boolean[] visited = new boolean[nums.length];
        permuteUniqueHelper(nums, visited, new ArrayList<Integer>(), ans);
        return ans;
    }

    private void permuteUniqueHelper(int[] nums, boolean[] visited, List<Integer> curList, List<List<Integer>> ans) {
        if (curList.size() == nums.length) {
            ans.add(new ArrayList<>(curList));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
                continue;
            }

            visited[i] = true;
            curList.add(nums[i]);
            permuteUniqueHelper(nums, visited, curList, ans);
            visited[i] = false;
            curList.remove(curList.size() - 1);
        }
    }
}

Leetcode: Permutation

Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2], and [3,2,1].

Understand the problem:
The problem gives a collection of numbers, ask for returning all possible permutations. 
For an array with length n, the number of possible permutations n! 

Recursive Solution:
It is not hard to think of a recursive solution. 

Code (Java):
public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        
        permute(num, 0, result);
        
        return result;
    }
    
    private void permute(int[] num, int start, ArrayList<ArrayList<Integer>> result) {
        if (start >= num.length) {
            ArrayList<Integer> temp = toArrayList(num);
            result.add(temp);
        }
        
        for (int i = start; i < num.length; i++) {
            swap(num, start, i);
            permute(num, start + 1, result);
            swap(num, start, i);
        }
    }
    
    private void swap(int[] num, int i, int j) {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
    
    private ArrayList<Integer> toArrayList(int[] num) {
        int len = num.length;
        ArrayList<Integer> temp = new ArrayList<Integer>(len);
        for (int i = 0; i < len; i++) {
            temp.add(num[i]);
        }
        return temp;
    }
}


Summary:
The crux of this problem is using recursion. This problem is very similar to the palindrome partition. The only trick is to swap the number and swap them back. 

Update on 5/7/19:
public class Solution {
    /*
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    public List<List<Integer>> permute(int[] nums) {
        // write your code here
        List<List<Integer>> ans = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        
        permuteHelper(nums, visited, new ArrayList<Integer>(), ans);
        
        return ans;
    }
    
    private void permuteHelper(int[] nums, boolean[] visited, List<Integer> curList, List<List<Integer>> ans) {
        if (curList.size() == nums.length) {
            ans.add(new ArrayList<>(curList));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            
            visited[i] = true;
            curList.add(nums[i]);
            permuteHelper(nums, visited, curList, ans);
            visited[i] = false;
            curList.remove(curList.size() - 1);
        }
    }
}

Leetcode: Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Understand the problem:
The problem is similar to the Single Number I, except that each number appears three times. Note that the problem asks for linear time complexity and constant space. 

Naive Solution:
The naive solution could use a hash table. It uses hash table instead of hash set because we want store the number of occurrence of each number. For each number if it is the first or second occurrences, we update the second value. For the third times, we remove that entry. So the only number in hash table is the one we are looking for.

Code (Java):
public class Solution {
    public int singleNumber(int[] A) {
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        int num = 0;
        
        for (int i = 0; i < A.length; i++) {
            if (!hashMap.containsKey(A[i])) {
                hashMap.put(A[i], 1);
            } else if (hashMap.get(A[i]) == 1) {
                hashMap.put(A[i], 2);
            } else if (hashMap.get(A[i]) == 2) {
                hashMap.remove(A[i]);
            }
        }
        Set<Integer> set = new HashSet<Integer>();
        set = hashMap.keySet();
        
        for (Integer n : set) {
            num = n;
        }
        return num;
    }
}
  
Discussion:
We see that the solution has O(n) in time, however O(n) in space. So we need to find out another way to solve it using constant space.

A Better Solution:
public class Solution {
    public int singleNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int[] bits = new int[32];
        
        // step 1: calcuate the number of bits for each number
        for (int num : nums) {
            int mask = 1;
            for (int i = 31; i >= 0; i--) {
                if ((num & mask) != 0) {
                    bits[i]++;
                }
                mask = (mask << 1);
            }
        }
        
        // step 2: find out the single number
        int result = 0;
        for (int i = 0; i < 32; i++) {
            bits[i] %= 3;
            if (bits[i] == 1) {
                result += 1;
            }
            
            if (i == 31) {
                break;
            }
            
            result = (result << 1);
        }
        
        return result;
    }
}















Leetcode: Single Number

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?


Understand the Problem:
As described in the problem, given an array of integers, every element appears twice except for one. The problem asks for finding the single one. Furthermore, the problem asks for linear time complexity and constant space complexity. 

Naive Approach:
As is described in the problem, each element appears twice except for one. So a straight-forward solution could use a hash set. For the element first encountered, we add it into the set. For the second met, we remove it. As a result, after iterating all elements of the array, the hashset only contains one element, which is the one we are looking for.

Code (Java):
public class Solution {
    public int singleNumber(int[] A) {
        HashSet<Integer> hashset = new HashSet<Integer>();
        int ret = 0;
        int len = A.length;
        
        for (int i = 0; i < len; i++) {
            if (!hashset.contains(A[i])) {
                hashset.add(A[i]);
            } else {
                hashset.remove(A[i]);
            }
        }
        
        for (Integer num : hashset) {
            ret = num;
        }
        return ret;
    }
}

Discussion:
As we can see that this approach has time complexity of O(n). However, the space complexity is O(n) as well since we used additional space. 

A better approach:
Since we are required to use constant space, we can think of using bit manipulation. We use XOR. Since x ^ x = 0. x ^ y ^ x = y. So we can use the XOR to eliminate the repeated numbers. 

Code (Java):
public class Solution {
    public int singleNumber(int[] A) {
        int num = A[0];
        
        for (int i = 1; i < A.length; i++) {
            num = num ^ A[i];
        }
        
        return num;
    }
}

Discussion:
Note that the solution utilized two properties: First of all, XOR is comm.communicative, i.e. x ^ y ^ x = x ^ x ^ y = y. Second, The solution relied on the assumption that each number appeared two times while one appears once. If this condition does not stand, the solution of using XOR does not hold.

Summary:
This post we learned a very simple problem but required tricky solution to solve it. Using bit manipulation is very subtle. If you are asked to perform an operation without using extra space, consider the bit manipulation. 

Wednesday, August 27, 2014

Leetcode: Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Understand the problem:
The problem asks for finding the longest palindromic substring in string S. The problem assumes that there is only one unique longest palindromic substring, and we are asked to return that substring. 

Naive Solution:
One straight-forward solution is to check each substring and determine if it is palindromic. So looping over each substring take O(n^2) time and checking each substring takes O(n) time. The total time complexity is O(n^3). 

DP Solution:

This question is quite similar to the Palindrome partitioning II, where return the minimum number of cuts such that all substrings are palindrome. The minimum cuts are equal to the longest palindrome. So we can still use the same idea to solve this problem.

In the palindrome partitioning II problem, we used an array dp[i] to indicate the minimum number of cuts from i to the end. However, in this problem, the longest palindromic substring does not always start from the first character of the input string; it can start from anywhere else. So we don't need to maintain an array dp[i] and check the results in dp[0]. Instead, whenever we found string[i, j] is a palindrome, we check its length. If it is the maximum, we keep it. In this way, we only keep the longest palindromic substring. The way to determine if a string from [i, j] is palindromic is the same as before.  

Code (Java):
public class Solution {
    public String longestPalindrome(String s) {
        String longestStr = null;
        int maxLen = 0;
        
        if (s == null || s.isEmpty()) return s;
        
        int len = s.length();
        boolean[][] palin = new boolean[len][len];
        
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if ((s.charAt(i) == s.charAt(j) && (j - i) < 2) || (s.charAt(i) == s.charAt(j) && palin[i + 1][j - 1])) {
                    palin[i][j] = true;
                    int temp = j - i + 1;
                    if (temp > maxLen) {
                        maxLen = temp;
                        longestStr = s.substring(i, j + 1);
                    }
                }
            }
        }
        return longestStr;
    }
}

Discussion:
So we see that both time and space complexity is O(n^2) for this solution. 


O(1) Space solution:
We can even develop a O(1) space solution. For a string is palindrome, it must be mirrored across a central point. Here we must consider both the even and odd length of the string. For a string with odd length, e.g. aa, it is palindromic for s[lo] == s[hi] where lo = 0, and hi = 1. For odd length, e.g. aba, lo = 0, and hi = 2. So we can iterate the string and check its left and right points to see if it is mirrored. 

Code (Java):
public class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len <= 1) return s;
        
        int start = 0;
        String longestSub = "";
        int maxLen = 0;
        
        for (int i = 1; i < len; i++) {
            //check the longest palindromic substring with even length;
            int lo = i - 1;
            int hi = i;
            
            while (lo >= 0 && hi < len && s.charAt(lo) == s.charAt(hi)) {
                lo--;
                hi++;
            }
            
            if ((hi - lo - 1) > maxLen) {
                maxLen = hi - lo - 1;
                start = lo + 1;
            }
            
            // check the longest palindromic substring with odd length
            lo = i - 1;
            hi = i + 1;
            
            while (lo >= 0 && hi < len && s.charAt(lo) == s.charAt(hi)) {
                lo--;
                hi++;
            }
            
            if ((hi - lo - 1) > maxLen) {
                maxLen = hi - lo - 1;
                start = lo + 1;
            }
        }
        return s.substring(start, start + maxLen);
    }
}

Discussion:
We can see that the solution above has time complexity of (n^2) since each point we need to check its left and right sides. The space complexity is (1).
Summary:
In this post, we learned how to find the longest palindromic substring. It is a classic problem. The DP solution is classic as well. Make sure you can apply it to other DP problems. Actually, there exists another method with time complexity of O(n). It is kind of complicated so we don't cover it here. 

Update on 11/26/14:
public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }    
        
        int start = 0;
        int len = 1;
        
        for (int i = 0; i < s.length(); i++) {
            int curLen = 0;
            // For even length
            int lo = i;
            int hi = i + 1;
            while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {
                curLen += 2;
                lo--;
                hi++;
            }
            if (curLen > len) {
                len = curLen;
                start = lo + 1;
            } 
            // For odd length
            lo = i - 1;
            hi = i + 1;
            curLen = 1;
            while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {
                curLen += 2;
                lo--;
                hi++;
            }
            
            if (curLen > len) {
                len = curLen;
                start = lo + 1;
            }
        }
        return s.substring(start, start + len);
    }
}
Update on 4/7/2019
public class Solution {
    /**
     * @param s: input string
     * @return: the longest palindromic substring
     */
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        int maxLen = 0;
        int startIdx = 0;
        
        for (int i = 0; i < s.length(); i++) {
            int lenEven = findLongestPalin(s, i, i + 1);
            int lenOdd = findLongestPalin(s, i - 1, i + 1) + 1;
            
            if (lenEven > lenOdd && lenEven > maxLen) {
                maxLen = lenEven;
                startIdx = i - lenEven / 2 + 1;
            } else if (lenOdd > lenEven && lenOdd > maxLen) {
                maxLen = lenOdd;
                startIdx = i - lenOdd / 2;
            }
        }
        
        return s.substring(startIdx, maxLen + startIdx);
    }
    
    private int findLongestPalin(String s, int start, int end) {
        int ans = 0;
        
        while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
            start--;
            end++;
            ans += 2;
        }
        
        return ans;
    }
}

Tuesday, August 26, 2014

Leetcode: Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Understand the problem:
The problem asks for partitioning a string s such that every substring of the partition is a palindrome. The mainly difference between the palindrome partition problem is it returns the minimum cuts needed for a palindrome partitioning of s. 

Naive Solution:
One naive solution is to find out a partition, then count the number of cuts. We maintain the minimum cuts. After we found all possible partitions, we return the minimal cuts. So the code looks very closed to the palindrome partitioning. 

Code (Java):
public class Solution {
    private int min = Integer.MAX_VALUE;
    
    public int minCut(String s) {
        if (s == null || s.length() == 0) return 0;
        if (isPalin(s)) return 0;
        
        ArrayList<String> list = new ArrayList<String>();
        
        minCut(s, list);
        
        return min;
    }
    
    private void minCut(String s, ArrayList<String> list) {
        if (s.isEmpty()) {
            min = Math.min(min, list.size() - 1);
            return;
        }
        
        for (int i = 1; i <= s.length(); i++) {
            if (isPalin(s.substring(0, i))) {
                list.add(s.substring(0, i));
                minCut(s.substring(i), list);
                list.remove(list.size() - 1);
            }
        }
    }
    
    private boolean isPalin(String s) {
        if (s == null) return true;
        
        int start = 0;
        int end = s.length() - 1;
        
        while (start < end) {
            if (s.charAt(start) == s.charAt(end)) {
                start++;
                end--;
            } else {
                return false;
            }
        }
        return true;
    }
}

Discussion:
The naive solution has TLE error. Let's analyze the time complexity at first. Recursion takes O(n) time, however, note that the isPalindrome function also takes O(n) time as well. So the overall time complexity is O(n^2). 

A DP Solution:
Since we now know that most of the time takes on determining if a string is a palindrome. We can do it better to reduce the time. 
We define dp[ i ] means minimum cuts from i to end. 
We define palin[i][j] = true to indicate if string from index i to j is a palindrome. palin[i][j] is palindrome if and only if [i+1, j-1] is a palindrome AND s[i] = s[j]. Or j - i < 2 && s[i] == s[j], meaning the string s has at most 2 characters. 

Code (Java):
public class Solution {
    public int minCut(String s) {
        if (s == null || s.length() == 0) return 0;
        
        int len = s.length();
        int[] dp = new int[len + 1];
        boolean[][] palin = new boolean[len][len];
        
        // initialize dp[]
        for (int i = 0; i < len; i++) {
            dp[i] = len - i;
        }
        
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if ((s.charAt(i) == s.charAt(j) && (j - i) < 2) || 
                    (s.charAt(i) == s.charAt(j) && palin[i + 1][j - 1])) {
                    palin[i][j] = true;
                    dp[i] = Math.min(dp[i], dp[j + 1] + 1);
                }
            }
        }
        return dp[0] - 1;
    }
}

Leetcode: Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
Understand the problem:
As described by the problem, given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
So the key to understand this problem is to know what is adjacent numbers?
For index = 1 in row i, the adjacent numbers that 1 can go is index 0, 1, 2 on row i + 1. 

In addition, the problem allows negative numbers in the triangle, so we must consider all possible paths. 

However, after reading some posts, I found that the adjacent numbers for A[ i ][ j ] is actually A[ i + 1 ][ j ] and A[ i + 1 ] [ j + 1 ], no A[i + 1] [j - 1]. 

Recursive Solution:
Consider the DFS. Use post-order traversal, i.e. bottom-up traversal. 

Code (Java):
public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        return postOrderTraversal(triangle, 0, 0);
    }
    
    private int postOrderTraversal(List<List<Integer>> triangle, int layer, int next) {
        if (layer == triangle.size()) return 0;
        
        int lMax = postOrderTraversal(triangle, layer + 1, next);
        int rMax = postOrderTraversal(triangle, layer + 1, next + 1);
        
        return Math.min(lMax, rMax) + triangle.get(layer).get(next);
    }
}

Discussion:
Now let's analyze the complexity. The time complexity is O(2^n) since it has many repeated calculations. Therefore we can think of a DP solution.

DP Solution:
public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[][] dp = new int[triangle.size()][triangle.size()];
        return postOrderTraversal(triangle, 0, 0, dp);
    }
    
    private int postOrderTraversal(List<List<Integer>> triangle, int layer, int next, int[][] dp) {
        if (layer == triangle.size()) return 0;
        
        if (dp[layer][next] != 0) return dp[layer][next];
        
        int lMax = postOrderTraversal(triangle, layer + 1, next, dp);
        int rMax = postOrderTraversal(triangle, layer + 1, next + 1, dp);
        
        dp[layer][next] = Math.min(lMax, rMax) + triangle.get(layer).get(next);
        return dp[layer][next];
    }
}

Discussion:
From the solution, we can see that the space complexity now becomes O(n^2) since we allocated O(n^2) space of the array, where n is the number of rows. 

A Space-optimal Solution:
For the DP solution, we can find actually we only need to store layer i + 1 for calculating layer i. Consequently, we only need to create an array with size row (maximal number of numbers for the last row). 

Since DFS cannot traverse the "tree" in level order. In this solution, we use an iterative approach. 

Code (Java):
public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.isEmpty()) return 0;
        
        int[] dp = new int[triangle.size()];
        
        // save the last row
        for (int i = 0; i < triangle.size(); i++) {
            dp[i] = triangle.get(triangle.size() - 1).get(i);
        }
        
        // start from the second last row bottom-up
        for (int i = triangle.size() - 2; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
            }
        }
        return dp[0];
    }
}

Summary:
This problem is a very classical DP problem. Make sure at least you understand the first recursive solution. The idea of post-order traversal is often used in many maximal/minimum path sum problems. Make sure you understand the first DP approach. The last solution is very tricky. Understand the idea.


Update on 10/9/2014:
Top-down 2D DP:
dp[i][j] -- the minimum path sum from root to position i, j
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
initial: dp[0][0] = 0;
dp[i][0] = dp[i - 1][0] + triangle[i][j];
Others are set to Integer.MAX_VALUE

Final state: min (dp[n - 1][0] ... dp[n - 1][n - 1])


public class Solution {
    int min = Integer.MAX_VALUE;
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        
        // 2D DP solution
        int n = triangle.size();
        int[][] dp = new int[n][n];
        
        // Initialize
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < triangle.get(i).size(); j++) {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
            }
        }
        
        int min = Integer.MAX_VALUE;
        for (int i  = 0; i < n; i++) {
            if (dp[n - 1][i] < min) {
                min = dp[n - 1][i];
            }
        }
        
        return min;
    }
}

1D DP solution:
dp[j]: the minimum path sum from bottom to the column j at current level
Transit function: dp[j] = dp[j] + dp[j + 1]
Initial state:    Initialize dp[j] as the bottom number of the triangle
Final state:     dp[0].

Code (java):
public class Solution {
    int min = Integer.MAX_VALUE;
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        
        int n = triangle.size();
        /// 1D DP solution
        int[] dp = new int[n];
        
        /// Initialization
        for (int i = 0; i < n; i++) {
            dp[i] = triangle.get(n-1).get(i);
        }
        
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        
        return dp[0];
    }
}







Leetcode: Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Understand the problem:
The problem asks for finding a subarray which yields in the largest sum. It is not hard to find that for a brute force solution, we try all possible combinations and add them up, so we have totally Cn1 + Cn2 + ... + Cnn = n! combinations. That motivate us find a practical solution in polynomial time.

Note that this problem is ambiguous. In real code interview, you may be asked for two cases. The first case, for a array with only negative numbers, return 0, meaning empty subarray.
The second case is to return the maximal negative value. Both of the cases can pass the OJ here, but the code will look different. 


In this problem, we onlNote that this problem is ambiguous. In real code interview, you may be asked for two cases. The first case, for a array with only negative numbers, return 0, meaning empty subarray.
The second case is to return the maximal negative value. Both of the cases can pass the OJ here, but the code will look different. y consider the second case, where return the maximal negative value. I think that makes more sense to me. Of course, changing to the first case requires little changes in the code. 

DP Solution:
We use an array, s[ ] to store the max(A[i] + s[i - 1], A[i]). That is, the maximum sum of the previous number, or A[i], whoever greater. The purpose is if the previous sum deduct the current number A[i], we discard the previous sum and start the sum from A[i]. 

Code (Java):
public class Solution {
    public int maxSubArray(int[] A) {
        if (A == null || A.length == 0) return 0;
        
        int[] s = new int[A.length];
        s[0] = A[0];
        
        int max = A[0];
        
        for (int i = 1; i < A.length; i++) {
            s[i] = Math.max(s[i - 1] + A[i], A[i]);
            max = Math.max(s[i], max);
        }
        return max;
    }
}

Discussion:
The time complexity is O(n) since we only traverse the array once. The space complexity is O(n) as well. 

An O(1) Space Solution:
Consider the Line 11 in the above solution. s[i] is determined by the maximal s[i - 1] + A[i] and A[i]. So what caused s[i - 1] + A[i] < A[i]. That is obvious, s[i - 1] < 0. So we can devise a constant space solution that when sum < 0, we discarded the previous sum and start from this number. Since we don't need to maintain an array but just a variable sum, its space complexity is O(1).

Code (Java):
public class Solution {
    public int maxSubArray(int[] A) {
        if (A == null || A.length == 0) return 0;
        
        int max = Integer.MIN_VALUE;
        int sum = 0;
        
        for (int i = 0; i < A.length; i++) {
            if (sum < 0) {
                sum = A[i];
            } else {
                sum += A[i];
            }
            max = Math.max(max, sum);
        }
        return max;
    }
}

Divide-and-Conquer Solution:
The idea of divide-and-conquer is similar to the binary search. We first cut the array into three parts, A[0, mid - 1], A[mid], A[mid + 1, len - 1]. As a result, the maximum subarray must exist either in left or right part, or cross the middle point. 

Code (Java):
public class Solution {
    int max = Integer.MIN_VALUE;
    public int maxSubArray(int[] A) {
        if (A == null || A.length == 0) return 0;
        
        return maxSubArray(A, 0, A.length - 1);
    }
    
    private int maxSubArray(int[] A, int lo, int hi) {
        if (lo > hi) return Integer.MIN_VALUE;
        
        int mid = (lo + hi)/2;
        
        int lMax = maxSubArray(A, lo, mid - 1);
        int rMax = maxSubArray(A, mid + 1, hi);
        
        max = Math.max(max, lMax);
        max = Math.max(max, rMax);
        
        // find max from middle to left
        int mlMax = 0;
        int sum = 0;
        for (int i = mid - 1; i >= lo; i--) {
            sum += A[i];
            mlMax = Math.max(mlMax, sum);
        }
        
        // find max from middle to right
        int mrMax = 0;
        sum = 0;
        for (int i = mid + 1; i <= hi; i++) {
            sum += A[i];
            mrMax = Math.max(mrMax, sum);
        }
        
        return Math.max(max, mrMax + mlMax + A[mid]);
        
    }
}

Discussion:
Note in Line 21 and 29, mlMax and mrMax = 0. This 0 is very important and should not be Integer.MIN_VALUE. That is  because in the case where the maximum subarray across the mid point, it could be actually four cases: left + mid, mid, right + mid,  left + mid + right. However, if either left or right sum is less than zero, we can simply discard that part. That is why the mlMax and mrMax start from zero, and we simply calculate the left + mid + right which guarantee covering all cases above. 

For the divide and conquer, the time complexity is O(n logn). That is because for the recursion the time is O(logn), while for each recursion we have two for loops, which could be at worst O(n), so the total time complexity is O(nlogn).

Summary:
Finding the maximum subarray is a classical problem. Make sure you understand the DP solution with O(n) time. 


Update on 4/7/2019:
public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int curSum = 0;
        int minPreSum = 0;
        int maxSum = Integer.MIN_VALUE;
        
        for (int i = 0; i < nums.length; i++) {
            curSum += nums[i];
            maxSum = Math.max(maxSum, curSum - minPreSum);
            
            minPreSum = Math.min(minPreSum, curSum);
        }
        
        return maxSum;
        
    }
}