Leetcode: Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

Understand the problem:
1. If num, push into num stack.
2. If operator: 
    -- If the op stack is empty, push the operator into the stack. 
    -- If the op has higher precedence, e.g. * or /, check the top of the op stack. 
        -- If the top operator on the op stack is a "(", push and move on. 
        -- If the top operator on the op stack has lowe precedence as well, push into the stack. 
        -- If the top operator on the op stack has the same precedence, consume one operation, and then push the op into the op stack. 
    -- If the op has lower percedence, e.g. + or -, check the top of the op stack as well. 
        -- If the top of the op stack is a left parthesis, push the op and move on
        -- Else, Pop one operator and two operands from the two stacks, resp. and push the result back. 
    -- If the op is a left parthesis, push to the op stack and move on. 

    -- If the op is a right parthesis, pop and compuate until we reach a left parthesis.   

Code (Java):

class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        s = s.trim();
        s = s.replaceAll("[ ]+", "");
        
        Stack<Integer> numStack = new Stack<>();
        Stack<Character> opStack = new Stack<>();
        
        int ans = 0;
        
        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    int digit = Character.getNumericValue(s.charAt(i));
                    num = num * 10 + digit;
                    i++;
                }
                numStack.push(num);
            } else {
                if (opStack.isEmpty() || c == '(') {
                    opStack.push(c);
                    i++;
                } else if (c == '*' || c == '/') {
                    if (opStack.peek() == '*' || opStack.peek() == '/') {
                        compute(numStack, opStack);
                    } else {
                        opStack.push(c);
                        i++;
                    }
                } else if (c == '+' || c == '-') {
                    compute(numStack, opStack);
                } else if (c == ')') {
                    while (!opStack.isEmpty() && opStack.peek() != '(') {
                        compute(numStack, opStack);
                    }
                    opStack.pop();
                    i++;
                }
            }
        }
        
        while (!opStack.isEmpty()) {
            compute(numStack, opStack);
        }
        
        return numStack.pop();
    }
    
    private void compute(Stack<Integer> numStack, Stack<Character> opStack) {
        int num2 = numStack.pop();
        int num1 = numStack.pop();
        
        char op = opStack.pop();
        
        int ans = 0;
        
        switch (op) {
            case '+': 
                ans = num1 + num2;
                break;
            case '-' :
                ans = num1 - num2;
                break;
            case '*' :
                ans = num1 * num2;
                break;
            case '/': 
                ans = num1 / num2;
                break;
        }
        
        numStack.push(ans);
    }
}

Summary:
The problem looks complicated to implement, actually could be memorized in a template way. 
If the token is a number, then push it to the num stack. 
If the token is a operator, there are 5 cases to consider:
1. If the opStack is empty
  -- push into opStack
2. If the token is + or -
  -- Check the top of the opStack. 
     -- If the top is '(', then push the token into opStack.
     -- Else (which means has higher or equal precedence), consume the stack by doing one computation. 
3. If the token is * or /
     -- If the top is '(', push the token into opStack
     -- Else if top has lower precedence ( + or -), push the token into opStack.
     -- Else if the top has equal precedence (* or /), consume the stack by doing one computation. 
4. If the token is (
    -- Push into opStack
5. If the token is )
   -- Doing computations until we see the '(' in the opStack. 


There is another corner case need to be very careful is:
If the input String has only one number, e.g. (1), 1, 1*. For OA it is still valid. So the trick to handle this edge case is in the computation method, before we pop two numbers from the numStack, we check if the size of the numStack. If less than 2, we know that this case happens. Then we only need to do is pop out the opStack until it is empty. Then the result is the only number in the numStack. 

Leetcode: Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

Understand the problem:
A histogram problem very similar to container with most water and trapping rain water problems. So the first thing is to come out the area of the histograms, which could be calculated as area = (j - i + 1) * min(A[i], A[j]). Thus the most straight-forward way is to try each pair of i and j, and get its area, as well as its largest area. 

A wrong Solution:
As described above, the most straight-forward way is to iterate through all possible i and j, and calculate the area. So the time complexity is O(n^2) for this solution. 

Code (Java):

public class Solution {
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        
        int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = 0; j < height.length; j++) {
                int area = (j - i + 1) * Math.min(height[i], height[j]);
                if (area > maxArea) {
                    maxArea = area;
                }
            }
        }
        
        return maxArea;
    }
}

The height = [2,1,5,6,2,3], generated the result of 12, instead of 10. The reason is because the area calculation equation was wrong. For a pair of i, j, its area is not determined by the min (A[i], A[j])., but minimum A[k], i <= i <= j.  

The correct Solution:

public class Solution {
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        
        int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
            int minV = height[i];
            for (int j = i; j < height.length; j++) {
              minV = Math.min(minV, height[j]);  
              int area = (j - i + 1) * minV;
                if (area > maxArea) {
                    maxArea = area;
                }
            }
        }
        
        return maxArea;
    }
}

A better Solution:

public class Solution {
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        
        if (height.length == 1) {
            return height[0];
        }
        
        Stack<Integer> stack = new Stack<Integer>();
        int[] copy = new int[height.length + 1];
        copy = Arrays.copyOf(height, height.length + 1);
        
        int maxArea = 0;
        int i = 0;
        
        while (i < copy.length) {
            if (stack.isEmpty() || copy[i] > copy[stack.peek()]) {
                stack.push(i);
                i++;
            } else {
                int index = stack.pop();
                int localArea = copy[index] * (stack.isEmpty() ? i : i - stack.peek() - 1);
                maxArea = Math.max(maxArea, localArea);
            }
        }
        
        return maxArea;
    }
}