Leetcode–Longest Valid Parentheses

The Problem:

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.

Notes:

  1. Wrong way: I was thinking of using stack, and each time find a pair then pop that pair. Then realized that the stack will only contain ‘(‘, since each time a ‘)’ come, instead of pushing it, a ‘(‘ will be popped. So I switched to only use a counter to record the number of ‘(‘. But consider this case: “(()()” and “()(()”, although they follow the same number of ‘(‘ and ‘)’, we need to record the location of unmatched ‘(‘ !
  2. Solution I: use a stack of integer to record the indices of unpaired ones. So each ‘(‘ will be pushed into stack, and for each ‘)’, if no ‘(‘ can match (stack empty, or stack top is a ‘)’ ), then also push into stack. otherwise pop a ‘(‘. In this fashion only peek the top can know the last unpaired index, by subtracting it we can get the valid length.
  3. Solution II: a less straight forward DP solution I found online. Use an array vlen to record the valid length of parentheses ending with s[i]. For each ‘(‘, it will have vlen[i] = 0; for each ‘)’, check the index of precous ‘free’ char, which is at j=(i-1-vlen[i-1]), see if it’s a ‘(‘, if true then can be paired, and vlen[i]=vlen[i-1]+2, and do NOT forget to also merge with vlen[j-1] !

Java Solution I:

public class Solution {
    public int longestValidParentheses(String s) {
        // use a stack to record unpaired indices
        Stack<Integer> st = new Stack<Integer>();
        int valid = 0;
        int max = 0;
        for(int i = 0; i < s.length(); i++){
             // 1. it's a '(' ; 2. it's a ')' but no '(' left to match
            if(s.charAt(i)=='(' || st.empty()|| s.charAt(st.peek())==')'){
                st.push(i);
            }
            else{
                st.pop();
                if(st.empty()){
                    // note here is i+1, not i !
                    valid = i+1;
                    max = valid;
                }
                else{
                    valid = i-st.peek();
                    max = Math.max(max, valid);
                }
            }            
        }
        return max;        
    }
}

Java Solution II:

public class Solution {
    public int longestValidParentheses(String s) {
        if(s.length()==0)return 0;
        //valid length ending at i
        int[] vlen = new int[s.length()];
        vlen[0]= 0;
        int max = 0;
        for(int i = 1; i < s.length(); i++){
            if(s.charAt(i)=='('){
            // valid parenthese cannot end with '('
                vlen[i] = 0;
            }
            else{
                int j = i-1-vlen[i-1];
                //can match with a previous '('
                if(j>=0 && s.charAt(j)=='('){
                    vlen[i] = vlen[i-1]+2;
                    // connect with the length before j
                    if(j-1>=0){
                        vlen[i] += vlen[j-1];
                    }
                }                
            }
            max = Math.max(max, vlen[i]);
        }
        return max;
    }
}

Leetcode–Best Time to Buy and Sell Stock III

The Problem:

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Notes:

  1. I used a brutal force way to call maxProfit (similar function as in Best Time to Buy and Sell Stock II) to get each of max profit of two halves. Then I realized actually if we store the max profit as array can avoid the duplicate recursive calls .
  2. As for the second half, similarly, go through prices backwards, to get an array of max profit of buying stock at day i and sell afterwards.

Java Solution

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length<=1)
            return 0;
        //for first half
        int minP = prices[0];
        int maxP = prices[prices.length-1];
        int[] maxBefore = new int[prices.length];
        int[] maxAfter = new int[prices.length];

        int maxPro = 0;
        for(int i = 1; i<prices.length; i++){
            maxBefore[i] = Math.max(maxPro, prices[i]-minP);
            maxPro = maxBefore[i];
            minP = Math.min(minP, prices[i]);
        }
        maxPro = 0;
        for(int i = prices.length-2; i>=0; i--){
            maxAfter[i] = Math.max(maxPro, maxP - prices[i]);
            maxPro = maxAfter[i];
            maxP = Math.max(maxP, prices[i]);
        }
        // initialize using the single transaction case
        int profit = maxBefore[prices.length-1];
        // i is the beginning index of second transaction
        for(int i = 1; i < prices.length; i++){
            profit = Math.max(profit, maxBefore[i-1]+maxAfter[i]);
        }
        return profit;
    }   
}

Leetcode–Best Time to Buy and Sell Stock

The Problem:

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Notes:

  1. Keep track of max profit if sell at day i, and a min price to buy before day i.

Java Solution

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length <=1)
            return 0;
        int maxProfit = 0;
        int minP = prices[0];
        for(int i = 1; i < prices.length; i++){
            maxProfit = Math.max(maxProfit, prices[i]-minP);
            minP = Math.min(minP, prices[i]);
        }
        return maxProfit;
    }
}

Leetcode–Best Time to Buy and Sell Stock II

The Problem:

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Notes:

  1. Observe a simple rule that each time detects a drop in price, should sell it before drop, and then buy at the drop. So use greedy. Remember to sell in the last day even no drop.

Java Solution

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length<=1) 
            return 0;
        int profit = 0;
        int buy = prices[0];
        for(int i = 1; i < prices.length; i++){
            // sell only prices go down
            if(prices[i] < prices[i-1]){
                profit += prices[i-1]-buy;
                buy = prices[i];
            }
            // sell in last day even not go down
            else if(i==prices.length-1){
                profit += prices[i]-buy;
            }
        }
        return profit;
    }
}

Leetcode–Triangle

The Problem:

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Notes:

  1. The main idea is traversing the list backwards, which means start from bottom of the triangle. For each level up, store the result of min path to reach this node from lower level.
  2. It is a DP problem, but the previous results for one level can be updated in place.

Java Solution

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size()==1)
            return triangle.get(0).get(0);
        int rows = triangle.size();
        int sum[] = new int[triangle.get(rows-1).size()];
        for(int i = 0; i < triangle.get(rows-1).size(); i++ ){
            sum[i] = triangle.get(rows-1).get(i);
        }
        
        for(int i = rows-2; i>= 0; i--){
            for(int j = 0; j <  triangle.get(i).size(); j++ ){
                sum[j] = triangle.get(i).get(j) + Math.min(sum[j], sum[j +1]);
            }
        }
        return sum[0];
    }
}

Leetcode–Regular Expression Matching

The Problem:

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Notes:

  1. Note that for each pair of “?*” in p, there is a possible match of skipping this pair in p.
  2. Design the branch condition as:
    1. p[1] !=’*’, which means if p[0] not match then can directly return false;
    2. otherwise, need to consider the ‘?*’ skipping cases:
      1. directly skip by going to p[2]
      2. traversing s while s[id] match p[0], and for each match also consider a skip to p[2]

Java Solution

public class Solution {
    public boolean isMatch(String s, String p) {
        if(s.length()==0 &&  p.length()==0)
            return true;
        if( p.length()==0) 
            return false;
        // check if not have a P:"x*" condition, then the first char must match      
        if(p.length()==1 ||  p.charAt(1)!='*'){
            if(s.length() >0 && (p.charAt(0)=='.' || s.charAt(0) == p.charAt(0))){
               return isMatch(s.substring(1),p.substring(1));
            }
            else
                return false;
        }
        else{
        // for condition: P:"x*", need to consider skipping each pair of "x*"
            //directly skip
            if(isMatch(s, p.substring(2)))
                return true;
            //for each match of s[id] and p:x, try a skip 
            int id = 0;
            while(id < s.length()){
                if(s.charAt(id)==p.charAt(0) || p.charAt(0)=='.'){
                    if(isMatch(s.substring(id+1), p.substring(2)))
                        return true;
                }
                else{
                    break;
                }
                id++;       
            }
            return false;
        }
    }
}

Leetcode–Maximum Product Subarray

The Problem:

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Notes:

  1. Keep track of a minAt and a maxAt of product ending with each index. The trick is to record minAt, it covers the case that previously has a negative number (we discarded in maxAt), but later have another negative number which together may result in a bigger product.
  2. minAt and maxAt should be updated after all computed, so use a temp variable to hold first.

Java Solution

public class Solution {
    public int maxProduct(int[] A) {
        int maxAt = A[0];
        int minAt = A[0];
        int max = A[0];
        int tempMax, tempMin;
        for(int i = 1; i < A.length; i++){
            tempMax = Math.max(Math.max(maxAt * A[i], minAt * A[i]), A[i]);
            tempMin = Math.min(Math.min(maxAt * A[i], minAt * A[i]), A[i]);
            
            maxAt = tempMax;
            minAt = tempMin;
            max = Math.max(maxAt, max);
            
        }
        return max;
    }
}