Happy Coding: June 2015

Saturday, June 27, 2015

[LeetCode] Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

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

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Solution: Since here we do not have parentheses, a stack is not necessary.

One can directly make one pass to derive the result, by maintaining preMulDiv, preAddSub, preNum, and curNum.

The logic:

Each time we see '+' or '-', we know '*' or '/' before it must have been processed. If we have unprocessed '+' or '-' before, process the old one.

Each time we see a number, if we have unprocessed '*' or '/', process it immediately. Otherwise, update preNum and curNum.

In the end, we need to check whether we need to process '+' or '-' once.
Remarks. In order to deal with the special test case "0-2147483648", I added a little more code. Did not aim to take care of all large number operations.

public class Solution {
    private boolean isOverflow(String s) {
        return s.equals("2147483648");
    }

    private int evalOp(int a, int b, char op) {
        switch (op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            default: return a / b;
        }
    }
    
    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Character preAddSub = null;
        Character preMulDiv = null;
        Integer preNum = null;
        Integer curNum = null;
        int i = 0;
        while (i < s.length()) {
            if (Character.isWhitespace(s.charAt(i))) {
                i++;
            } else if (Character.isDigit(s.charAt(i))) {
                int j = i + 1;
                while (
                    j < s.length() && 
                    Character.isDigit(s.charAt(j))
                ) {
                    j++;    
                }
                if (isOverflow(s.substring(i, j))) {
                    return Integer.MIN_VALUE;
                }
                int nextNum = Integer.valueOf(s.substring(i, j));
                if (preMulDiv != null) {
                    curNum = evalOp(curNum, nextNum, preMulDiv);
                    preMulDiv = null;
                } else {
                    preNum = curNum;
                    curNum = nextNum;
                }
                i = j;
            } else if (s.charAt(i) == '+' || s.charAt(i) == '-') {
                if (preAddSub != null) {
                    curNum = evalOp(preNum, curNum, preAddSub);
                } 
                preAddSub = s.charAt(i);
                i++;
            } else {
                preMulDiv = s.charAt(i);
                i++;
            }
        }
        if (preAddSub != null) {
            curNum = evalOp(preNum, curNum, preAddSub);
        } 
        return curNum;
    }
}

Friday, June 26, 2015

[LeetCode] Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
Solution 1: HashSet. This requires two iterations.
Sadly, Time Limit Exceeded.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        HashSet<Character> set = new HashSet<Character>();
        int i = 0; 
        int j = 0;
        int maxLen = 0;
        while (j < s.length()) {
            if (set.contains(s.charAt(j))) {
                while (set.contains(s.charAt(j))) {
                    set.remove(s.charAt(i));
                    i++;
                }
            } 
            maxLen = Math.max(maxLen, j - i + 1);
            set.add(s.charAt(j));
            j++;
        }
        return maxLen;
    }
}

Solution 2: HashMap. Now this is only one iteration.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        int i = 0; 
        int j = 0;
        int maxLen = 0;
        while (j < s.length()) {
            if (
                map.containsKey(s.charAt(j)) && 
                map.get(s.charAt(j)) >= i
            ) {
                i = map.get(s.charAt(j)) + 1;
            } 
            maxLen = Math.max(maxLen, j - i + 1);
            map.put(s.charAt(j), j); 
            j++;
        }
        return maxLen;
    }
}

[LeetCode] First Missing Positive

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

Solution:

O(n) running time, O(n) extra space.

public class Solution {
    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 1;
        }
        HashSet<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            set.add(num);
        }
        int num = 1;
        while (set.contains(num)) { 
            num++;
        }
        return num;
    }
}

O(n) running time, O(1) extra space.
This utilizes a smart trick by modifying the array to act as a HashSet. See a detailed discussion here.

public class Solution {
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
    private int partition(int[] nums) {
        int storeIdx = 0;
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] > 0) {
                swap(nums, storeIdx, j);
                storeIdx++;
            }
        }
        return storeIdx;
    }
    
    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 1;
        }
        int numPos = partition(nums);
        for (int i = 0; i < numPos; i++) {
            if (Math.abs(nums[i]) - 1 < numPos) {
                if (nums[Math.abs(nums[i]) - 1] > 0) {
                    nums[Math.abs(nums[i]) - 1] *= -1;
                }
            }
        }
        for (int i = 0; i < numPos; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return numPos + 1;
    }
}

Friday, June 12, 2015

[LeetCode] Decode Ways

Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Solution: Dynamic Programming.

Note that if a message starts with 0, there is no feasible way to decode it.

public class Solution {
    private int[] ways;
    
    private int numDecodings(String s, int i) {
        if (i >= s.length()) {
            return 1;
        }
        if (s.charAt(i) == '0') {
            return 0;
        }
        if (ways[i] > -1) {
            return ways[i];
        }
        ways[i] = numDecodings(s, i + 1);
        if (
            i + 2 <= s.length() &&
            Integer.valueOf(s.substring(i, i + 2)) <= 26
        ) {
            ways[i] += numDecodings(s, i + 2);
        }
        return ways[i];
    }
    
    public int numDecodings(String s) {
        if (s.length() == 0) {
            return 0;
        }
        ways = new int[s.length()];
        Arrays.fill(ways, -1);
        return numDecodings(s, 0);
    }
}

[LeetCode] Basic Calculator

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.

Solution: Stack.

If we encounter +, - or (, we push them in the stack.

If we encounter ), we know the expression inside () has been evaluated. Pop the result for that expression, and pop (. And perform one operation if necessary.

if we encounter a number, perform one operation if necessary.

Remarks. One may solve this recursively by working from the end of the string.

public class Solution {
    private boolean isDigit(char ch) {
        return ch >= '0' && ch <= '9';
    }
    
    private void pushOrAddOrMinus(
        String str, 
        Stack<String> stack
    ) {
        if (stack.empty() || stack.peek().equals("(")) {
            stack.push(str);
            return;
        }
        int val = Integer.valueOf(str);
        if (stack.peek().equals("+")) {
            stack.pop();
            int val_o = Integer.valueOf(stack.pop());
            stack.push(String.valueOf(val_o + val));
        } else if (stack.peek().equals("-")) {
            stack.pop();
            int val_o = Integer.valueOf(stack.pop());
            stack.push(String.valueOf(val_o - val));
        }
    }
    
    public int calculate(String s) {
        if (s.length() == 0) {
            return 0;
        }
        Stack<String> stack = new Stack<String>();
        int i = 0;
        while (i < s.length()) {
            if (s.charAt(i) == '+') {
                stack.push("+");
                i++;
            } else if (s.charAt(i) == '-') {
                stack.push("-");
                i++;
            } else if (s.charAt(i) == '(') {
                stack.push("(");
                i++;
            } else if (s.charAt(i) == ')') {
                String str = stack.pop();
                stack.pop();
                i++;
                pushOrAddOrMinus(str, stack);
            } else if (s.charAt(i) == ' ') {
                i++;  
            } else {
                int j = i + 1;
                while (j < s.length() && isDigit(s.charAt(j))) {
                    j++;
                }
                String str = s.substring(i, j);
                i = j;
                pushOrAddOrMinus(str, stack);
            }
        }
        return Integer.valueOf(stack.pop());
    }
}

Tuesday, June 9, 2015

[LeetCode] Generate Parentheses

Generate Parentheses

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

Solution: Backtracking.

public class Solution {
    private ArrayList<String> result;
    private char[] chars;
    
    private void genParen(int leftRem, int rightRem, int i) {
        if (leftRem > rightRem || leftRem < 0) {
            return;
        }
        if (leftRem == 0 && rightRem == 0) {
            result.add(String.valueOf(chars));
            return;
        }
        chars[i] = '(';
        genParen(leftRem - 1, rightRem, i + 1);
        chars[i] = ')';
        genParen(leftRem, rightRem - 1, i + 1);
    }
    
    public List<String> generateParenthesis(int n) {
        result = new ArrayList<String>();
        chars = new char[2 * n];
        genParen(n, n, 0);
        return result;
    }
}

[LeetCode] Rectangle Area

Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Assume that the total area is never beyond the maximum possible value of int.

Credits:
Special thanks to @mithmatt for adding this problem, creating the above image and all test cases.

Solution:
The main observation is that the vertices of the common rectangle (if it exists) must be formed by x coordinates and y coordinates of the vertices of the given two rectangles.
There are 16 possible such vertices. For any of them, if it lies in both rectangles, then it is a vertex of the common rectangle. When the two rectangles are the same, all 16 of them belong to the common rectangle (each vertex is duplicated four times).

public class Solution {
   class Point {
       int x;
       int y;
       
       Point() { }
       
       Point(int _x, int _y) {
           x = _x;
           y = _y;
       }
   }
   
   class Rect {
       int left;
       int right;
       int top;
       int bottom;
       
       Rect() {}
       
       Rect(int l, int b, int r, int t) {
           left = l;
           bottom = b;
           right = r;
           top = t;
       }
       
       Rect(Point a, Point b, Point c, Point d) {
           left = min(a.x, b.x, c.x, d.x);
           bottom = min(a.y, b.y, c.y, d.y);
           right = max(a.x, b.x, c.x, d.x);
           top = max(a.y, b.y, c.y, d.y);
       }
       
       private int min(int v1, int v2, int v3, int v4) {
           int min12 = Math.min(v1, v2);
           int min34 = Math.min(v3, v4);
           return Math.min(min12, min34);
       }
       
       private int max(int v1, int v2, int v3, int v4) {
           int max12 = Math.max(v1, v2);
           int max34 = Math.max(v3, v4);
           return Math.max(max12, max34);
       }
       
       public boolean contains(Point pt) {
           return pt.x >= left && 
                  pt.x <= right && 
                  pt.y >= bottom && 
                  pt.y <= top;
       }
       
       public int area() {
           return (right - left) * (top - bottom);
       }
   }
   
   public int computeArea(
       int A, int B, int C, int D, 
       int E, int F, int G, int H
   ) {
       Rect rect1 = new Rect(A, B, C, D);
       Rect rect2 = new Rect(E, F, G, H);
       int[] x = new int[]{A, C, E, G};
       int[] y = new int[]{B, D, F, H};
       ArrayList<Point> vertices = new ArrayList<Point>();
       for (int i = 0; i < 4; i++) {
           for (int j = 0; j < 4; j++) {
               Point p = new Point(x[i], y[j]);
               if (rect1.contains(p) && rect2.contains(p)) {
                   vertices.add(p);
               }
           }
       }
       if (vertices.size() == 0 || vertices.size() == 1) {
           return rect1.area() + rect2.area();
       }
       if (vertices.size() == 16) {
           return rect1.area();
       }
       Rect rect_common = new Rect(
           vertices.get(0),
           vertices.get(1),
           vertices.get(2),
           vertices.get(3)
       );
       return rect1.area() - rect_common.area() + rect2.area();
   }
}

Saturday, June 6, 2015

[LeetCode] Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

Solution: DFS.
This is one of those classic problems for which a not-careful-enough implementation would take O(n*H) time, where n is the total number of nodes in the tree, and H is the height of the tree. And H can be as good as O(log n), and as bad as O(n). Such an implementation has duplicate computations.
An optimal solution should make sure that we do not compute the same thing twice. A typical way to do so is to compute two different things at the same time. In the following code, we are computing the max prefix sum starting from root and the max path sum through root at the same time (in one function).
Time Complexity: O(n), where n is the total number of nodes in the tree.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int maxSum;
    
    private int maxPrefixSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left_max_preSum = maxPrefixSum(root.left);
        int right_max_preSum = maxPrefixSum(root.right);
        
        // Compute the max path sum through root
        int max_through_here = root.val;
        if (left_max_preSum > 0) {
            max_through_here += left_max_preSum;
        }
        if (right_max_preSum > 0) {
            max_through_here += right_max_preSum;
        }
        if (maxSum < max_through_here) {
            maxSum = max_through_here;
        }
        
        // Compute the max prefix sum starting from root
        int max_preSum_root = root.val;
        int max_preSum_subtree = Math.max(
                left_max_preSum, 
                right_max_preSum
            );
        if (max_preSum_subtree > 0) {
            max_preSum_root += max_preSum_subtree;
        }
        return max_preSum_root;
    }
    
    public int maxPathSum(TreeNode root) {
        maxSum = Integer.MIN_VALUE;
        maxPrefixSum(root);
        return maxSum;
    }
}

[LeetCode] Path Sum II

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

Solution: Backtracking is the most space-efficient way to solve this.
Code in Java: Non-backtracking.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private ArrayList<List<Integer>> result;
    
    void pathSum(
        TreeNode root, 
        int sum,
        ArrayList<Integer> path
    ) {
        if (root == null) { return; }
        path.add(root.val);
        sum -= root.val;
        if (root.left == null && root.right == null && sum == 0) {
            result.add(new ArrayList<Integer>(path));
        }
        pathSum(root.left, sum, new ArrayList(path));
        pathSum(root.right, sum, new ArrayList(path));
    }
    
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        result = new ArrayList<List<Integer>>();
        pathSum(root, sum, new ArrayList<Integer>());
        return result;
    }
}

Code in Java: Backtracking.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private ArrayList<List<Integer>> result;
    ArrayList<Integer> path;
    
    void pathSumBackTracking(
        TreeNode root, 
        int sum
    ) {
        if (root == null) { return; }
        path.add(root.val);
        sum -= root.val;
        if (root.left == null && root.right == null && sum == 0) {
            result.add(new ArrayList<Integer>(path));
        }
        pathSumBackTracking(root.left, sum);
        pathSumBackTracking(root.right, sum);
        path.remove(path.size() - 1);
    }
    
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        result = new ArrayList<List<Integer>>();
        path = new ArrayList<Integer>();
        pathSumBackTracking(root, sum);
        return result;
    }
}

[LeetCode] Merge Intervals

Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Solution: First sort, then merge.
See also: [LeetCode] Insert Interval.

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    class IntervalComparator implements Comparator<Interval> {
        public int compare(Interval a, Interval b) {
            return a.start - b.start;
        }
    }
    
    private Interval merge(Interval a, Interval b) {
        int start = Math.min(a.start, b.start);
        int end = Math.max(a.end, b.end);
        return new Interval(start, end);
    }
    
    private boolean overlap(Interval a, Interval b) {
        if (a.end < b.start || b.end < a.start) {
            return false;
        }
        return true;
    }
    
    public List<Interval> merge(List<Interval> intervals) {
        Collections.sort(intervals, new IntervalComparator());
        int i = 0;
        while (i < intervals.size()) {
            Interval interval = intervals.get(i);
            while (
                i < intervals.size() &&
                overlap(interval, intervals.get(i))
            ) {
                interval = merge(interval, intervals.remove(i));
            }
            intervals.add(i, interval);
            i++;
        }
        return intervals;
    }
}