Happy Coding

Thursday, July 2, 2015

[LeetCode] Contains Duplicate III

Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

Solution: TreeSet.
We maintain a TreeSet of size k. Each time when the size is greater than k, we remove old ones. TreeSet supports the following two operations:

floor(E e)

Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.

ceiling(E e)

Returns the least element in this set greater than or equal to the given element, or null if there is no such element.

Time Complexity: O(n log k).
Each operation takes O(log k) time.

Space Complexity: O(k).

public class Solution {
    TreeSet<Integer> tree;
    
    private boolean containsNearbyAlmostDuplicate(
        int num, 
        int k, 
        int t
    ) {
        Integer preClosest = tree.floor(num);
        if (preClosest != null && num <= preClosest + t) {
            return true;
        }
        Integer nextClosest = tree.ceiling(num);
        if (nextClosest != null && num >= nextClosest - t) {
            return true;
        }
        return false;
    }
    
    public boolean containsNearbyAlmostDuplicate(
        int[] nums, 
        int k, 
        int t
    ) {
        if (nums == null || k < 1 || t < 0) {
            return false;
        }
        tree = new TreeSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (containsNearbyAlmostDuplicate(nums[i], k, t)) {
                return true;
            }
            tree.add(nums[i]);
            if (i >= k) {
                tree.remove(nums[i - k]);
            }
        }
        return false;
    }
}

Saturday, June 27, 2015

[LeetCode] Basic Calculator II

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;
    }
}