LeetCode 1766 - Tree of Coprimes


https://ophaxor.com/leetcode-1766-tree-of-coprimes

There is a tree (i.e., a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. Each node has a value associated with it, and the root of the tree is node 0.

To represent this tree, you are given an integer array nums and a 2D array edges. Each nums[i] represents the ith node’s value, and each edges[j] = [uj, vj] represents an edge between nodes uj and vj in the tree.

Two values x and y are coprime if gcd(x, y) == 1 where gcd(x, y) is the greatest common divisor of x and y.

An ancestor of a node i is any other node on the shortest path from node i to the root. A node is not considered an ancestor of itself.

Return an array ans of size nwhere ans[i] is the closest ancestor to node i such that nums[i] and nums[ans[i]] are coprime, or -1 if there is no such ancestor.

Example 1:

Input: nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
Output: [-1,0,0,1]
Explanation: In the above figure, each node's value is in parentheses.
- Node 0 has no coprime ancestors.
- Node 1 has only one ancestor, node 0. Their values are coprime (gcd(2,3) == 1).
- Node 2 has two ancestors, nodes 1 and 0. Node 1's value is not coprime (gcd(3,3) == 3), but node 0's
  value is (gcd(2,3) == 1), so node 0 is the closest valid ancestor.
- Node 3 has two ancestors, nodes 1 and 0. It is coprime with node 1 (gcd(3,2) == 1), so node 1 is its
  closest valid ancestor.

Example 2:

Input: nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
Output: [-1,0,-1,0,0,0,-1]

Constraints:

  • nums.length == n
  • 1 <= nums[i] <= 50
  • 1 <= n <= 105
  • edges.length == n - 1
  • edges[j].length == 2
  • 0 <= uj, vj < n
  • uj != vj

题意: 对于树上的每个节点,找出与它的值互质的最近的祖先节点。

题解: 由于节点上的值在1-50之间,所以算互质很好算,事先算法。然后就是深度优先遍历树的时候维护路径上的节点的位置,利用1-50这个小范围,快速找到与当前节点值互质的值出现在哪些位置上

https://leetcode.com/problems/tree-of-coprimes/discuss/1074581/Java-or-DFS-or-O(n)

    public int gcd(int n1, int n2) {
        if (n2 == 0) {
            return n1;
        }
        return gcd(n2, n1 % n2);
    }
    
    public void dfs(int[] nums, LinkedList<Integer>[] tree, int depth, int node, boolean[] visited, int[] ans, Map<Integer,int[]> map, boolean[][] poss) {
        if(visited[node]) return;
        visited[node] = true;
        int ancestor = -1;
        int d = Integer.MAX_VALUE;
        for(int i = 1; i < 51; i++) {
            if(poss[nums[node]][i] && map.containsKey(i)) {
                if(depth - map.get(i)[0] <= d) {
                    d = depth - map.get(i)[0];
                    ancestor = map.get(i)[1];
                }
            }
        }
        ans[node] = ancestor;
        int[] exist = (map.containsKey(nums[node])) ? map.get(nums[node]) :  new int[]{-1,-1};
        map.put(nums[node],new int[]{depth,node});
        for(int child : tree[node]) {
            if(visited[child]) continue;
            dfs(nums, tree, depth+1, child, visited, ans, map, poss);
        }
        if(exist[0] != -1) map.put(nums[node], exist);
        else map.remove(nums[node]);
  
        return;
    }
    
    public int[] getCoprimes(int[] nums, int[][] edges) {
        boolean[][] poss = new boolean[51][51];
        for(int i = 1; i < 51; i++) {
            for(int j = 1; j < 51; j++) {
                if(gcd(i,j) == 1) {
                    poss[i][j] = true;
                    poss[j][i] = true;
                }
            }
        }
        int n = nums.length;
        LinkedList<Integer>[] tree = new LinkedList[n];
       
        for(int i =0 ; i < tree.length; i++) tree[i] = new LinkedList<>();
        for(int edge[] : edges) {
            tree[edge[0]].add(edge[1]);
            tree[edge[1]].add(edge[0]);
        }
        
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        ans[0] = -1;
        Map<Integer,int[]> map = new HashMap<>();
        
        boolean[] visited = new boolean[n];
        dfs(nums, tree, 0, 0, visited, ans, map, poss);
        return ans;
    }       

https://leetcode.com/problems/tree-of-coprimes/discuss/1074737/Python-3-DFS-Clean-and-Concise

  • Time: O(50 * N)
  • Space: O(N)
  • Please notice in the constraints that all node values is in range 1..50.
  • We create an array of 51 elements path[51] where path[x] contains list of nodes from root to current node which their node's value are equal to x.
  • While traversing nodes using DFS, for current node we can check all paths path[x] (up to 50) where x and current node are co-prime then we try to pick the node which is close to current node as our ancestor.
  • A node is close to current node if its depth is largest.

    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:
        ans = [-1] * len(nums)
        path = [[] for _ in range(51)]
        graph = defaultdict(list)
        seen = set()
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        def dfs(node, depth):
            if node in seen: return
            seen.add(node)
            largestDepth = -1
            for x in range(1, 51):
                if gcd(nums[node], x) == 1: # co-prime
                    if len(path[x]) > 0:
                        topNode, topDepth = path[x][-1]
                        if largestDepth < topDepth:  # Pick node which has largestDepth and co-prime with current node as our ancestor node
                            largestDepth = topDepth
                            ans[node] = topNode
            path[nums[node]].append((node, depth))
            for nei in graph[node]:
                dfs(nei, depth + 1)
            path[nums[node]].pop()

        dfs(0, 0)
        return ans

https://easyforces.com/solutions/1766/

Like many other problems, let's figure out the input, limitation and output from the description.

  • The input of this problem is a tree where each node has a value. It is given by an array nums representing values of each node. And edges representing the edge between the edge[i][0] and edge[i][1].
  • The limitation is given by the definition Coprime, where the greatest common divisor(GCD) of 2 node values is 1.
  • The required output is the closest coprime anacestor for each node. The result should be returned by an array where result[i] is the index of node i's closest coprime anacestor.
Data Structure

Even if the input is a tree, since we are only given edges, we can use adjacent list to represent the tree, where adj[i] is a list of nodes who is node i's neighbors.

Basic Idea

The basic idea of this problem is to traverse the tree. And during the traversal, for each node, calculate the closest coprime anacestor. Now let's consider the time complexity of this basic solution.

  • To traverse a tree, we can use Depth-first Search (DFS). The basic time complexity of DFS is O(nodes.length + edges.length).
  • For each node, we need to go through all it's ancestors from bottom to top to check if they are coprime. The worst case would be there are no coprime in it's ancestors, and the time complexity of this step would be O(tree.depth). Since the tree is not a balanced tree, for it's depth, we need to consider it's the same as node number, which is O(nodes.length).
  • To check if 2 numbers are coprime, we would need to check all number which is less than or equal to the minimum number between the 2 numbers, to see if it's a common divisor of them. Time complexity of this step is O(num).

The overall time complexity would be:

O((nodes.length + edges.length) * nodes.length * max(nums))

The input range is given in the problem description.

  • nums.length == n
  • 1 <= nums[i] <= 50
  • 1 <= n <= 100,000
  • edges.length == n - 1
  • edges[j].length == 2
  • 0 <= uj, vj < n
  • uj != vj

And the number of operations is:

O( (n + n) * n * len(nums) )
= O( n ** 2 * len(nums) )
= O( (10 ** 10) * 50 )
= O( 10 ** 11 )

This is high above standard which is 1,000,000.

Improvement

The basic solution spend too much time because there are too many operations. In this case, we can consider to pre-calculate something. So the time complexity would be O(pre) + O(solution).

  • One key point of this problem is that the range of each number is between 1 and 50. So

System Message: WARNING/2 (<string>, line 69)

Bullet list ends without a blank line; unexpected unindent.

we could calculate isCoprime for all integer pairs in time O(max(nums) ** 2) = O(2,500).

  • Then, for each node, instead of calculate through all it's ancestors, we maintain a array storing

System Message: WARNING/2 (<string>, line 72)

Bullet list ends without a blank line; unexpected unindent.

the closest anacestor for each number. And update this array for each node. This would only take O(max(nums)).

So now, the time complexity is:

O(max(nums) ** 2) + O(n + n) * O(max(nums))
= O(max(nums) ** 2) + O( n * max(nums) )
= O( max(nums) * (max(nums) + n) )
= O( 50 * (50 + 100,000) )
~= O( 5 * (10 ** 6) )
= O( 5,000,000 )

This would be a just fine time time complexity (around 1,000,000).

About Code
  • The method isCoprime is for calculating whether 2 numbers are coprime.
  • The method _dfs is the main part of the solution, which traverses the tree and calculate the closest coprime ancestor.
  • Variable candidates stores the cloeset coprime ancestor for each possible number, it's maximum length is 50.

X. Videos

English Version in Youtube

中文版解答Youtube Link


LeetCode 1768 - Merge Strings Alternately


http://code.minggr.net/leetcode-1768/

https://leetcode.com/problems/merge-strings-alternately/

You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.

Return the merged string.

Example 1:

Input: word1 = “abc”, word2 = “pqr”
Output: “apbqcr”
Explanation: The merged string will be merged as so:
word1: a b c
word2: p q r
merged: a p b q c r
Example 2:

Input: word1 = “ab”, word2 = “pqrs”
Output: “apbqrs”
Explanation: Notice that as word2 is longer, “rs” is appended to the end.
word1: a b
word2: p q r s
merged: a p b q r s
Example 3:

Input: word1 = “abcd”, word2 = “pq”
Output: “apbqcd”
Explanation: Notice that as word1 is longer, “cd” is appended to the end.
word1: a b c d
word2: p q
merged: a p b q c d

Constraints:

1 <= word1.length, word2.length <= 100
word1 and word2 consist of lowercase English letters.

    string mergeAlternately(string word1, string word2) {
int i = 0, j = 0;

string ans;

while (i < word1.size() && j < word2.size()) {
if ((i+j) % 2 == 0)
ans.push_back(word1[i++]);
else
ans.push_back(word2[j++]);
}

if (i < word1.size())
ans += word1.substr(i);
if (j < word2.size())
ans += word2.substr(j);

return ans;
}

https://leetcode.com/problems/merge-strings-alternately/discuss/1075534/JavaC%2B%2BPython-Straignt-Forward-Solutions

Alternatively append the character from w1 and w2 to res.

Complexity

Time O(n + m)
Space O(n + m)

X. Two Pointers

    public String mergeAlternately(String w1, String w2) {
        int n = w1.length(), m = w2.length(), i = 0, j = 0;
        StringBuilder res = new StringBuilder();
        while (i < n || j < m) {
            if (i < w1.length())
                res.append(w1.charAt(i++));
            if (j < w2.length())
                res.append(w2.charAt(j++));
        }
        return res.toString();
    }

One Pointer

    public String mergeAlternately(String w1, String w2) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < w1.length() || i < w2.length(); ++i) {
            if (i < w1.length())
                res.append(w1.charAt(i));
            if (i < w2.length())
                res.append(w2.charAt(i));
        }
        return res.toString();
    }

https://walkccc.me/LeetCode/problems/1768/

string mergeAlternately(string word1, string word2) { const int n = min(word1.length(), word2.length()); string prefix; for (int i = 0; i < n; ++i) { prefix += word1[i]; prefix += word2[i]; } return prefix + word1.substr(n) + word2.substr(n); }


LeetCode 1769 - Minimum Number of Operations to Move All Balls to Each Box


https://chowdera.com/2021/03/20210326160903226c.html

Give you a length of n Binary string of boxes , among boxes[i] The value of is '0' It means the first one i A box is empty Of , and boxes[i] The value of is '1' There is... In the box One Pellet .

In one step , You can take One The ball moves from a box to an adjacent box . The first i A box and j Two adjacent boxes need to satisfy abs(i - j) == 1 . Be careful , After operation , There may be more than one ball in some boxes .

Returns a length of n Array of answer , among answer[i] It's moving all the balls to the second i What a box needs Minimum Operands .

Every answer[i] It all depends on the box The initial state Calculate .

有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes ,其中 boxes[i] 的值为 '0' 表示第 i 个盒子是 空 的,而 boxes[i] 的值为 '1' 表示盒子里有 一个 小球。

在一步操作中,你可以将 一个 小球从某个盒子移动到一个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需满足 abs(i - j) == 1 。注意,操作执行后,某些盒子中可能会存在不止一个小球。

返回一个长度为 n 的数组 answer ,其中 answer[i] 是将所有小球移动到第 i 个盒子所需的 最小 操作数。

每个 answer[i] 都需要根据盒子的 初始状态 进行计算。

输入:boxes = "110"
输出:[1,1,3]
解释:每个盒子对应的最小操作数如下:
1) 第 1 个盒子:将一个小球从第 2 个盒子移动到第 1 个盒子,需要 1 步操作。
2) 第 2 个盒子:将一个小球从第 1 个盒子移动到第 2 个盒子,需要 1 步操作。
3) 第 3 个盒子:将一个小球从第 1 个盒子移动到第 3 个盒子,需要 2 步操作。将一个小球从第 2 个盒子移动到第 3 个盒子,需要 1 步操作。共计 3 步操作。
示例 2:

输入:boxes = "001011"
输出:[11,8,5,4,3,4]

X. O(n) - left sum and right sum
    public int[] minOperations(String boxes) {
        int n = boxes.length();

        int[] left = new int[n];
        int[] right = new int[n];
        int[] ans = new int[n];

        int count = boxes.charAt(0) - '0';
        for(int i = 1 ; i < n ; i++){
            left[i] = left[i - 1] + count;
            count += boxes.charAt(i) - '0';
        }

        count = boxes.charAt(n - 1) - '0';
        for(int i = n - 2 ; i >=0 ; i--){
            right[i] = right[i + 1] + count;
            count += boxes.charAt(i) - '0';
        }
		
        for(int i = 0 ; i < n ; i++) {
            ans[i] = left[i] + right[i];
        }

        return ans;
    }
You can just get rid of the temp arrays. As problem asks us to return a new answer array, we won't consider that space in complexity analysis and hence space complexity is constant.
  public int[] minOperations(String boxes) {        
        int[] ans = new int[boxes.length()];
		int cnt = boxes.charAt(0) - '0';
		for(int i=1;i<boxes.length(); i++) {
			ans[i] = ans[i-1] + cnt;
			cnt += boxes.charAt(i) - '0';
		}
		
		int runner = 0; 
		cnt = boxes.charAt(boxes.length()-1) - '0';
		for(int i=boxes.length()-2;i>=0; i--) {
			runner += cnt; 
			ans[i] += runner;
			cnt += boxes.charAt(i) - '0'; 
		}
        return ans;  
  }
public int[] minOperations(String boxes) {
    int left = 0, right = 0, lsum = 0, rsum = 0, len = boxes.length();
	for (int i = 0; i < len; i++) {
		if (boxes.charAt(i) == '1') {
			right++;
			rsum += i;
		}
	}

	int[] ans = new int[len];

	for (int i = 0; i < len; i++) {
		ans[i] = lsum + rsum;
		if (boxes.charAt(i) == '1') {
			left++;
			right--;
		}
		lsum = lsum + left;
		rsum = rsum - right;
	}

	return ans;
}

We first "move" balls from left to right, and track how many ops it takes for each box.

For that, we count how many balls we got so far in cnt, and accumulate it in ops.

Then, we do the same from right to left.

public int[] minOperations(String boxes) {
    int[] res = new int[boxes.length()];
    for (int i = 0, ops = 0, cnt = 0; i < boxes.length(); ++i) {
       res[i] += ops;
       cnt += boxes.charAt(i) == '1' ? 1 : 0;
       ops += cnt;
    }    
    for (int i = boxes.length() - 1, ops = 0, cnt = 0; i >= 0; --i) {
        res[i] += ops;
        cnt += boxes.charAt(i) == '1' ? 1 : 0;
        ops += cnt;
    }
    return res;
}

What needs to be considered is , How to move to by all x The number of operations answer[x] Find all move to x+1 The number of operations answer[x+1]. about x+1 The ball on the left , Each ball will be operated once more , about x The ball on the right , Each will operate less than once . So , You just have to figure out x+1 The number of balls on the left side left(x+1) and x The number of balls on the right right(x) that will do . That is to say answer[x+1]=answer[x]+left(x+1)-right(x).

At present, we don't have to ask for it every time left and right, Save the position of the ball in line , Compare the current position and x,x+1 The relationship between , It can be calculated directly left and right The change of , But this code is easier to understand . You can try to optimize it yourself .

vector<int> minOperations(string boxes) { vector<int> positions; int n = boxes.size(); vector<int> answer(n, 0); for (int i = 0; i < n; i++) { if (boxes[i] == '1') { positions.push_back(i); if (i) answer[0] += i; } } for (int i = 1; i < n; i++) { // answer[i]=answer[i-1]+left(i)-right(i-1) int left = lower_bound(positions.begin(), positions.end(), i) - positions.begin(); int right = positions.end() - upper_bound(positions.begin(), positions.end(), i - 1); answer[i] = answer[i - 1] + left - right; } return answer; }

https://www.taodudu.cc/news/show-2114813.html

这个思路是:我们先找到把所有的 1 移到下标为 0 的起始位置需要的最小操作数为 r e s [ 0 ] res[0] res[0]。然后其余把所有 1 移到 i i i 位置的操作数 = 把所有 1 移到 i − 1 i - 1 i1 位置的的操作数 -(右边的所有 1) + (左边的所有 1),即转移方程是:

r e s [ i ] = r e s [ i − 1 ] − ( o n e s − v i s i t e d ) + v i s i t e d res[i] = res[i - 1] - (ones - visited) + visited res[i]=res[i1](onesvisited)+visited

原理是什么呢?因为把所有位置移动到 r e s [ i ] res[i] res[i] 位置相对于 r e s [ i − 1 ] res[i - 1] res[i1] 位置来说,所有它右边位置的 1 少移动了一次,它左边位置的 1 多移动了一次。

时间复杂度: O ( N ) O(N) O(N),空间复杂度: O ( 1 ) O(1) O(1).

https://shareablecode.com/snippets/minimum-number-of-operations-to-move-all-balls-to-each-box-c-solution-leetcode-u8Vu-zhvF

    vector<int> minOperations(string boxes) {
        vector<int> result(size(boxes)); 
        for (int i = 0, accu = 0, cnt = 0; i < size(boxes); ++i) {
           result[i] += accu;
           cnt += (boxes[i] == '1') ? 1 : 0;
           accu += cnt;
        }
        for (int i = size(boxes) - 1, accu = 0, cnt = 0; i >= 0; --i) {
            result[i] += accu;
            cnt += (boxes[i] == '1') ? 1 : 0;
            accu += cnt;
        }
        return result;
    }

X.

https://www.taodudu.cc/news/show-2114813.html

本题的数据规模为 2000,用 O ( N 2 ) O(N^2) O(N2) 的解法竟然能过。这个方法比较简单,直接对每个位置向左右两边统计具体各个 1 的位置之和。

    def minOperations(self, boxes: str) -> List[int]:
        N = len(boxes)
        res = [0] * N
        for i in range(N):
            left = [i - j for j in range(i) if boxes[j] == "1"]
            right = [j - i for j in range(i + 1, N) if boxes[j] == "1"]
            res[i] = sum(left) + sum(right)
        return res

https://kickstart.best/1769-minimum-number-of-operations-to-move-all-balls-to-each-box/

vector<int> minOperations(string boxes) {
int n = boxes.size();
vector<int> ret(n, 0);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
if(boxes[j] == '1') {
ret[i] += abs(i - j);
}
}
}
return ret;
}


Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts