[LeetCode] Different ways to add parentheses

Problem statement (link):

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +,- and *.

Example 1

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

Analysis:

This problem statement is a bit misleading (in a good way) so that my first attempt is to construct the different parenthesesed strings, and compute each string individually. This approach is exponential in both space and time complexity.

Now, the problems that ask for "all possible results" is usually solved using DFS approach. Don't get confused about the * operator as it would be treated equivalently as the + and - because of the parentheses. In the end, all the question asks is to find all possible combinations using parentheses.

With that, we could construct the solutions bottom-up. It's exactly the same as Unique Binary Tree II problem if we think each node as an arithmetic string. For instance,  in Example 2, we have the following ways of constructing the solutions:

Recursion Trees:
1)
                                        2 * 3 - 4 * 5
                                      /                     \
                                   2                   3 - 4 * 5
                                                       /             \
                                                     3             4 * 5
                                                                     /     \
                                                                    4      5
2)
                                        2 * 3 - 4 * 5
                                      /                     \
                                 2 * 3                  4 * 5
                                /       \                 /        \
                              2          3            4           5
3) ...
4) ...
5) ...

You get the idea.

Only extra work we need to do is instead of connecting the nodes, we compute each node (arithmetic string). The time complexity is still exponential but the code looks very clean.

Code:

public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<>();
        for (int i=0; i<input.length(); i++) {
            char c = input.charAt(i);
            if (c=='+' || c=='-' || c=='*') {
                for (Integer int1: diffWaysToCompute(input.substring(0, i))) {
                    for (Integer int2: diffWaysToCompute(input.substring(i+1))) { // i+1: to skip the operator char
                        res.add(c=='+' ? int1+int2 : c=='-' ? int1-int2 : int1*int2);
                    }
                }
            }
        }

        if (res.size()==0)
            res.add(Integer.parseInt(input));
        return res;
    }
}

[LeetCode] Pow(x, n)

Problem Statement (link):
Implement pow(x, n).

Analysis:
The naive approach is simply to multiply n x's together and get the result. The time complexity is O(n).

Thinking of a better way, when we do linear search with O(n), we optimize the time complexity to O(log(n)) using binary search. In this problem, we can do similar as well.

The following is an example for pow(3, 10), the 'res' is the result that we need to return. We initialize res = 1 so that res = res * x ^ n.
The strategy is to get x as large as possible by squaring it (n>>1 at the same time) so that when we multiple res and x, we have less operations. When n is odd and we couldn't do that, we change res = res*n, so that n = n-1 and n is even again.

Step	res	x	n
1	1	3	10
2	1	9	5
3	9	9	4
4	9	81	2
5	9	6561	1

Code:

public class Solution {
    public double myPow(double x, int n) {
        if (n==0) return 1;
        if (x==0 || x==1) return x;
        if (n<0) {
            x = 1/x;
            n = -n;
        }
        double res = 1;
        while (n>0) {
            if (n%2==1) {
                res *= x;
                n--;
            } else {
                x *= x;
                n >>= 1;
            }
        }
        return res;
    }
}

Further, we could optimize the above if-else statement inside the while loop such that we are able to skip one operations - from Step 2->Step 4. The code looks like following

public class Solution {
    public double myPow(double x, int n) {
        if (n==0) return 1;
        if (x==0 || x==1) return x;
        if (n<0) {
            x = 1/x;
            n = -n;
        }
        double res = 1;
        while (n>0) {
            if (n%2==1) {
                res *= x;
            }
            x *= x;
            n >>= 1;
        }
        return res;
    }
}

Java Autoboxing and unboxing

Autoboxing: Java converts primitive types to its wrapper class when object is expected;

Unboxing: Java converts the object to its primitive type value when primitive type is expected.

Details here.

Primitive type	Wrapper class
boolean	Boolean
byte	Byte
char	Character
float	Float
int	Integer
long	Long
short	Short
double	Double

[C++] Data structures and their common operators

	vector	stack	queue	Deque (Double ended queue)	Priority_queue
Access	x=v.front() x=v.back()	x=s.top()	x=q.front()	x=dq.front() x=dq.back()	x=pq.top()
Add	v.insert(itr, x) v.push_back(x) v.emplace(itr, x) v.emplace_back(x)	s.emplace(x) s.push(x)	q.emplace(x) q.push(x)	dq.emplace(itr, x) dq.emplace_back(x) dq.emplace_front(x) dq.push_back(x) dq.push_front(x) dq.insert(itr,x)	pq.emplace(x) pq.push(x)
Remove	v.clear() v.erase(itr) v.pop_back()	s.pop()	q.pop()	dq.clear() dq.erase(itr) dq.pop_back() dq.pop_front()	pq.pop()
Check empty	v.empty()	s.empty()	q.empty()	dq.empty()	pq.empty()
Check size	x=v.size()	x=s.size()	x=q.size()	dq.size()	pq.size()

Vector vs. Deque:

Both vector and deque provide a very similar interface, but internally they work in quite different ways: vector uses a single array that needs occasionally re-allocation for growth; deque has its elements scattered in different chunk of storage, with the container keeping the necessary information for direct accesses to any element in constant time - through iterators.

[LeetCode] Maximum Subarray

Problem Statement (link):

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.

Analysis:
Suppose we scan from left to right, each element could either be counted in the max-sum subarray, or not. If we use an array to store this information, we probably could solve the problem in O(n) time.

Thus, the idea is to use DP to solve the problem. Specifically, the DP array stores the maximum sum we have so far if we count the current element in. In addition, we use an integer to store the maximum sum we have so far.

Code:

class Solution {
public:
    int maxSubArray(int A[], int n) {
        if (n==0) return 0;
        int maxSum=INT_MIN; // max sum so far
        vector<int> dp(n+1);  // dp[i+1]: the maxSum of subarray which ends with A[i];
        dp[0]=0;
        for (int i=0; i<n; i++) {
            if (dp[i]<0) dp[i+1]=A[i];
            else dp[i+1]=dp[i]+A[i];
            maxSum=max(maxSum, dp[i+1]);
        }
        return maxSum;
    }
};

[LeetCode] Generate Parentheses

Problem Statement (link):

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:
"((()))", "(()())", "(())()", "()(())", "()()()"

Analysis:
The problem asks for all combinations, this usually indicates it's a DFS problem.

In the recursion function, if we've used up all left and right parentheses, we push the formed string into result vector. Otherwise, we can add either left parentheses or right parentheses. The code for this problem is shown in Sol 1 below.

The extended version of this problem is that instead of only having parentheses, we are given n1 parentheses pairs, n2 bracket pairs, and n3 curly parentheses, and we are asked for the same thing - all combinations.

The idea is pretty similar to the simple version. The only difference is that we can do one of the following:
1) add left parentheses '(';
2) add left bracket '[';
3) add left curly parentheses '{';
4) add the right part, depending on the left situation, we choose either ')', ']', or '}'.

The code is shown in Sol 2 below.

Code:
Sol 1:

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        if (n<1) return res;
        dfs(res, "", "", n);
        return res;
    }
    void dfs(vector<string> &res, string left, string tmp, int n) {
        if (left.size()==0 && n==0) {
            res.push_back(tmp);
            return;
        }
        if (n>0) {
            dfs(res, "("+left, tmp+"(", n-1);
        }
        if (left.size()>0) {
            dfs(res, left.substr(1), tmp+")", n);
        }
    }
};

Sol 2:

string rightPart(string left) {
    if (left=="(") return ")";
    else if (left=="[") return "]";
    else return "}";
}

void dfsParen(vector<string> &res, string leftStack, string str, int n1, int n2, int n3) {
    if (leftStack.empty() && n1==0 && n2==0 && n3==0) {
        res.push_back(str);
        return;
    }

    // add left parentheses
    if (n1>0) {
        dfsParen(res, "("+leftStack, str+"(", n1-1, n2, n3);
    }
    if (n2>0) {
        dfsParen(res, "["+leftStack, str+"[", n1, n2-1, n3);
    }
    if (n3>0) {
        dfsParen(res, "{"+leftStack, str+"{", n1, n2, n3-1);
    }

    // add right parentheses
    if (!leftStack.empty()) {
        dfsParen(res, leftStack.substr(1), str+rightPart(leftStack.substr(0,1)), n1, n2, n3);
    }
}

vector<string> getParen(int n1, int n2, int n3) {
    vector<string> res;
    if (n1==0 && n2==0 && n3==0) return res;
    string leftStack;
    string str="";
    dfsParen(res, leftStack, str, n1, n2, n3);
    return res;
}

[LeetCode] Container with Most Water

Problem Statement (link):

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.

Analysis:
The naive O(n^2) brute force is apparently not optimal.

An O(n) algorithm goes like this:
- Start from the very beginning and end of the vector, we calculate the volume hold by these two boards;
- Compare the height of current boards, advance the shorter board;

To justify this algorithm, think about the following case:
Suppose we are currently at left index i, right index j. If height i is smaller height j, then with any other height jj (i<jj<j), the area(i, jj) < area(i, j). The reason is that the container area is determined by the shorter height of the two boards, i.e., board i. In other words, the maximum area that determined by board i is already found.

Code:

class Solution {
public:
    int maxArea(vector<int> &height) {
        int left=0, right=height.size()-1;
        int vol=min(height[left], height[right]) * (right-left);
        while (left<right) {
            if (height[left]<height[right]) left++;
            else right--;
            vol=max(vol, min(height[left], height[right]) * (right-left));
        }
        return vol;
    }
};