(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;
        }
    }
};
Advertisements

(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;
        }
    }
};

Previous Older Entries