Showing posts with label Hash Table. Show all posts
Showing posts with label Hash Table. Show all posts

Friday, November 23, 2018

939. Minimum Area Rectangle

Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.

If there isn't any rectangle, return 0.


Example 1:

Input: [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

Example 2:

Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2


Note:

1 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.


Solution:

The brute-force way is to use four for loops to iterate all four points. For each four points, we can determine whether they can form a rectangular and maintain a minimum size.

If 4 points can form a rectangular, they have to be (x1, y1), (x1, y2), (x2, y1), and (x2, y2). We can see x1 exists twice, x2 exists twice, y1 exists twice and y2 exists twice. We can implement an isValid function with this logic.

The bruce-force approach takes O(n4) time, which is not good.

A better solution is we can go through all points in O(n) and maintain a HashMap. For each x, we maintain a Set in the map that contains all existing y corresponding to this x.

After building up the map, we can use two for loops to choose any two points in the input. For each two points (A and B), we first determine if they are diagonal. If they are diagonal, we know these two points have different x and different y.

Then we can use the map to check:
1.  there exists a point which has A's x and B's y
2.  there exists a point which has B's x and A's y
3.  check size

This takes O(1) time.

In this way, we can solve the problem in O(n2) time with an additional space for the map.


Code:


class Solution {
    public int minAreaRect(int[][] points) {
        int res = Integer.MAX_VALUE;
        HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
        for (int[] point : points) {
            if (!map.containsKey(point[0])) {
                map.put(point[0], new HashSet<>());
            }
            map.get(point[0]).add(point[1]);
        }
        for (int[] pointA : points) {
            for (int[] pointB : points) {
                if (pointA[0] == pointB[0] || pointA[1] == pointB[1]) {
                    continue;
                }
                if (!map.get(pointA[0]).contains(pointB[1]) 
                    || !map.get(pointB[0]).contains(pointA[1])) {
                    continue;
                }
                res = Math.min(res, 
                               Math.abs((pointB[0] - pointA[0]) 
                                        * (pointB[1] - pointA[1])
                                        )
                              );
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

Tuesday, May 29, 2018

219. Contains Duplicate II

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

Example 1:

Input: [1,2,3,1], k = 3
Output: true

Example 2:

Input: [1,0,1,1], k = 1
Output: true

Example 3:

Input: [1,2,1], k = 0
Output: false


Solution:

In this array if we can find index i and j such that nums[i] == nums[j] and j - i <= k, return true. If we cannot find such i and j, return false.

We can iterate through the array and maintain a HashMap to store the value we've already met, and it's index.

For any index i, if there exists the same value in the map, we check their distance. If the distance is <= k, return true. If not, we update this value in the map with a new index i.

When finish iterating the array, we do not find such pair, and return false.

The time complexity is O(n) and the space complexity is also O(n).


Code:


class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        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;
    }
}

Tuesday, August 8, 2017

653. Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.
Example 1:
Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True
Example 2:
Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False


Solution:

The inorder sequence of BST is sorted.

So firstly we use O(n) time to construct a sorted ArrayList.

After that, we can apply two pointers from the start and end of the ArrayList to search for a target sum.

The time complexity of the search is also (n).

Thus, the time complexity is O(n) and the space complexity is O(n).


Code:


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        int i = 0;
        int j = list.size() - 1;
        while (i < j) {
            int sum = list.get(i) + list.get(j);
            if (sum == k) {
                return true;
            }
            else if (sum < k) {
                i++;
            }
            else {
                j--;
            }
        }
        return false;
    }

    public List<Integer> inorder(TreeNode root, List<Integer> list) {
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }
}

Friday, July 14, 2017

205. Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
For example,
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.
Note:
You may assume both s and t have the same length.



Solution:

This problem is a simplified version of Word Pattern.



Code:


public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        HashMap<Character, Character> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);
            if (!map.containsKey(c1)) {
                map.put(c1, c2);
            }
            else {
                if (map.get(c1) != c2) {
                    return false;
                }
            }
        }
        map.clear();
        for (int i = 0; i < t.length(); i++) {
            char c1 = t.charAt(i);
            char c2 = s.charAt(i);
            if (!map.containsKey(c1)) {
                map.put(c1, c2);
            }
            else {
                if (map.get(c1) != c2) {
                    return false;
                }
            }
        }
        return true;
    }
}

290. Word Pattern

Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.
Examples:
  1. pattern = "abba", str = "dog cat cat dog" should return true.
  2. pattern = "abba", str = "dog cat cat fish" should return false.
  3. pattern = "aaaa", str = "dog cat cat dog" should return false.
  4. pattern = "abba", str = "dog dog dog dog" should return false.
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.



Solution:

The idea is to create two HashMaps.

We first check the uniqueness between each character in the pattern to words in string using one HashMap.

Then we check the uniqueness between each words in the string to the character in the pattern using the second HashMap.

The reason to check twice is to handle such case:

"abcb" -> "dog cat dog cat"



Code:


public class Solution {
    public boolean wordPattern(String pattern, String str) {
        HashMap<Character, String> map1 = new HashMap<>();
        String[] strarr = str.split(" ");
        if (strarr.length != pattern.length()) {
            return false;
        }
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (!map1.containsKey(c)) {
                map1.put(c, strarr[i]);
            }
            else {
                if (!map1.get(c).equals(strarr[i])) {
                    return false;
                }
            }
        }
        HashMap<String, Character> map2 = new HashMap<>();
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (!map2.containsKey(strarr[i])) {
                map2.put(strarr[i], c);
            }
            else {
                if (map2.get(strarr[i]) != c) {
                    return false;
                }
            }
        }
        return true;
    }
}

Tuesday, July 11, 2017

37. Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.
A sudoku puzzle...
...and its solution numbers marked in red.



Solution:

Use DFS and backtracking to fill each grid with a valid answer.



Code:


public class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length != 9) {
            return;
        }
        if (board[0] == null || board[0].length != 9) {
            return;
        }
        helper(board);
    }
    
    public boolean helper(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    continue;
                }
                for (char num = '1'; num <= '9'; num++) {
                    board[i][j] = num;
                    if (isValid(board) && helper(board)) {
                        return true;
                    }
                    board[i][j] = '.';
                }
                return false;
            }
        }
        return true;
    }
    
    public boolean isValid(char[][] board) {
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (set.contains(board[i][j])) {
                    return false;
                }
                set.add(board[i][j]);
            }
            set.clear();
        }
        for (int j = 0; j < 9; j++) {
            for (int i = 0; i < 9; i++) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (set.contains(board[i][j])) {
                    return false;
                }
                set.add(board[i][j]);
            }
            set.clear();
        }
        for (int k = 0; k < 9; k++) {
            for (int i = k / 3 * 3; i < k / 3 * 3 + 3; i++) {
                for (int j = (k % 3) * 3; j < (k % 3) * 3 + 3; j++) {
                    if (board[i][j] == '.') {
                        continue;
                    }
                    if (set.contains(board[i][j])) {
                        return false;
                    }
                    set.add(board[i][j]);
                }
            }
            set.clear();
        }
        return true;
    }
}

36. Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
A partially filled sudoku which is valid.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.



Solution:

For this kind of problems, you have to go through the entire grid to check each entry.

We first check each row.

Secondly we check each column.

Finally we check each 3 x 3 grid. We can use / and % to locate the coordinates of sub grid.

The time complexity is O(1) and the space complexity is O(1), since the number of input is constant.



Code:

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board == null || board.length != 9) {
            return false;
        }
        if (board[0] == null || board[0].length != 9) {
            return false;
        }
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (set.contains(board[i][j])) {
                    return false;
                }
                set.add(board[i][j]);
            }
            set.clear();
        }
        for (int j = 0; j < 9; j++) {
            for (int i = 0; i < 9; i++) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (set.contains(board[i][j])) {
                    return false;
                }
                set.add(board[i][j]);
            }
            set.clear();
        }
        for (int k = 0; k < 9; k++) {
            for (int i = k / 3 * 3; i < k / 3 * 3 + 3; i++) {
                for (int j = (k % 3) * 3; j < (k % 3) * 3 + 3; j++) {
                    if (board[i][j] == '.') {
                        continue;
                    }
                    if (set.contains(board[i][j])) {
                        return false;
                    }
                    set.add(board[i][j]);
                }
            }
            set.clear();
        }
        return true;
    }
}

Saturday, July 8, 2017

508. Most Frequent Subtree Sum

Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.
Examples 1
Input:
  5
 /  \
2   -3
return [2, -3, 4], since all the values happen only once, return all of them in any order.
Examples 2
Input:
  5
 /  \
2   -5
return [2], since 2 happens twice, however -5 only occur once.
Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.



Solution:

The idea is to perform a bottom-up traversal of the tree and calculate the subtree sum of each nodes.

The frequency of the sum is stored in a HashMap.

After this pre-computation, we go through the HashMap and find the maximum frequency.

Thus, we go through the HashMap one more time and put all the keys that map to the maximum frequency to the result list.



Code:


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    HashMap<Integer, Integer> map = new HashMap<>();
    public int[] findFrequentTreeSum(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        helper(root);
        int max = Integer.MIN_VALUE;
        for (int val : map.values()) {
            max = Math.max(max, val);
        }
        List<Integer> list = new ArrayList<>();
        for (int key : map.keySet()) {
            if (map.get(key) == max) {
                list.add(key);
            }
        }
        int[] res = new int[list.size()];
        int i = 0;
        for (int val : list) {
            res[i++] = val;
        }
        return res;
    }
    public int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = helper(root.left);
        int right = helper(root.right);
        int sum = left + right + root.val;
        if (!map.containsKey(sum)) {
            map.put(sum, 1);
        }
        else {
            map.put(sum, map.get(sum) + 1);
        }
        return sum;
    }
}

Friday, July 7, 2017

451. Sort Characters By Frequency

Given a string, sort it in decreasing order based on the frequency of characters.
Example 1:
Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
Example 2:
Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.
Example 3:
Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.



Solution:

This is a bucket sort problem.

We first count the frequency of each character and maintains a max frequency.

The size of bucket array is the max + 1.

bucket[i] denotes the character(s) who has frequency of i.

We can go through the frequency map and insert each character to the corresponding bucket.

Finally, we start from the max frequency and put all characters from non-empty buckets to the result string.

The time complexity is O(n) and the space complexity is O(n).



Code:


public class Solution {
    public String frequencySort(String s) {
        int[] map = new int[256];
        int max = 0;
        for (char c : s.toCharArray()) {
            map[c]++;
            max = Math.max(max, map[c]);
        }
        String[] bucket = new String[max + 1];
        for (int i = 0; i < 256; i++) {
            String str = bucket[map[i]];
            if (map[i] > 0) {
                bucket[map[i]] = str == null ? "" + (char) i : str + (char) i;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = max; i >= 0; i--) {
            if (bucket[i] != null) {
                for (char c : bucket[i].toCharArray()) {
                    for (int j = 0; j < i; j++) {
                        sb.append(c);
                    }
                }
            }
        }
        return sb.toString();
    }
}

Monday, June 26, 2017

560. Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:
Input:nums = [1,1,1], k = 2
Output: 2
Note:
  1. The length of the array is in range [1, 20,000].
  2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].



Solution:

The idea is to use a HashMap to store the prefixSum and its frequency.

When we are at index i with prefixSum sum, we check if there exists a prefixSum (sum - k).

If so, the frequency of this (sum - k) means how many different continuous subarray we can have that end with i will sum up to k.

The time complexity is O(n) and the space complexity is also O(n).



Code:


public class Solution {
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int count = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0;
        for (int i = 0; i < nums.length; i++)  {
            sum += nums[i];
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            if (!map.containsKey(sum)) {
                map.put(sum, 1);
            }
            else {
                map.put(sum, map.get(sum) + 1);
            }
        }
        return count;
    }
}

Saturday, June 24, 2017

389. Find the Difference

Given two strings s and t which consist of only lowercase letters.
String t is generated by random shuffling string s and then add one more letter at a random position.
Find the letter that was added in t.
Example:
Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.



Solution:

XOR all elements.

Pairs will cancel out.



Code:


public class Solution {
    public char findTheDifference(String s, String t) {
        char xor = 0;
        for (char c : s.toCharArray()) {
            xor ^= c;
        }
        for (char c : t.toCharArray()) {
            xor ^= c;
        }
        return xor;
    }
}

288. Unique Word Abbreviation

An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations:
a) it                      --> it    (no abbreviation)

     1
b) d|o|g                   --> d1g

              1    1  1
     1---5----0----5--8
c) i|nternationalizatio|n  --> i18n

              1
     1---5----0
d) l|ocalizatio|n          --> l10n
Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word's abbreviation is unique if no other word from the dictionary has the same abbreviation.
Example: 
Given dictionary = [ "deer", "door", "cake", "card" ]

isUnique("dear") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true



Solution:

To clarify the problem, we take a look at these examples:

[“dog”]; isUnique(“dig”);
False.
Because "dig" has the same abbreviation with "dog" and dog is already in the dictionary.

[“dog”, “dog"]; isUnique(“dog”);
True.
Because "dog" is the only abbreviation of "dog".

[“dog”, “dig”]; isUnique(“dog”);
False.
Because "dog" had "dig" have the same abbreviation.

To convert a word to its abbreviation, we first check if the length of the word is smaller or equal to 2.

If so, we do not need to convert it.

Otherwise, the abbreviation is the word's first letter + its length - 2 + the word's last letter.

We use a HashMap to store the abbreviation to word mapping.

If we find an abbreviation can map to two different words, we simply set the word to "".

When we check if a word is valid, we check whether its abbreviation's mapping word is itself, or there is no mapping in the HashMap.



Code:


public class ValidWordAbbr {

    public HashMap<String, String> map;
    public ValidWordAbbr(String[] dictionary) {
        map = new HashMap<>();
        for (String word : dictionary) {
            String abbr = getAbbr(word);
            if (!map.containsKey(abbr)) {
                map.put(abbr, word);
            }
            else {
                if (!map.get(abbr).equals(word)) {
                    map.put(abbr, "");
                }
            }
        }
    }
    
    public boolean isUnique(String word) {
        String abbv = getAbbr(word);
        return !map.containsKey(abbv) || map.get(abbv).equals(word);
    }
    
    public String getAbbr(String word) {
        int n = word.length();
        return n <= 2 ? word : "" + word.charAt(0) + (n - 2) + word.charAt(n - 1);
    }
}

/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * ValidWordAbbr obj = new ValidWordAbbr(dictionary);
 * boolean param_1 = obj.isUnique(word);
 */

Saturday, June 17, 2017

18. 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: 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:

Same with 3Sum.

Just having one more loop.



Code:


public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length; j++) {
                if (j != i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int lo = j + 1;
                int hi = nums.length - 1;
                while (lo < hi) {
                    if (nums[lo] + nums[hi] + nums[i] + nums[j] == target ) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[lo]);
                        list.add(nums[hi]);
                        result.add(list);
                        lo++;
                        hi--;
                        while (lo < hi && nums[lo] == nums[lo - 1]) {
                            lo++;
                        }
                        while (lo < hi && nums[hi] == nums[hi + 1]) {
                            hi--;
                        }
                    }
                    else if (nums[lo] + nums[hi] + nums[i] + nums[j] < target) {
                        lo++;
                    }
                    else {
                        hi--;
                    }
                }
            }
        }
        return result;
    }
}