Friday, March 22, 2019

Lintcode 130. Heapify

Given an integer array, heapify it into a min-heap array.
For a heap array A, A[0] is the root of heap, and for each A[i], A[i * 2 + 1] is the left child of A[i] and A[i * 2 + 2] is the right child of A[i].

Example

Given [3,2,1,4,5], return [1,2,3,4,5] or any legal heap array.

Challenge

O(n) time complexity

Clarification

What is heap?
  • Heap is a data structure, which usually have three methods: push, pop and top. where "push" add a new element the heap, "pop" delete the minimum/maximum element in the heap, "top" return the minimum/maximum element.

What is heapify?
  • Convert an unordered integer array into a heap array. If it is min-heap, for each element A[i], we will get A[i * 2 + 1] >= A[i] and A[i * 2 + 2] >= A[i].

What if there is a lot of solutions?
  • Return any of them.

Solution 1: Shift-up approach
Since for each node with index i, its parent's index is (i - 1) / 2. So the idea of the shift-up approach is for each node from left, compare to its parent, if not smaller, swap until the heap order is made. Therefore, for each node with index i, its left nodes are all heapified. 

Code (Java):
public class Solution {
    /*
     * @param A: Given an integer array
     * @return: nothing
     */
    public void heapify(int[] A) {
        if (A == null || A.length < 2) {
            return;
        }

        for (int i = 1; i < A.length; i++) {
            swim(i, A);
        }
    }

    private void swim(int i, int[] A) {
        while (i > 0 && A[i] <= A[(i - 1) / 2]) {
            swap(A, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

Solution 2: Shift-down approach
Unlike the shift up, the shift-down approach starts from the N/2-th element, it compares with its two children, and swap the node with its smaller children until the order is heapify. So for each node i, its right nodes are heapify ordered.

Code (Java):
public class Solution {
    /*
     * @param A: Given an integer array
     * @return: nothing
     */
    public void heapify(int[] A) {
        if (A == null || A.length < 2) {
            return;
        }

        for (int i = A.length / 2 - 1; i >= 0; i--) {
            sink(A, i);
        }
    }

    private void sink(int[] A, int i) {
        while (2 * i + 1 < A.length) {
            int child = 2 * i + 1;
            if (2 * i + 2 < A.length && A[child] > A[2 * i + 2]) {
                child = 2 * i + 2;
            }

            if (A[i] < A[child]) {
                break;
            }

            swap(A, i, child);
            i = child;
        }
    }

    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

Complexity discussion:
The shift-up solution takes time O(nlogn) since we may need to move every node to the root.

The bottom-down solution takes O(n) since we only move n/2 nodes down to the bottom. The rest of the n/2 nodes are already in the bottom.

The formal proof can be found here:
Both of these solutions will produce a valid heap. The question is: which implementation for buildHeap is more efficient? Unsurprisingly, it is the second operation that uses siftDown.
Let h = log n represent the height of the heap. The work required for the siftDown approach is given by the sum
(0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1).
Each term in the sum has the maximum distance a node at the given height will have to move (zero for the bottom layer, h for the root) multiplied by the number of nodes at that height. In contrast, the sum for calling siftUp on each node is
(h * n/2) + ((h-1) * n/4) + ((h-2)*n/8) + ... + (0 * 1).
It should be clear that the second sum is larger. The first term alone is hn/2 = 1/2 n log n, so this approach has complexity at best O(n log n). But how do we prove that the sum for the siftDownapproach is indeed O(n)? One method (there are other analyses that also work) is to turn the finite sum into an infinite series and then use Taylor series. We may ignore the first term, which is zero:
Taylor series for buildHeap complexity
If you aren't sure why each of those steps works, here is a justification for the process in words:
  • The terms are all positive, so the finite sum must be smaller than the infinite sum.
  • The series is equal to a power series evaluated at x=1/2.
  • That power series is equal to (a constant times) the derivative of the Taylor series for f(x)=1/(1-x).
  • x=1/2 is within the interval of convergence of that Taylor series.
  • Therefore, we can replace the Taylor series with 1/(1-x), differentiate, and evaluate to find the value of the infinite series.

Since the infinite sum is exactly n, we conclude that the finite sum is no larger, and is therefore, O(n).

Thursday, March 21, 2019

Lintcode 126. Max Tree

Given an integer array with no duplicates. A max tree building on this array is defined as follow:
  • The root is the maximum number in the array
  • The left subtree and right subtree are the max trees of the subarray divided by the root number.
Construct the max tree by the given array.

Example

Given [2, 5, 6, 0, 3, 1], the max tree constructed by this array is:
    6
   / \
  5   3
 /   / \
2   0   1

Challenge

O(n) time and memory.
Solution:
For any node x of the array, its parent must be the first number greater than it. 
– ….., L, <X, …,<X, X, <X, …, <X, R,…
– 如果L<R,[L, R]里一定R先做根。然后[L, R)里L先做根,然后就是X
– 如果L>R, [L, R]里一定L先做根。然后(L, R]里R先做根,然后就是X
• 如何找到每个值左右第一个比它大的值?
– 单调递减栈

Code (Java)
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param A: Given an integer array with no duplicates.
     * @return: The root of max tree.
     */
    public TreeNode maxTree(int[] A) {
        if (A == null || A.length == 0) {
            return null;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(new TreeNode(A[0]));

        for (int i = 1; i < A.length; i++) {
            TreeNode curr = new TreeNode(A[i]);
            while (!stack.isEmpty() && curr.val > stack.peek().val) {
                TreeNode top = stack.pop();
                if (stack.isEmpty() || curr.val < stack.peek().val)  {
                    curr.left = top;
                } else {
                    stack.peek().right = top;
                }
            }
            stack.push(curr);
        }

        // now the stack is a mono descreasing stack
        //
        while (stack.size() > 1) {
            TreeNode top = stack.pop();
            stack.peek().right = top;
        }

        return stack.pop();
    }
}

Lintcode 364. Trapping Rain Water II

Given n x m non-negative integers representing an elevation map 2d where the area of each cell is 1 x 1, compute how much water it is able to trap after raining.

Example

Given 5*4 matrix
[12,13,0,12]
[13,4,13,12]
[13,8,10,12]
[12,13,12,12]
[13,13,13,13]
return 14.
Code (Java)
public class Solution {
    /**
     * @param heights: a matrix of integers
     * @return: an integer
     */
    public int trapRainWater(int[][] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }

        int m = heights.length;
        int n = heights[0].length;

        PriorityQueue<Pair> pq = new PriorityQueue<>(new MyPairComparator());
        boolean[][] visited = new boolean[m][n];

        // step 1: put borders into the pq
        //
        for (int i = 0; i < n; i++) {
            pq.offer(new Pair(0, i, heights[0][i]));
            visited[0][i] = true;

            pq.offer(new Pair(m - 1, i, heights[m - 1][i]));
            visited[m - 1][i] = true;
        }

        for (int i = 1; i < m - 1; i++) {
            pq.offer(new Pair(i, 0, heights[i][0]));
            visited[i][0] = true;

            pq.offer(new Pair(i, n - 1, heights[i][n - 1]));
            visited[i][n - 1] = true;
        }
        
        int ans = 0;
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!pq.isEmpty()) {
            Pair top = pq.poll();

            for (int i = 0; i < 4; i++) {
                int nx = top.x + dirs[i][0];
                int ny = top.y + dirs[i][1];

                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    ans += Math.max(0, top.val - heights[nx][ny]);
                    pq.offer(new Pair(nx, ny, Math.max(top.val, heights[nx][ny])));
                }
            }
        }

        return ans;
    }
}

class Pair {
    int x;
    int y;
    int val;

    public Pair(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }
}

class MyPairComparator implements Comparator<Pair> {
    @Override
    public int compare(Pair a, Pair b) {
        return a.val - b.val;
    }
}

Tuesday, March 19, 2019

Lintcode 360. Sliding Window Median

Given an array of n integer, and a moving window(size k), move the window at each iteration from the start of the array, find the median of the element inside the window at each moving. (If there are even numbers in the array, return the N/2-th number after sorting the element in the window. )

Example

For array [1,2,7,8,5], moving window size k = 3. return [2,7,7]
At first the window is at the start of the array like this
[ | 1,2,7 | ,8,5] , return the median 2;
then the window move one step forward.
[1, | 2,7,8 | ,5], return the median 7;
then the window move one step forward again.
[1,2, | 7,8,5 | ], return the median 7;

Challenge

O(nlog(n)) time

Solution:
Use two PriorityQueue as a customerized queue. The max PQ saves the smaller element while the minPQ saves the bigger elements. We also need to rebalance the size of the two pq. The total number of elements of the two pqs are k.

Code (Java):
public class Solution {
    /**
     * @param nums: A list of integers
     * @param k: An integer
     * @return: The median of the element inside the window at each moving
     */
    public List<Integer> medianSlidingWindow(int[] nums, int k) {
        List<Integer> ans = new ArrayList<>();

        if (nums == null || nums.length < k || k <= 0 || k > nums.length) {
            return ans;
        }

        MyQueue myQueue = new MyQueue();

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (myQueue.size() < k) {
                myQueue.offer(num);
            } else {
                myQueue.delete(nums[i - k]);
                myQueue.offer(num);
            }

            if (i >= k - 1) {
                ans.add(myQueue.getMedian());
            }
        }

        return ans;
    }
}

class MyQueue {
    private PriorityQueue<Integer> maxPQ;
    private PriorityQueue<Integer> minPQ;

    public MyQueue() {
        maxPQ = new PriorityQueue<>(Collections.reverseOrder());
        minPQ = new PriorityQueue<>();
    }

    public int size() {
        return maxPQ.size() + minPQ.size();
    }

    // minPQ.size == maxPQ.size OR
    // maxPQ.size - minPQ.size == 1
    //
    public void offer(int num) {
        if (maxPQ.isEmpty() || num <= maxPQ.peek()) {
            maxPQ.offer(num);
        } else {
            minPQ.offer(num);
        }

        rebalance();
    }

    public void delete(Integer num) {
        if (!maxPQ.isEmpty() && num <= maxPQ.peek()) {
            maxPQ.remove(num);
        } else {
            minPQ.remove(num);
        }

        rebalance();
    }

    public int getMedian() {
        return maxPQ.peek();
    }

    private void rebalance() {
        if (maxPQ.size() - minPQ.size() > 1) {
            minPQ.offer(maxPQ.poll());
        }

        if (minPQ.size() > maxPQ.size()) {
            maxPQ.offer(minPQ.poll());
        }
    }
}

Monday, March 18, 2019

Lintcode 634. Word Squares

Given a set of words without duplicates, find all word squares you can build from them.
A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).
For example, the word sequence ["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically.
b a l l
a r e a
l e a d
l a d y

Example

Given a set ["area","lead","wall","lady","ball"]
return [["wall","area","lead","lady"],["ball","area","lead","lady"]]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

Given a set ["abat","baba","atan","atal"]
return [["baba","abat","baba","atan"],["baba","abat","baba","atal"]]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

Notice

  • There are at least 1 and at most 1000 words.
  • All words will have the exact same length.
  • Word length is at least 1 and at most 5.
  • Each word contains only lowercase English alphabet a-z.


Solution:
For a naive solution, for each row, we can have at most n possbile choices, where n is the number of words. For the word length with m, the toal time is n^m. For each possible board, we need additional n * m time to check if it's a squre or not. So the total time complexity is O(n^m * n * m). 

Do we have a better solution? We can actually use a trie to look up candidates quickly. For the first row, we can have n possibilities. For the second row, we have 1st character set, for the second, we have 1st and 2nd character set, for the third row, we have first, second and third characters set, etc..

So the idea is for each prefix, we go to the trie and get all the words with that prefix. Then try to use DFS to go through all probabilities.

Code (Java): 
public class Solution {
    /*
     * @param words: a set of words without duplicates
     * @return: all word squares
     */
    public List<List<String>> wordSquares(String[] words) {
        List<List<String>> ans = new ArrayList<>();
        if (words == null || words.length == 0) {
            return ans;
        }

        Trie trie = new Trie();
        for (String word : words) {
            trie.add(word);
        }

        int len = words[0].length();

        for (String word : words) {
            List<String> curr = new ArrayList<>();
            curr.add(word);
            wordSquaresHelper(1, len, curr, trie, ans);
            curr.remove(curr.size() - 1);
        }

        return ans;
    }

    private void wordSquaresHelper(int start, int len, List<String> curr, Trie trie, List<List<String>> ans) {
        if (start >= len) {
            ans.add(new ArrayList<>(curr));
            return;
        }

        StringBuilder prefix = new StringBuilder();
        for (int i = 0; i < start; i++) {
            prefix.append(curr.get(i).charAt(start));
        }

        List<String> candidates = trie.getPrefixStrs(prefix.toString());
        
        for (String candidate : candidates) {
            System.out.println("candidate: " + candidate);
        }

        for (String candidate : candidates) {
            curr.add(candidate);
            wordSquaresHelper(start + 1, len, curr, trie, ans);
            curr.remove(curr.size() - 1);
        }
    }
}

class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void add(String s) {
        TrieNode p = root;

        for (char c : s.toCharArray()) {
            if (p.children[c - 'a'] == null) {
                p.children[c - 'a'] = new TrieNode();
            }

            p = p.children[c - 'a'];
        }

        p.leaf = true;
    }

    public List<String> getPrefixStrs(String prefix) {
        TrieNode p = root;

        List<String> ans = new ArrayList<>();
        for (char c : prefix.toCharArray()) {
            if (p.children[c - 'a'] == null) {
                return ans;
            }
            p = p.children[c - 'a'];
        }

        StringBuilder sb = new StringBuilder(prefix);
        getPrefixHelper(p, sb, ans);

        return ans;
    }

    private void getPrefixHelper(TrieNode p, StringBuilder curr, List<String> ans) {
        if (p == null) {
            return;
        }

        if (p.leaf) {
            ans.add(curr.toString());
            return;
        }

        for (int i = 0; i < 26; i++) {
            if (p.children[i] != null) {
                curr.append((char) (i + 'a'));
                getPrefixHelper(p.children[i], curr, ans);
                curr.deleteCharAt(curr.length() - 1);
            }
        }
    }
}

class TrieNode {
    TrieNode[] children;
    boolean leaf;

    public TrieNode() {
        children = new TrieNode[26];
        leaf = false;
    }
}

An even better solution:
To find all the words with the prefix is an expensive operation. A better solution is to cache the word in all nodes.

Code (Java):
/**
* This reference program is provided by @jiuzhang.com
* Copyright is reserved. Please indicate the source for forwarding
*/

public class Solution {
     class TrieNode {
        List<String> startWith;
        TrieNode[] children;

        TrieNode() {
            startWith = new ArrayList<>();
            children = new TrieNode[26];
        }
    }

    class Trie {
        TrieNode root;

        Trie(String[] words) {
            root = new TrieNode();
            for (String w : words) {
                TrieNode cur = root;
                for (char ch : w.toCharArray()) {
                    int idx = ch - 'a';
                    if (cur.children[idx] == null)
                        cur.children[idx] = new TrieNode();
                    cur.children[idx].startWith.add(w);
                    cur = cur.children[idx];
                }
            }
        }

        List<String> findByPrefix(String prefix) {
            List<String> ans = new ArrayList<>();
            TrieNode cur = root;
            for (char ch : prefix.toCharArray()) {
                int idx = ch - 'a';
                if (cur.children[idx] == null)
                    return ans;

                cur = cur.children[idx];
            }
            ans.addAll(cur.startWith);
            return ans;
        }
    }

    public List<List<String>> wordSquares(String[] words) {
        List<List<String>> ans = new ArrayList<>();
        if (words == null || words.length == 0)
            return ans;
        int len = words[0].length();
        Trie trie = new Trie(words);
        List<String> ansBuilder = new ArrayList<>();
        for (String w : words) {
            ansBuilder.add(w);
            search(len, trie, ans, ansBuilder);
            ansBuilder.remove(ansBuilder.size() - 1);
        }

        return ans;
    }

    private void search(int len, Trie tr, List<List<String>> ans,
            List<String> ansBuilder) {
        if (ansBuilder.size() == len) {
            ans.add(new ArrayList<>(ansBuilder));
            return;
        }

        int idx = ansBuilder.size();
        StringBuilder prefixBuilder = new StringBuilder();
        for (String s : ansBuilder)
            prefixBuilder.append(s.charAt(idx));
        List<String> startWith = tr.findByPrefix(prefixBuilder.toString());
        for (String sw : startWith) {
            ansBuilder.add(sw);
            search(len, tr, ans, ansBuilder);
            ansBuilder.remove(ansBuilder.size() - 1);
        }
    }
}

Saturday, March 16, 2019

Lintcode 432. Find the Weak Connected Component in the Directed Graph

Find the number Weak Connected Component in the directed graph. Each node in the graph contains a label and a list of its neighbors. (a weak connected component of a directed graph is a maximum subgraph in which any two vertices are connected by direct edge path.)

Example

Example 1:
Input: {1,2,4#2,4#3,5#4#5#6,5}
Output: [[1,2,4],[3,5,6]]
Explanation:
  1----->2    3-->5
   \     |        ^
    \    |        |
     \   |        6
      \  v
       ->4
Example 2:
Input: {1,2#2,3#3,1}
Output: [[1,2,3]]

Notice

Sort the elements of a component in ascending order.
Code (Java):
/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 * };
 */


public class Solution {
    /*
     * @param nodes: a array of Directed graph node
     * @return: a connected set of a directed graph
     */
    public List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nodes == null || nodes.size() == 0) {
            return ans;
        }
        
        // note: the label is not from 1 to n
        //
        Set<Integer> set = new HashSet<>();
        
        for (DirectedGraphNode node : nodes) {
            set.add(node.label);
            for (DirectedGraphNode neighbor : node.neighbors) {
                set.add(neighbor.label);
            }
        }
        
        UF uf = new UF(set);

        // union find
        //
        for (DirectedGraphNode node : nodes) {
            int labelA = node.label;
            for (DirectedGraphNode neighbor : node.neighbors) {
                int labelB = neighbor.label;
                
                int rootA = uf.find(labelA);
                int rootB = uf.find(labelB);
                
                if (rootA != rootB) {
                    uf.union(rootA, rootB);
                }
            }
        }
        
        return uf.getCC();
    }
    
}

class UF {
    Map<Integer, Integer> parents;
    Set<Integer> set;
    
    public UF(Set<Integer> set) {
        this.parents = new HashMap<>();
        this.set = set;
        
        for (int num : set) {
            parents.put(num, num);
        }
    }
    
    public int find(int a) {
        int root = a;
        
        while (root != parents.get(root)) {
            root = parents.get(root);
        }
        
        while (root != a) {
            int temp = parents.get(a);
            parents.put(a, root);
            a = temp;
        }
        
        return root;
    }
    
    public void union(int a, int b) {
        parents.put(b, a);
    }
    
    public List<List<Integer>> getCC() {
        List<List<Integer>> ans = new ArrayList<>();
        Map<Integer, List<Integer>> map = new HashMap<>();

        
        for (int i : set) {
            int root = find(i);
            List<Integer> list = map.getOrDefault(root, new ArrayList<>());
            list.add(i);
            map.put(root, list);
        }
        
        for (int key : map.keySet()) {
            List<Integer> list = map.get(key);
            Collections.sort(list);
            ans.add(list);
        }
        
        return ans;
    }
}

Analysis:
Note that we should build the result of CC at last. That's because the root of a node might change along with connecting the nodes. 

Why note DFS for this problem? That's because it's a directed graph. We need to change to undirected graph first in order to use DFS.

Lintcode 477. Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O''s into 'X''s in that surrounded region.

Example

Example 1:
Input:
  X X X X
  X O O X
  X X O X
  X O X X
Output:
  X X X X
  X X X X
  X X X X
  X O X X
Example 2:
Input:
  X X X X
  X O O X
  X O O X
  X O X X
Output:
  X X X X
  X O O X
  X O O X
  X O X X

Code (Java):
public class Solution {
    /*
     * @param board: board a 2D board containing 'X' and 'O'
     * @return: nothing
     */
    public void surroundedRegions(char[][] board) {
        if (board.length == 0 || board[0].length == 0) {
            return;
        }

        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];

        for (int i = 0; i < n; i++) {
            surroundedRegionsHelper(0, i, board, visited);
            surroundedRegionsHelper(m - 1, i, board, visited);
        }

        for (int i = 1; i < m - 1; i++) {
            surroundedRegionsHelper(i, 0, board, visited);
            surroundedRegionsHelper(i, n - 1, board, visited);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == 'Y') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    private void surroundedRegionsHelper(int row, int col, char[][] board, boolean[][] visited) {
        int m = board.length;
        int n = board[0].length;

        if (row < 0 || row >= m || col < 0 || col >= n || visited[row][col]) {
            return;
        }

        if (board[row][col] == 'X') {
            return;
        }

        visited[row][col] = true;
        board[row][col] = 'Y';

        int[][] dirs = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
        for (int i = 0; i < 4; i++) {
            surroundedRegionsHelper(row + dirs[i][0], col + dirs[i][1], board, visited);
        }
    }
}

Lintcode 559. Trie Service

Build tries from a list of <word, freq> pairs. Save top 10 for each node.

Example

Example1
Input:  
 <"abc", 2>
 <"ac", 4>
 <"ab", 9>
Output:<a[9,4,2]<b[9,2]<c[2]<>>c[4]<>>> 
Explanation:
   Root
             / 
           a(9,4,2)
          /    \
        b(9,2) c(4)
       /
     c(2)
Example2
Input:  
<"a", 10>
<"c", 41>
<"b", 50>
<"abc", 5>
Output: <a[10,5]<b[5]<c[5]<>>>b[50]<>c[41]<>>

Code (Java):
/**
 * Definition of TrieNode:
 * public class TrieNode {
 *     public NavigableMap<Character, TrieNode> children;
 *     public List<Integer> top10;
 *     public TrieNode() {
 *         children = new TreeMap<Character, TrieNode>();
 *         top10 = new ArrayList<Integer>();
 *     }
 * }
 */
public class TrieService {

    private TrieNode root = null;

    public TrieService() {
        root = new TrieNode();
    }

    public TrieNode getRoot() {
        // Return root of trie root, and 
        // lintcode will print the tree struct.
        return root;
    }

    // @param word a string
    // @param frequency an integer
    public void insert(String word, int frequency) {
        TrieNode p = root;
        for (char c : word.toCharArray()) {
            TrieNode child = p.children.getOrDefault(c, new TrieNode());
            PriorityQueue<Integer> pq = new PriorityQueue<>(child.top10);
            if (pq.size() < 10) {
                pq.offer(frequency);
            } else {
                if (frequency > pq.peek()) {
                    pq.poll();
                    pq.offer(frequency);
                }
            }

            List<Integer> sortedList = new ArrayList<>(pq);
            Collections.sort(sortedList, Collections.reverseOrder());
            child.top10 = sortedList;
            p.children.put(c, child);
            p = child;
        }
    }
}

Friday, March 15, 2019

Lintcode 629. Minimum Spanning Tree

Given a list of Connections, which is the Connection class (the city name at both ends of the edge and a cost between them), find some edges, connect all the cities and spend the least amount.
Return the connects if can connect all the cities, otherwise return empty list.

Example

Gievn the connections = ["Acity","Bcity",1], ["Acity","Ccity",2], ["Bcity","Ccity",3]
Return ["Acity","Bcity",1], ["Acity","Ccity",2]

Notice

Return the connections sorted by the cost, or sorted city1 name if their cost is same, or sorted city2 if their city1 name is also same.

Solution:
Classic Kruskal algorithm, which is a greedy algorithm. The key idea is sort the connections by the cost. Then connect all the cities using Union-Find. Since we use the edges with the minimal costs first, and the Union-Find will result in a tree. After we connect all the edges, we will end with a minimum spanning tree. 

Code (Java):
/**
 * Definition for a Connection.
 * public class Connection {
 *   public String city1, city2;
 *   public int cost;
 *   public Connection(String city1, String city2, int cost) {
 *       this.city1 = city1;
 *       this.city2 = city2;
 *       this.cost = cost;
 *   }
 * }
 */
public class Solution {
    /**
     * @param connections given a list of connections include two cities and cost
     * @return a list of connections from results
     */
    public List<Connection> lowestCost(List<Connection> connections) {
        List<Connection> ans = new ArrayList<>();
        if (connections == null || connections.size() == 0) {
            return ans;
        }

        Collections.sort(connections, new MyConnectionComparator());

        int count = 0;
        Map<String, Integer> map = new HashMap<>();
        for (Connection connection : connections) {
            if (!map.containsKey(connection.city1)) {
                map.put(connection.city1, count++);
            }

            if (!map.containsKey(connection.city2)) {
                map.put(connection.city2, count++);
            }
        }

        int[] parents = new int[count];
        for (int i = 0; i < count; i++) {
            parents[i] = i;
        }

        for (Connection connection : connections) {
            int rootA = find(map.get(connection.city1), parents);
            int rootB = find(map.get(connection.city2), parents);

            if (rootA != rootB) {
                parents[rootA] = rootB;
                ans.add(connection);
            }
        }

        return ans.size() == count - 1 ? ans : new ArrayList<>();
    }

    private int find(int a, int[] parents) {
        int root = a;
        while (root != parents[root]) {
            root = parents[root];
        }

        while (root != a) {
            int temp = parents[a];
            parents[a] = root;
            a = temp;
        }

        return root;
    }
}

class MyConnectionComparator implements Comparator<Connection> {
    @Override
    public int compare(Connection a, Connection b) {
        if (a.cost != b.cost) {
            return a.cost - b.cost;
        }
        
        if (!a.city1.equals(b.city1)) {
            return a.city1.compareTo(b.city1);
        }
        
        return a.city2.compareTo(b.city2);
    }
}

Lintcode 434. Number of Islands II

Given a n,m which means the row and column of the 2D matrix and an array of pair A( size k). Originally, the 2D matrix is all 0 which means there is only sea in the matrix. The list pair has k operator and each operator has two integer A[i].x, A[i].y means that you can change the grid matrix[A[i].x][A[i].y] from sea to island. Return how many island are there in the matrix after each operator.

Example

Example 1:
Input: n = 4, m = 5, A = [[1,1],[0,1],[3,3],[3,4]]
Output: [1,1,2,2]
Explanation:
0.  00000
    00000
    00000
    00000
1.  00000
    01000
    00000
    00000
2.  01000
    01000
    00000
    00000
3.  01000
    01000
    00000
    00010
4.  01000
    01000
    00000
    00011
Example 2:
Input: n = 3, m = 3, A = [[0,0],[0,1],[2,2],[2,1]]
Output: [1,1,2,2]

Notice

0 is represented as the sea, 1 is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.

Code (Java):
public class Solution {
    private int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int numCC = 0;

    public List<Integer> numIslands2(int n, int m, Point[] operators) {
        List<Integer> ans = new ArrayList<>();
        
        if (operators == null || operators.length == 0) {
            return ans;
        }

        int[] parents = new int[n * m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                parents[i * m + j] = i * m + j;
            }
        }

        Set<Integer> islands = new HashSet<>();

        for (Point point : operators) {
            if (!islands.contains(point.x * m + point.y)) {
                islands.add(point.x * m + point.y);
                numCC++;
                for (int i = 0; i < 4; i++) {
                    connect(point.x, point.y, point.x + dirs[i][0], point.y + dirs[i][1], n, m, islands, parents);
                }
            }
            ans.add(numCC);
        }
        return ans;
    }

    private void connect(int ax, int ay, int bx, int by, int n, int m, Set<Integer>islands, int[] parents) {
        if (bx < 0 || bx >= n || by < 0 || by >= m) {
            return;
        }

        if (!islands.contains(bx * m + by)) {
            return;
        }

        int rootA = find(ax, ay, n, m, parents);
        int rootB = find(bx, by, n, m, parents);

        if (rootA != rootB) {
            parents[rootB] = rootA;
            numCC--;
        }
    }

    private int find(int x, int y, int n, int m, int[] parents) {
        int p = x * m + y;
        int root = p;

        while (root != parents[root]) {
            root = parents[root];
        }

        // path compression
        //
        while (root != p) {
            int temp = parents[p];
            parents[p] = root;
            p = temp;
        }

        return root;
    }
}