[LeetCode] Container With Most Water

Container With Most Water

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.

Solution: Two pointers. See the discussions. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

public class Solution { public int maxArea(int[] height) { int i = 0; int j = height.length - 1; int maxArea = 0; while (i < j) { int w = j - i; int h = Math.min(height[i], height[j]); int area = w * h; if (maxArea < area) { maxArea = area; } if (height[i] < height[j]) { i++; } else { j--; } } return maxArea; } }

[LeetCode] Anagrams

Anagrams

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Solution: Sorting and HashMap.

public class Solution {
    private String sort(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }
    
    public List<String> anagrams(String[] strs) {
        HashMap<String, ArrayList<String>> map = 
            new HashMap<String, ArrayList<String>>();
        for (String s : strs) {
            String str = sort(s);
            if (map.containsKey(str)) {
                map.get(str).add(s);
            } else {
                ArrayList<String> li = new ArrayList<String>();
                li.add(s);
                map.put(str, li);   
            }
        }
        
        ArrayList<String> list = new ArrayList<String>();
        Iterator iter = map.values().iterator();
        while (iter.hasNext()) {
            ArrayList<String> li = (ArrayList<String>)iter.next();
            if (li.size() > 1) {
                list.addAll(li);
            }
        }
        return list;
    }
}

[LeetCode] 3Sum Closest

3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Solution: Based on [LeetCode] 3SUM.
Complexity: O(n^2). Since 3SUM can be solved in O(n^2) time. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

public class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int minDist = Integer.MAX_VALUE; int closest = target; for (int i = 0; i < nums.length - 2; i++) { int j = i + 1; int k = nums.length - 1; while (j < k) { int sum = nums[i] + nums[j] + nums[k]; int dist = Math.abs(sum - target); if (dist < minDist) { minDist = dist; closest = sum; } if (sum == target) { return target; } else if (sum < target) { j++; } else { k--; } } } return closest; } }

[LeetCode] 4Sum

4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

Solution: 

Sorting helps us to deal with both constraints. Keep 4 pointers. We move the 1st pointer from left to right, and each time solve a 3SUM problem using the other 3 pointers in the subarray with index ranging from i + 1 to n.
Complexity: O(n^3). Since 3SUM can be solved in O(n^2) time. 
Further reading: [LeetCode] 3SUM

public class Solution {
    private ArrayList<Integer> quadruplet(
        int[] nums, 
        int i, 
        int j, 
        int k, 
        int l
    ) {
        ArrayList<Integer> li = new ArrayList<Integer>();
        li.add(nums[i]);
        li.add(nums[j]);
        li.add(nums[k]);
        li.add(nums[l]);
        return li;
    }
    
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        ArrayList<List<Integer>> list = 
            new ArrayList<List<Integer>>();
        for (int i = 0; i < nums.length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int k = j + 1;
                int l = nums.length - 1;
                while (k < l) {
                    int sum = nums[i] + nums[j] + nums[k] + nums[l];
                    if (sum == target) {
                        list.add(quadruplet(nums, i, j, k, l));
                        k++;
                        l--;
                        while (k < l && nums[k] == nums[k - 1]) {
                            k++;
                        }
                        while (k < l && nums[l] == nums[l + 1]) {
                            l--;
                        }
                    } else if (sum < target) {
                        k++;
                    } else {
                        l--;
                    }
                }
            }
        }
        return list;
    }
}

[LeetCode] 3Sum

3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Solution: 
Sorting helps us to deal with both constraints. Keep 3 pointers. We move the 1st pointer from left to right, and each time solve a 2SUM problem using the other 2 pointers in the subarray with index ranging from i + 1 to n.
Complexity: O(n^2). 
Since 2SUM can be solved in O(n) time after sorting, or in O(n) time using HashMap.

public class Solution {
    private ArrayList<Integer> oneTriple(int a, int b, int c) {
        ArrayList<Integer> triple = new ArrayList<Integer>();
        triple.add(a);
        triple.add(b);
        triple.add(c);
        return triple;
    }
    
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        ArrayList<List<Integer>> list 

            = new ArrayList<List<Integer>>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int j = i + 1;
            int k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    list.add(oneTriple(nums[i], nums[j], nums[k]));
                    j++;
                    k--;
                    while (j < k && nums[j] == nums[j - 1]) {
                        j++;
                    }
                    while (j < k && nums[k] == nums[k + 1]) {
                        k--;
                    }
                } else if (sum > 0) {
                    k--;
                } else {
                    j++;
                }
            }
        }
        return list;
    }
}

[LeetCode] Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Solution: Use a stack.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

public class Solution { private boolean isNumber(String s) { if (s.charAt(0) == '-' && s.length() > 1) { return true; } if (s.charAt(0) >= '0' && s.charAt(0) <= '9') { return true; } return false; } private int evalOp(int first, int second, String s) { if (s.equals("+")) { return first + second; } if (s.equals("-")) { return first - second; } if (s.equals("*")) { return first * second; } if (s.equals("/")) { return first / second; } return 0; } public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<Integer>(); for (String s : tokens) { if (isNumber(s)) { stack.push(Integer.parseInt(s)); } else { int second = stack.pop(); int first = stack.pop(); int result = evalOp(first, second, s); stack.push(result); } } return stack.pop(); } }

[LeetCode] Contains Duplicate II

Contains Duplicate II

Given an array of integers and an integer k, return true if and only if there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.
Solution: HashMap.
In the hash map, we use nums[i] as key, and the index i as value. 
If nums[j] = nums[i] (j > i), we check whether j - i <= k. If so, we return true. 
We update the value for the key nums[j] = nums[i] when j - i > k, or simply register the new pair (nums[j], j) when there does not exist an index i such that nums[j] = nums[i], where j > i.
Correctness: 
The observation is that if there exist indices a < b < c such that nums[a] = nums[b] = nums[c], then we only need to check whether b - a <= k, and c - b <= k, since c - a = (c - b) + (b - a). That being said, we only need to check two consecutive duplicate elements. This is what the hash map is doing, hence the algorithm is correct.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

public class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(nums[i])) { if (i - map.get(nums[i]) <= k) { return true; } } map.put(nums[i], i); } return false; } }

[LeetCode] Add and Search Word - Data structure design

Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

Solution: This is based on the post for [LeetCode] Implement Trie (Prefix Tree).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

public class WordDictionary { Trie trie = new Trie(); // Adds a word into the data structure. public void addWord(String word) { trie.insert(word); } // Returns if the word is in the data structure. A word could // contain the dot character '.' to represent any one letter. public boolean search(String word) { return trie.search(word); } } // Your WordDictionary object will be instantiated and called as such: // WordDictionary wordDictionary = new WordDictionary(); // wordDictionary.addWord("word"); // wordDictionary.search("pattern"); class TrieNode { char ch; boolean isWord = false; TrieNode[] children = null; public TrieNode() { } public TrieNode(char c) { this.ch = c; } } class Trie { TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String word) { if (word == null || word.length() == 0) { return; } TrieNode node = root; for (int i = 0; i < word.length(); i++) { if (node.children == null) { node.children = new TrieNode[26]; } int idx = word.charAt(i) - 'a'; if (node.children[idx] == null) { node.children[idx] = new TrieNode(word.charAt(i)); } node = node.children[idx]; if (i == word.length() - 1) { node.isWord = true; } } } public boolean search(String word) { if (word == null || word.length() == 0) { return false; } return DFS(word, 0, root); } public boolean DFS(String word, int i, TrieNode node) { if (node == null) { return false; } if (i == word.length()) { return node.isWord; } if (node.children == null) { return false; } if (word.charAt(i) != '.') { int idx = word.charAt(i) - 'a'; return DFS(word, i + 1, node.children[idx]); } for (int j = 0; j < 26; j++) { if (DFS(word, i + 1, node.children[j])) { return true; } } return false; } }

[LeetCode] Implement Trie (Prefix Tree)

Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Solution: See below.
Further reading: http://en.wikipedia.org/wiki/Trie

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93

class TrieNode { char ch; boolean isWord = false; TrieNode[] children = null; // Initialize your data structure here. public TrieNode() { } public TrieNode(char c) { this.ch = c; } } public class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } // Inserts a word into the trie. public void insert(String word) { if (word == null || word.length() == 0) { return; } TrieNode node = root; for (int i = 0; i < word.length(); i++) { if (node.children == null) { node.children = new TrieNode[26]; } int idx = word.charAt(i) - 'a'; if (node.children[idx] == null) { node.children[idx] = new TrieNode(word.charAt(i)); } node = node.children[idx]; if (i == word.length() - 1) { node.isWord = true; } } } // Returns if the word is in the trie. public boolean search(String word) { if (word == null || word.length() == 0) { return false; } TrieNode node = root; for (int i = 0; i < word.length(); i++) { if (node.children == null) { return false; } int idx = word.charAt(i) - 'a'; if (node.children[idx] == null) { return false; } if ( i == word.length() - 1 && node.children[idx].isWord == false ) { return false; } node = node.children[idx]; } return true; } // Returns if there is any word in the trie // that starts with the given prefix. public boolean startsWith(String prefix) { if (prefix == null || prefix.length() == 0) { return false; } TrieNode node = root; for (int i = 0; i < prefix.length(); i++) { if (node.children == null) { return false; } int idx = prefix.charAt(i) - 'a'; if (node.children[idx] == null) { return false; } node = node.children[idx]; } return true; } } // Your Trie object will be instantiated and called as such: // Trie trie = new Trie(); // trie.insert("somestring"); // trie.search("key");