(Minimum Window Substring)

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.
Note:
If there is no such window in S that covers all characters in T, return the emtpy string “”.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Thoughts:
The idea is from here. I try to rephrase it a little bit here. The general idea is that we find a window first, not necessarily the minimum, but it’s the first one we could find, traveling from the beginning of S. We could easily do this by keeping a count of the target characters we have found. After finding an candidate solution, we try to optimize it. We do this by going forward in S and trying to see if we could replace the first character of our candidate. If we find one, we then find a new candidate and we update our knowledge about the minimum. We keep doing this until we reach the end of S. For the giving example:

  1. We start with our very first window: “ADOBEC”, windowSize = 6. We now have “A”:1, “B”:1, “C”:1
  2. We skip the following character “ODE” since none of them is in our target T. We then see another “B” so we update “B”:2. Our candidate solution starts with an “A” so getting another “B” cannot make us a “trade”.
  3. We then see another “A” so we update “A”:2. Now we have two “A”s and we know we only need 1. If we keep the new position of this “A” and disregard the old one, we could move forward of our starting position of window. We move from A->D->O->B. Can we keep moving? Yes, since we know we have 2 “B”s so we can also disregard this one. So keep moving until we hit “C”: we only have 1 “C” so we have to stop. Therefore, we have a new candidate solution, “CODEBA”. Our new map is updated to “A”:1, “B”:1, “C”:1.
  4. We skip the next “N” and we arrive at “C”. Now we have two “C”s so we can move forward the starting position of last candidate: we move along this path C->O->D->E until we hit “B”. We only have one “B” so we have to stop. We have yet another new candidate, “BANC”.
  5. We have hit the end of S so we just output our best candidate, which is “BANC”.

Code (Java):

public class Solution {
    public String minWindow(String S, String T) {
        int[] needToFind = new int[256];
        int[] hasFound = new int[256];
        
        for(int i = 0; i < T.length(); ++i) {
            needToFind[T.charAt(i)]++;
        }
        
        int count = 0;
        int minWindowSize = Integer.MAX_VALUE;
        int start = 0, end = 0;
        String window = "";
        
        for(; end < S.length(); end++) {
            if(needToFind[S.charAt(end)] == 0) continue;
            char c = S.charAt(end);
            hasFound[c]++;
            
            if(hasFound[c] <= needToFind[c]) {
                count++;
            }
            
            if(count == T.length()) {
                while(needToFind[S.charAt(start)] == 0 ||
                    hasFound[S.charAt(start)] > needToFind[S.charAt(start)]) {
                    if(hasFound[S.charAt(start)] > needToFind[S.charAt(start)])
                        hasFound[S.charAt(start)]--;
                    start++;
                }
                
                if(end - start + 1 < minWindowSize) {
                    minWindowSize = end - start + 1;
                    window = S.substring(start, end + 1);
                }
            }
        }
        
        return window;
    }
}

Code (C++):

class Solution {
public:
    string minWindow(string S, string T) {
        int needToFind[256] = {0};
        int hasFound[256] = {0};
        
        for(int i = 0; i < T.size(); ++i) {
            needToFind[T[i]]++;
        }
        
        int count = 0;
        int minWindowSize = INT_MAX;
        int start = 0, end = 0;
        string window;
        
        for(; end < S.size(); end++) {
            if(needToFind[S[end]] == 0) continue;
            hasFound[S[end]]++;
            
            if(hasFound[S[end]] <= needToFind[S[end]]) {
                count++;
            }
            
            if(count == T.size()) {
                while(needToFind[S[start]] == 0 ||
                    hasFound[S[start]] > needToFind[S[start]]) {
                    if(hasFound[S[start]] > needToFind[S[start]])
                        hasFound[S[start]]--;
                    start++;
                }
                
                if(end - start + 1 < minWindowSize) {
                    minWindowSize = end - start + 1;
                    window = S.substr(start, minWindowSize);
                }
            }
        }
        
        return window;
    }
};

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