Union Find

From wiki:
In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. It supports two useful operations:
Find: Determine which subset a particular element is in. Find typically returns an item from this set that serves as its “representative”; by comparing the result of two Find operations, one can determine whether two elements are in the same subset.
Union: Join two subsets into a single subset.

Example:
261. Graph Valid Tree
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Hint:
Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?
According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

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

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < edges.length; i++) {
            if (!uf.union(edges[i][0], edges[i][1])) {
                return false;
            }
        }
        return uf.size == 1;
    }
    
    private class UnionFind {
        int size;
        int[] nodes;
        
        UnionFind(int size) {
            this.size = size;
            this.nodes = new int[size];
            for (int i = 0; i < size; i++) {
                nodes[i] = i;
            }
        }
        
        boolean union(int a, int b) {
            int label_a = nodes[a];
            int label_b = nodes[b];
            if (label_a == label_b) {
                return false;
            } else {
                for (int i = 0; i < nodes.length; i++) {
                    if (nodes[i] == label_a) {
                        nodes[i] = label_b;
                    }
                }
                size--;
                return true;
            }
        }
    }
}

Read More

Single Number

XOR features:
a ^ b = c
a ^ c = b
b ^ c = a
a ^ 0 = a
a ^ a = 0
(a ^ b) ^ c = a ^ (b ^ c)

• I: all the numbers appear twice except one
  XOR all the numbers, and the result is the one
• II: all the numbers appear three times except one
  Use a int[32] to store each bit, if the number of this bit can be mod by 3, we set it as 0, otherwise we set it as 1.
• III: all the numbers appear twice except two
  XOR all the numbers so we can get the two by XOR. Since these two elements are not the same, there is at least one bit that different. We find this different position and XOR all the elements which have 1 on position different, the result is one of the two. Finally, we XOR the found one with XOR-ed two, we can get another one.

Majority Number

• I: find the number appears more than half
  Since it is a strict majority number, we only need to maintain a variable result and a counter. Initially, when the counter faces with a different number, minus one of counter and change the result to this new number, otherwise we only need to add 1 to the counter. And finally, the result we maintained is the result. (We need to do another pass to make sure this number is the one we are looking for)
• II: find the number appears more than 1/3
  Similar with I, we maintain two variables and two counters so that we can get most appeared two numbers. And then we put these two numbers back to the array to find out which one appears more than 1/3. (We can’t use counter to find out, because counters have minus operation during the traversal)
• III: find the number appears more than 1/k
  We maintain a HashMap<number, counter>. Since if majority, each k different numbers should have more than one element. When we get k entries in the map, we remove entries which values are 1. Finally, find the entry that have highest value(count), that key should be the majority number. In this way, we can implement this in O(n) time and O(k) extra space.

  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

  public class Solution { public int majorityNumber(ArrayList<Integer> nums, int k) { if(nums == null || nums.size() == 0) { return -1; } HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for(int num : nums) { if(map.containsKey(num)) { map.put(num, map.get(num) + 1); } else { // if there are k entries, check if there are any entries that // its value == 1, that is not satisfied with "more than 1/k" if(map.size() == k) { Iterator<Map.Entry<Integer, Integer>> iter = map.entrySet().iterator(); while(iter.hasNext()) { Map.Entry<Integer, Integer> entry = iter.next(); if(entry.getValue() - 1 == 0) { // can't use: map.remove(entry.getKey()); // above wrong code would lead the iter can't find its next !!! iter.remove(); } else { map.put(entry.getKey(), entry.getValue() - 1); } } } else { map.put(num, 1); } } } // find the one that have highest value(count), that key should be the majority number int value = 0; int result = -1; for(Map.Entry<Integer, Integer> entry : map.entrySet()) { if(entry.getValue() > value) { value = entry.getValue(); result = entry.getKey(); } } return result; } }

Read More

Data Structure is a way to organize data. It provides some methods to handle data stream, e.g. insert, delete, etc.

Linear Data Structure

Queue & Stack

Min Stack
Use two stacks, one is storing the input, when calling pop() or peek(), pop from another stack, which stores the minimum values from top to bottom.

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

class MinStack {
    ArrayList<Integer> stack = new ArrayList<Integer>();
    ArrayList<Integer> minStack = new ArrayList<Integer>();
    public void push(int x) {
        stack.add(x);
        if(minStack.isEmpty() || minStack.get(minStack.size() - 1) >= x) {
            minStack.add(x);
        }
        return;
    }

    public void pop() {
        if(stack.isEmpty()) {
            return;
        }
        int elem = stack.remove(stack.size() - 1);
        if(!minStack.isEmpty() && minStack.get(minStack.size() - 1) == elem) {
            minStack.remove(minStack.size() - 1);
        }
        return;
    }

    public int top() {
        if(!stack.isEmpty()) {
            return stack.get(stack.size() - 1);
        }
        return 0;
    }

    public int getMin() {
        if(!minStack.isEmpty()) {
            return minStack.get(minStack.size() - 1);
        }
        return 0;
    }
}

Implement Queue by stacks
Use two stacks, one is for storing elements. When calling pop() or top(), pop the elements from the first stack and push them into the second one.

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

public class Solution {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public Solution() {
       // do initialization
       stack1 = new Stack<Integer>();
       stack2 = new Stack<Integer>();
    }
    
    public void push(int element) {
        stack1.push(element);
    }

    public int pop() {
        if(stack2.isEmpty()) {
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int top() {
        if(stack2.isEmpty()) {
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
}

Largest Rectangle in Histogram
Brute force: totally O(n^2) windows and O(n) to find the minimun one in each window, so we need O(n^3) time.
Improve: for each number, search both side of it until find two smaller number, calculate the result, O(n^2) cost.
Best: use a stack to store the index (all increased heights), when faced with a smaller one, pop out from tha stack and calculate the area until the value bigger than the peek() one. This method cost O(n) time, with O(n) space in worst case (two passes).

Read More

Clone Graph

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

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null) {
            return null;
        }

        LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
        HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
        queue.offer(node);
        map.put(node, new UndirectedGraphNode(node.label));

        while(!queue.isEmpty()) {
            UndirectedGraphNode cur = queue.poll();
            for(int i = 0; i < cur.neighbors.size(); i++) {
                // !!! if node not in map, add a new node into the map !!!
                if(!map.containsKey(cur.neighbors.get(i))) {
                    map.put(cur.neighbors.get(i), new UndirectedGraphNode(cur.neighbors.get(i).label));
                    queue.offer(cur.neighbors.get(i));
                }
                // now we are sure that the node is existed, add the neighbors to the value
                map.get(cur).neighbors.add(map.get(cur.neighbors.get(i)));
            }
        }

        return map.get(node);
    }
}

Topological Sorting
DFS: O(n) time with O(n) space for the map and the result.

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

/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 * };
 */
public class Solution {
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */    
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        ArrayList<DirectedGraphNode> result = new ArrayList<DirectedGraphNode>();
        if(graph == null || graph.size() == 0) {
            return result;
        }
        // construct map with all nodes
        HashMap<DirectedGraphNode, Integer> map = new HashMap<DirectedGraphNode, Integer>();
        for(DirectedGraphNode node: graph) {
            // mark 0 as unsorted
            map.put(node, 0);
        }
        // find a new unsorted node to start sorting (if possible):
        while (hasUnsorted(map, graph)) {
            DirectedGraphNode node = null;
            for (DirectedGraphNode temp : graph) {
                if (map.get(temp) == 0) {
                    node = temp;
                }
            }
            // get the node and do sort(search):
            sort(map, graph, result, node);
        }
        return result;
    }
    
    // check if there is any node that not yet been sorted
    public boolean hasUnsorted(Map<DirectedGraphNode, Integer> map, ArrayList<DirectedGraphNode> graph){
        for (DirectedGraphNode node : graph) {
            if (map.get(node) == 0) {
                return true;
            }
        }
        return false;
    }
    
    // search and sort the graph
    public void sort(Map<DirectedGraphNode, Integer> map, ArrayList<DirectedGraphNode> graph, ArrayList<DirectedGraphNode> result, DirectedGraphNode node){
        if (map.get(node) != 0) {
            // if 1: System.out.println("It is not a DAG");
            // if 2: sorted
            return;
        }
        // mark 1 as visited(not yet been sorted), do with its neighbors:
        map.put(node, 1);
        for (DirectedGraphNode next : node.neighbors) {
            sort(map, graph, result, next);
        }
        // mark 2 as sorted
        // map.put(node, 2);
        result.add(0, node);
    }
}

Read More

1. Dynamic Programming

A method for solving a complex problem by breaking it down into a collection of simpler sub-problems.

1.1 When to use

1. One of the following three:

• Maximum/Minimum Problem
• Yes or No Question
• Count all possible solutions

2. Can’t do sort or swap operation

Note: DP can’t return all results, it only returns max/min, yes/no or a certain value(like length, possible solutions, etc.).

1.2 How to think

1. States: what we need to store for each sub-problem (usually an array).
2. Function: what is the relationship between each state.
3. Intialization: what is the start of each state.
4. Answer: what is the end of each state.

Example: Number Triangle
We use an array f[i][j] to record the minimum sum from (0, 0) to (i, j). For a certain (i, j), we know it is either from (i - 1, j - 1) or (i - 1, j). So the sub-problem is to traverse all elements in the triangle and calculate all the f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + T[i]][j]. The result will be the minimum one in f[n - 1][0, ..., n - 1].
We can also do it from bottom up. First we find the minimum of each pair in the last row, then we do above similarly but from bottom up. Finally the only one element left in the array is the result we are looking for.
A bonus point is doing this using only O(n) extra space, where n is the total number of rows in the triangle. Since each time we calculate f[i][j], the result is only related with f[i - 1][], we can only use 1D array and update the elements in it in each for loop.
Here is the code from bottom up with O(n) space cost.

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

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size() == 0) {
            return 0;
        }

        int[] result = new int[triangle.size() + 1];
        
        for(int row = triangle.size() - 1; row >= 0; row--) {
            for(int col = 0; col <= row; col++) {
                result[col] = Math.min(result[col], result[col + 1]) + triangle.get(row).get(col);
            }
        }
        
        return result[0];
    }
}

Dynamic Programming uses extra space to remember the mid-result. So that it is more efficient than recursive searching, which may repeated calculate the same mid-result for many times. In the above example, if we do a brute force search, it cost O(2^n) time, where n is the height of the triangle (each row, we need to choose one from two, totally n rows). But it only costs O(n^2) in theoretical(m rows, each row has n elements, totally n^2) or O(n), which means all numbers we only need to visit once.

Read More