Runhe Tian Coding Practice

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.

Thoughts:
For each element in the array, we want to track the subarray with the largest sum ending here. And the largest of those largest sums is the result we need. So how do we track the largest sum ending at a particular position? We can keep adding up positive numbers. We can also add negative numbers as long as the sum would be less than 0. If it’s smaller than 0, we need to reset from this position by starting the sum from 0. In the above example, the largest sums ending at each position are [-2,1,-3,4,3,5,6,1,5]. Hence the largest sum is 6.

code (Java):

public class Solution {
    public int maxSubArray(int[] A) {
        int maxSumSoFar = Integer.MIN_VALUE;
        int maxSumEndingHere = 0;
        
        for(int num : A) {
            maxSumEndingHere = Math.max(maxSumEndingHere + num, num);
            maxSumSoFar = Math.max(maxSumSoFar, maxSumEndingHere);
        }
        
        return maxSumSoFar;
    }
}

Code (C++):
class Solution {
public:
    int maxSubArray(int A[], int n) {
        int maxSumSoFar = INT_MIN;
        int maxSumEndingHere = 0;
        for(int i = 0; i < n; ++i) {
            maxSumEndingHere = max(maxSumEndingHere+A[i], A[i]);
            maxSumSoFar = max(maxSumSoFar, maxSumEndingHere);
        }
        return maxSumSoFar;
    }
};

	

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

Thoughts:
If we think the matrix as a number of rows and each row is a histogram then we can reduce the problem to the Largest Rectangle in Histogram problem. So how can we view each row as histogram? Consider the following binary matrix:

11000
11000
00111
00111
00111

The largest rectangle should be 3*3, apparently. What makes up a rectangle? There are 3 columns there, if you like, and each of them contains 3 consecutive ones. So if for each row, we count how many consecutive ones we have above us, we can construct 5 histograms:
11000
22000
00111
00222
00333

Then we can compute the largest rectangle for each row and we will find out that the last row contains a maximal rectangle with area of 5 in its histogram.
Code (Java):
import java.util.Stack;
public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length == 0) 
            return 0;
        int[][] auxillary = new int[matrix.length][matrix[0].length];
        for(int i = 0; i < matrix.length; ++i) {
            for(int j = 0; j < matrix[i].length; ++j) {
                auxillary[i][j] = Character.getNumericValue(matrix[i][j]);
            }
        }
        for(int i = 1; i < auxillary.length; ++i) {
            for(int j = 0; j < auxillary[i].length; ++j) {
                if(auxillary[i][j] == 1)
                    auxillary[i][j] = auxillary[i-1][j] + 1;
            }
        }
        
        int max = 0;
        for(int i = 0; i < auxillary.length; ++i) {
            max = Math.max(max, largestRectangleArea(auxillary[i]));
        }
        return max;
    }
    
    private int largestRectangleArea(int[] height) {
        Stack<Integer> stack = 
            new Stack<Integer>();
        int max = 0;
        int i = 0;
        while(i < height.length) {
            if(stack.isEmpty() || 
                height[i] >= stack.peek()) {
                stack.push(height[i]);
                i++;
            }
            else {
                int count = 0;
                while(!stack.isEmpty() && 
                    stack.peek() > height[i]) {
                    count++;
                    int top = stack.pop();
                    max = Math.max(max, top * count);
                }
                for(int j = 0; j < count + 1; ++j) {
                    stack.push(height[i]);
                }
                i++;
            }
        }
        
        int count = 0;
        while(!stack.isEmpty()) {
            count++;
            max = Math.max(max, stack.pop() * count);
        }
        return max;
    }
}

Code (C++):
class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        if(matrix.size() == 0) 
            return 0;
        vector<vector<int> > auxillary;
        for(int i = 0; i < matrix.size(); ++i) {
            vector<int> temp;
            for(int j = 0; j < matrix[i].size(); ++j) {
                temp.push_back(matrix[i][j] - '0');
            }
            auxillary.push_back(temp);
        }
        for(int i = 1; i < auxillary.size(); ++i) {
            for(int j = 0; j < auxillary[i].size(); ++j) {
                if(auxillary[i][j] == 1)
                    auxillary[i][j] = auxillary[i-1][j] + 1;
            }
        }
        
        int maxArea = 0;
        for(int i = 0; i < auxillary.size(); ++i) {
            maxArea = max(maxArea, largestRectangleArea(auxillary[i]));
        }
        return maxArea;
    }
    
private:
    int largestRectangleArea(vector<int> &height) {
        stack<int> stack_;
        int maxArea = 0;
        int i = 0;
        while(i < height.size()) {
            if(stack_.empty() || 
                height[i] >= stack_.top()) {
                stack_.push(height[i]);
                i++;
            }
            else {
                int count = 0;
                while(!stack_.empty() && 
                    stack_.top() > height[i]) {
                    count++;
                    int top = stack_.top();
                    stack_.pop();
                    maxArea = max(maxArea, top * count);
                }
                for(int j = 0; j < count + 1; ++j) {
                    stack_.push(height[i]);
                }
                i++;
            }
        }
        
        int count = 0;
        while(!stack_.empty()) {
            count++;
            maxArea = max(maxArea, stack_.top() * count);
            stack_.pop();
        }
        return maxArea;
    }
};


		
	
	

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
For “(()”, the longest valid parentheses substring is “()”, which has length = 2.
Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

Thoughts:
The idea is to use a stack to store all the index of ‘(‘ we encountered. We maintain a variable “startIndex” to store the earliest starting position of a ‘(‘, this is used to determine the start position (hence the length) of a possible solution. If we see a ‘)’, we can pop out a ‘(‘ to construct a parenthesis. Hence we have a candidate. After doing that, if the stack is empty, we can fetch the earliest starting position to calculate the length of this solution (this scenario occurs when we see the last index of “(()())”). If the stack is not empty yet, we can calculate the length by comparing the current index with the index of the top element in the stack (this scenario happens when we process the last index of “(()”).
Code (Java):

import java.util.Stack;
public class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        int len = 0;
        int maxLen = 0;
        int startIndex = s.length();
        for(int i = 0; i < s.length(); ++i) {
            if(s.charAt(i) == '(') {
                stack.push(i);
                continue;
            }
            
            if(stack.isEmpty()) {
                startIndex = s.length();
            } else {
                startIndex = Math.min(stack.peek(), startIndex);
                stack.pop();
                
                if(stack.isEmpty()) {
                    len = i - startIndex + 1;
                } else {
                    len = i - stack.peek();
                }
                maxLen = Math.max(maxLen, len);
            }
        }
        return maxLen;
    }
}

Code (C++):
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> Stack;
        int len = 0;
        int maxLen = 0;
        int startIndex = s.size();
        for(int i = 0; i < s.size(); ++i) {
            if(s[i] == '(') {
                Stack.push(i);
                continue;
            }
            
            if(Stack.empty()) {
                startIndex = s.size();
            } else {
                startIndex = min(Stack.top(), startIndex);
                Stack.pop();
                
                if(Stack.empty()) {
                    len = i - startIndex + 1;
                } else {
                    len = i - Stack.top();
                }
                maxLen = max(maxLen, len);
            }
        }
        return maxLen;
    }
};

	

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Thoughts:
We use the similar approach as in Jump Game with the exception that table[i] now stores the minimum step it takes from position i to the last index. We update the table from end to start. At each position i, we look at every possible position j that one can reach from i, and then pick the least step it takes from j to the last index (i.e., table[j]). We then store table[j] + 1 in table[i]. When A[i] == 0, i.e., we cannot go anywhere from position i, we make table[i] = INT_MAX. Also when we cannot get to any intermediate position that will lead us to the last index, we make table[i] = INT_MAX.

Code (Java):

public class Solution {
    public int jump(int[] A) {
        int n = A.length;
        int[] table = new int[n];
        table[n-1] = 0;
        for(int start = n - 2; start >= 0; --start) {
            if(A[start] == 0) {
                table[start] = Integer.MAX_VALUE;
            } else if(n - 1 - start <= A[start]) {
                table[start] = 1;
            } else {
                int min = Integer.MAX_VALUE;
                for(int j = start + 1; j < n && 
                    j - start <= A[start]; ++j) {
                    if(table[j] < min) {
                        min = table[j];
                    }
                }
                table[start] = min == Integer.MAX_VALUE ? 
                                min : min + 1;
            }
        }
        return table[0];   
    }
}

Code (C++):
class Solution {
public:
    int jump(int A[], int n) {
        int *table = new int[n];
        table[n-1] = 0;
        
        for (int i = n-2; i >=0; i--) {
            if (A[i] == 0)
                table[i] = INT_MAX;
            else if (A[i] >= n - i - 1)
                table[i] = 1;
            else {
                int min = INT_MAX;
                for (int j = i+1; j < n && 
                    j <= A[i] + i; j++) {
                    if (min > table[j])
                        min = table[j];
                }     
                if (min != INT_MAX)
                    table[i] = min + 1;
                else
                    table[i] = min;
            }
        }
        return table[0];  
    }
};