(Minimum Path Sum)

Given a m \times n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

Thoughts:
Because the grid is filled with non-negative numbers. Standing at any position (i, j), the minimum sum we can get is \text{grid}[i,j] + \min(minimum sum starting from[i+1,j], minimum sum starting from [i,j+1]). Hence we find the recursive structure of this problem. The base case would be one element only, one row only and one column only. Notice that we could end up with repeating computations a lot (e.g., right->down and down->right), hence we should employ dynamic programming, in which we introduce a hashmap to cache the partial result.

Code (Java):

public class Solution {
    
    private Map<List<Integer>, Integer> map = 
            new HashMap<List<Integer>, Integer>();
    
    public int minPathSum(int[][] grid) {
        map.clear();
        return minPathSumRec(grid, 0, 0);
    }
    
    private int minPathSumRec(int[][] grid, int i, int j) {
        List<Integer> pair = new ArrayList<Integer>();
        pair.add(i);
        pair.add(j);
        if(map.get(pair) != null)
           return map.get(pair);
        else {
            int r = grid[i][j];;
            if(i == grid.length-1 && j == grid[0].length - 1)
                r += 0; 
            else if(i == grid.length - 1)
                r += minPathSumRec(grid, i, j + 1);
            else if(j == grid[0].length - 1)
                r += minPathSumRec(grid, i + 1, j);
            else
                r += Math.min(minPathSumRec(grid, i + 1, j), 
                        minPathSumRec(grid, i, j + 1));
            map.put(pair, r);
            return r;
        }
    }
}

Code (C++):

class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        cache.clear();
        return minPathSumRec(grid, 0, 0);
    }
    
private:
    map<vector<int>, int> cache;

    int minPathSumRec(vector<vector<int> > &grid, int i, int j) {
        vector<int> pair(2);
        pair[0] = i;
        pair[1] = j;
        if(cache.find(pair) != cache.end())
            return cache[pair];
        else {
            int r = grid[i][j];
            if(i == grid.size() -1 && j == grid[0].size() - 1)
                r += 0;
            else if(i == grid.size() - 1)
                r += minPathSumRec(grid, i, j + 1);
            else if(j == grid[0].size() - 1)
                r += minPathSumRec(grid, i + 1, j);
            else
                r += min(minPathSumRec(grid, i, j + 1), 
                        minPathSumRec(grid, i + 1, j));
            cache[pair] = r;
            return r;
        }
    }
};

(Minimum Depth of Binary Tree)

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Thoughts:
Sense of recursion should be came out now.
What is the base case or edge case? Empty tree. What is the minimum depth of an empty tree? 0.
In the recursion step, the passed in TreeNode “root” is been looked at. “root” is not null, which was covered in the base case. Then there are four sub-cases or combinations, if you like:

  1. root is a leaf node. In other word, root.left == null && root.right == null. Return 1 at this case.
  2. root.left == null && root.right != null. Then we just need to recurse on the right, so we return 1 + minDepth(root.right).
  3. root.left != null && root.right == null. Similarly, we return 1 + minDepth(root.left).
  4. root.left != null && root.right != null. This is rather interesting case. We don’t know which branch of the case has shorter path, so we should return the minimum of these two.

In the code, we can actually combine the four cases into two!

Code (Java):

public class Solution {
    public int minDepth(TreeNode root) {
        if(root == null)
            return 0;
        else {
            if(root.left != null && root.right != null)    
                return 1 + Math.min(minDepth(root.left), minDepth(root.right));
            else
                return 1 + minDepth(root.right) + minDepth(root.left);
        }
            
    }
}

Code (C++):

class Solution {
public:
    int minDepth(TreeNode *root) {
        if(root == NULL)
            return 0;
        else if(root -> left != NULL && root -> right != NULL)
            return 1 + min(minDepth(root -> left), minDepth(root -> right));
        else
            return 1 + minDepth(root -> right) + minDepth(root -> left);
    }
};

(Longest Substring Without Repeating Characters)

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Thoughts:
We want to finish this task in one scan. We can maintain a hashtable to detect if we have seen any character. We start from the beginning and walk through the array until we hit a repetition, let’s say, at position i. We then have two piece of valuable information right now:

  1. s[0..i-1] is a candidate of the longest substring without repetition. Therefore we can update the max length.
  2. There exists a position 0 \leq j \leq i-1, such that s[j] == s[i]. Substring starting from j is not a candidate because it has at least one repetition: s[j] and s[i]. Any substring ended at j will be shorter than the substring s[0..i-1] so we don’t need to look at them.

Then we can remove every elements in the hashtable from 0 to j, and make the start position of next candidate to j + 1. We keep walking and repeating this process until we hit the last element.

Code (Java):

import java.util.HashSet;
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        HashSet<Character> set = new HashSet<Character>();
        int candidateStartIndex = 0;
        for(int iter = 0; iter < s.length(); ++iter) {
            char c = s.charAt(iter);
            if(set.contains(c)) {
                max = Math.max(max, iter - candidateStartIndex);
                while(s.charAt(candidateStartIndex) 
                        != s.charAt(iter)) {
                    set.remove(s.charAt(candidateStartIndex));
                    candidateStartIndex++;
                }
                candidateStartIndex++;
            } else {
                set.add(c);
            }
        }
        max = Math.max(max, s.length() - candidateStartIndex);
        return max;
    }
}

Code (C++):

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unsigned int maxLen = 0;
        set<char> hashtable;
        int candidateStartIndex = 0;
        for(unsigned int iter = 0; iter < s.size(); ++iter) {
            char c = s[iter];
            if(hashtable.find(c) != hashtable.end()) {
                maxLen = max(maxLen, iter - candidateStartIndex);
                while(s[candidateStartIndex] != s[iter]) {
                    hashtable.erase(s[candidateStartIndex]);
                    candidateStartIndex++;
                }
                candidateStartIndex++;
            } else {
                hashtable.insert(c);
            }
        }
        maxLen = max(maxLen, s.size() - candidateStartIndex);
        return maxLen;
    }
};

(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.

Thoughts:
Two parts of this question: determine if a string is palindrome and find out the longest palindrome. First part can be done in recursive or iterative way. We just need to check if the 1st letter == last letter, 2nd letter == 2nd last letter, so on and so forth. Second part we can do it using a sliding window approach. We examine if the entire string is palindrome or not, then the substrings of length n – 1 (there are two of them), then the substrings of length n – 2 (3 of them), etc.

Code (Java):

public class Solution {
    public String longestPalindrome(String s) {
        for(int len = s.length(); len > 0; --len) {
            for(int j = 0; j <= s.length() - len; ++j) {
                String sub = s.substring(j, j + len);
                if(isPalindrome(sub))
                    return sub;
            }
        }
        return new String();
    }
    
    private boolean isPalindrome(String s) {
        if(s.length() <= 1)
            return true;
        else
            return s.charAt(0) == s.charAt(s.length()-1) && 
                isPalindrome(s.substring(1,s.length()-1));
    }
}

Code (C++):

class Solution {
public:
    string longestPalindrome(string s) {
        for(int len = s.size(); len > 0; --len) {
            for(int i = 0; i <= s.size() - len; ++i) {
                string sub = s.substr(i, len);
                if(isPalindrome(sub))
                    return sub;
            }
        }
        return "";
    }
    
private:
    bool isPalindrome(string s) {
        if(s.size() <= 1)
            return true;
        else
            return s[0] == s[s.size() - 1] && 
            isPalindrome(s.substr(1,s.size()-2));
    }
};

(Letter Combinations of a Phone Number)

Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Thoughts:
Another classic recursion problem. We try to generate solution each time by iterating through every digit and every character that digit maps to. If we overflow, we cut that solution and stop. If we get the correct solution (where solution.length() == digits.length()), we add to the solution set.

Code (Java):

public class Solution {
    private HashMap<Character, String> map;
    
    public ArrayList<String> letterCombinations(String digits) {
        setup();
        ArrayList<String> solutions
            = new ArrayList<String>();
        recursion(digits, 0, new String(), solutions);
        return solutions;
    }
    
    private void recursion(String digits, int start, 
        String sol, ArrayList<String> solutions) {
        if(sol.length() > digits.length()) {
            return;  
        } else if(sol.length() == digits.length()) {
            solutions.add(sol);
            return;
        } else {
            for(int i = start; i < digits.length(); ++i) {
                String letters = map.get(digits.charAt(i));
                for(int j = 0; j < letters.length(); ++j) {
                    recursion(digits, i + 1, sol + letters.charAt(j), solutions);
                }
            }
        }
    }
    
    private void setup() {
        map = new HashMap<Character, String>();
        map.put('1', "");
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        map.put('0', " ");
    }
}

Code (C++):

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        setup();
        vector<string> solutions;
        string s;
        recursion(digits, 0, s, solutions);
        return solutions;
    }
    
private:
    map<char, string> mapping;
    void recursion(string digits, int start, 
        string sol, vector<string>& solutions) {
        if(sol.size() > digits.size()) {
            return;  
        } else if(sol.size() == digits.size()) {
            solutions.push_back(sol);
            return;
        } else {
            for(int i = start; i < digits.size(); ++i) {
                string letters = mapping[digits[i]];
                for(int j = 0; j < letters.size(); ++j) {
                    recursion(digits, i + 1, sol + letters[j], solutions);
                }
            }
        }
    }
    
    void setup() {
        mapping.clear();
        mapping['1'] = "";
        mapping['2'] = "abc";
        mapping['3'] = "def";
        mapping['4'] = "ghi";
        mapping['5'] = "jkl";
        mapping['6'] = "mno";
        mapping['7'] = "pqrs";
        mapping['8'] = "tuv";
        mapping['9'] = "wxyz";
        mapping['0'] = " ";
    }
};

(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.

Thoughts:
This is definitely do-able through recursion. I actually tried but got time exceed limit. So I came up with this iterative method with O(n^2) time complexity. We maintain a boolean table where table[i] stores whether you can reach the last index starting from index i. We start populating the table from the last position (n-1) of the array. We are at destination here so table[n-1] is always true. For each i, we look at all table values from i + 1 to n – 1. If we found a true value at j, we know we can reach the last index from j, so we just need to examine if we can reach index j from index i. If we can, then table[i] will be true and we don’t need to see the rest. In the worst case, for each i, we need to check every element from i + 1 to n – 1 so this is O(n^2).

Code (C++):

class Solution {
public:
    bool canJump(int A[], int n) {
        bool *table = new bool[n];
        table[n-1] = true;
        int start = n - 2;
        while(start >= 0) {
            table[start] = false;
            for(int j = start + 1; j < n; ++j) {
                if(table[j] && j - start <= A[start]) {
                    table[start] = true;
                    break;
                }
            }
            start--;
        }
        return table[0];
    }
};

Code (Java):

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

(Gray Code)

The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 – 0
01 – 1
11 – 3
10 – 2

Thoughts:
The tricky part of this question is to recognize the recursive structure here. For n = 0, sol = [0], that’s the base case. For recursive step, let’s take n = 2 and n = 3 as examples. n = 2, sol = [0, 1, 3, 2]; n = 3, sol = [0, 1, 3, 2, 6, 7, 5, 4]. Look at these two solutions, we see when n = 3, we add 4 more elements [6, 7, 5, 4] and they are just [2+4, 3+4, 1+4, 0+4]. That is sol(n+1) = sol(n) + [ reverse(sol(n)) + 2^(n) ].

Code (Java):

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> grayCode(int n) {
        ArrayList<Integer> sol = new ArrayList<Integer>();
        if(n == 0) {
            sol.add(0);
            return sol;
        } else {
            ArrayList<Integer> previous = grayCode(n - 1);
            sol.addAll(previous);
            for(int i = previous.size() - 1; i >= 0; --i) {
                sol.add((int)Math.pow(2.0, n - 1) + previous.get(i));
            }
            return sol;
        }
    }
}

Code (C++):

class Solution {
public:
    vector<int> grayCode(int n) {
        if(n == 0) {
            vector<int> sol;
            sol.push_back(0);
            return sol;
        } else {
            vector<int> previous = grayCode(n - 1);
            vector<int> sol(previous);
            for(int i = previous.size() - 1; i >= 0; --i) {
                sol.push_back((int)pow(2.0, n - 1) + previous[i]);
            }
            return sol;
        }
    }
};

All combinations of balanced parentheses (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:
“((()))”, “(()())”, “(())()”, “()(())”, “()()()”

Thoughts:
Recursion. Base case is which the solution has size of 2*n. Recursive step: each time we count number of open parenthesis and closed parenthesis. If open == closed, then we have to add open parenthesis. If open > closed, we can add open parenthesis as long as we do not exceed n. We can also add closed parenthesis.

Code (Java):

import java.util.ArrayList;
public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> solutions = new ArrayList<String>();
        recursion(n, new String(), solutions);
        return solutions;
    }

    private void recursion(int n, String str, ArrayList<String> sol) {
        if(str.length() == 2 * n)
            sol.add(str);
        else {
            int left = 0;
            int right = 0;
            for(int i = 0; i < str.length(); ++i) {
                if(str.charAt(i) == '(')
                    left++;
                if(str.charAt(i) == ')')
                    right++;
            }
            if(left == right)
                recursion(n, str + "(", sol);
            else if(right < left) {
                if(left < n)
                    recursion(n, str + "(", sol);
                recursion(n, str + ")", sol);
            }
        }
    }
}

Code (C++):

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> solutions;
        string solution;
        recursion(n, solution, solutions);
        return solutions;
    }

    void recursion(int n, string solution, vector<string> &solutions) {
        if(solution.size() == 2*n) {
            solutions.push_back(solution);
        } else {
            int left = 0;
            int right = 0;
            for(int i = 0; i < solution.size(); ++i) {
                if(solution[i] == '(')
                    left++;
                if(solution[i] == ')')
                    right++;
            }
            if(left == right)
                recursion(n, solution + "(", solutions);
            else if(left > right) {
                if(left < n)
                    recursion(n, solution + "(", solutions);
                recursion(n, solution + ")", solutions);
            }
        }
    }
};

Dynamic programing for edit distance (Edit Distance)

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2 (each operation is counted as 1 step). You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character

Thoughts:
First, we explain the recursive structure here. Denote ed(s_{1}, s_{2}) as the edit distance between s_{1} and s_{2}. For base case, we have:

  • ed('', '') = 0
  • ed('', s) = ed(s, '') = \|s\|

Then, for the recursive step, we have:

  • ed(s_{1}+ch1, s_{2}+ch2) = ed(s_{1}, s_{2}) if ch1 == ch2 since we don’t need to anything from s_{1},s_{2} to s_{1}+ch1, s_{2}+ch2.
  • ed(s_{1}+ch1, s_{2}+ch2) = \min(1 + ed(s_{1}, s_{2}), 1 + ed(s_{1}+ch1, s_{2}), 1 + ed(s_{1}, s_{2}+ch2)) if ch1 != ch2. Here we compare three options:
    1. Replace ch1 with ch2, hence 1 + ed(s_{1}, s_{2}).
    2. Insert ch2 into s_{2}, hence 1 + ed(s_{1}+ch1, s_{2}).
    3. Delete ch1 from s_{1}, hence 1 + ed(s_{1}, s_{2}+ch2).

Code (Java):

public class Solution {
    public int minDistance(String word1, String word2) {
        int[][] table = new int[word1.length()+1][word2.length()+1];
        for(int i = 0; i < table.length; ++i) {
            for(int j = 0; j < table[i].length; ++j) {
                if(i == 0)
                    table[i][j] = j;
                else if(j == 0)
                    table[i][j] = i;
                else {
                    if(word1.charAt(i-1) == word2.charAt(j-1))
                        table[i][j] = table[i-1][j-1];
                    else
                        table[i][j] = 1 + Math.min(Math.min(table[i-1][j-1], 
                            table[i-1][j]), table[i][j-1]);
                }
            }
        }
        return table[word1.length()][word2.length()];
    }
}

Code (C++):

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int> > table(word1.size()+1, vector<int>(word2.size()+1));
        for(int i = 0; i < word1.size()+1; ++i) {
            for(int j = 0; j < word2.size()+1; ++j) {
                if(i == 0)
                    table[i][j] = j;
                else if(j == 0)
                    table[i][j] = i;
                else {
                    if(word1[i-1] == word2[j-1])
                        table[i][j] = table[i-1][j-1];
                    else
                        table[i][j] = min(min(1+table[i-1][j-1],
                                1+table[i-1][j]), 1+table[i][j-1]);
                }
            }
        }
        return table[word1.size()][word2.size()];
    }
};

Number of ways decoding a message (Decode Ways)

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1
‘B’ -> 2

‘Z’ -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example, given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12). The number of ways decoding “12” is 2.

Thoughts:
Again, we can use recursion with backtracking. Each time we try to encode the first digit in the message to a letter, or we can encode the first two digits into a letter if possible, we then recursively do the samething for the sub-string. When there is no way to encode (e.g., encountering a single ‘0’, or encountering ’32’ and tyring to encode the two-digits to a letter), we simply return. If there is no sub-string to go on, we know we have found a valid solution, so we increase the count.

Code (C++):

class Solution {
public:
    int numDecodings(string s) {
        int solutions = 0;
        if(s.size() != 0)
            recursion(s, solutions);
        return solutions;
    }
    
    void recursion(string s,int &solutions) {
        if(s.size() == 0){
            solutions++;
        } else {
            int value = (int)s.at(0)- '0';
            if(value > 0 && value <= 9) {
                recursion(s.substr(1), solutions);
            }
            
            if(s.size() >= 2) {
                int value1 = (int)s.at(0) - '0';
                int value2 = (int)s.at(1) - '0';
                if(value1 == 1 && value2 >= 0 && value2 <= 9) {
                    recursion(s.substr(2), solutions);
                } else if(value1 == 2 && value2 >= 0 && value2 <= 6) {
                    recursion(s.substr(2), solutions); 
                }
            }
        }
    }
};

Code (Java):
This is a very werid way to do it, I know. The ArrayList solutions are pretty much useless there other than counting the number of valid solutions. It’s just a way to bypass the fact that Java cannot pass argument by reference.

import java.util.ArrayList;
public class Solution {
    public int numDecodings(String s) {
        ArrayList<Integer> solutions = new ArrayList<Integer>();
        if(s.length() != 0)
            recursion(s, solutions);
        return solutions.size();
    }
    
    private void recursion(String s, ArrayList<Integer> solutions) {
        if(s.length() == 0){
            solutions.add(1);
        } else {
            int value = Character.getNumericValue(s.charAt(0));
            if(value > 0 && value <= 9) {
                recursion(s.substring(1), solutions);
            }
            
            if(s.length() >= 2) {
                int value1 = Character.getNumericValue(s.charAt(0));
                int value2 = Character.getNumericValue(s.charAt(1));
                if(value1 == 1 && value2 >= 0 && value2 <= 9) {
                    recursion(s.substring(2), solutions);
                } else if(value1 == 2 && value2 >= 0 && value2 <= 6) {
                    recursion(s.substring(2), solutions); 
                }
            }
        }
    }
}

Previous Older Entries