LeetCode 236 - Lowest Common Ancestor in a Binary Tree


Related: LeetCode 236 - Lowest Common Ancestor in a Binary Tree
LeetCode 235 - Lowest Common Ancestor of a Binary Search Tree (BST)
Lowest Common Ancestor in a Binary Tree | Set 1 | GeeksforGeeks
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree:  root = [3,5,1,6,2,0,8,null,null,7,4]


Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

X. 
http://rainykat.blogspot.com/2017/01/leetcode-236-lowest-common-ancestor-of.html
recursion: The idea is to traverse the tree starting from root. If any of the given keys (n1 and n2) matches with root, then root is LCA (assuming that both keys are present). If root doesn’t match with any of the keys, we recur for left and right subtree. The node which has one key present in its left subtree and the other key present in right subtree is the LCA. If both keys lie in left subtree, then left subtree has LCA also, otherwise LCA lies in right subtree
这道求二叉树的最小共同父节点的题是之前那道 Lowest Common Ancestor of a Binary Search Tree 的Follow Up。跟之前那题不同的地方是，这道题是普通是二叉树，不是二叉搜索树，所以就不能利用其特有的性质，所以我们只能在二叉树中来搜索p和q，然后从路径中找到最后一个相同的节点即为父节点，我们可以用递归来实现，在递归函数中，我们首先看当前结点是否为空，若为空则直接返回空，若为p或q中的任意一个，也直接返回当前结点。否则的话就对其左右子结点分别调用递归函数，由于这道题限制了p和q一定都在二叉树中存在，那么如果当前结点不等于p或q，p和q要么分别位于左右子树中，要么同时位于左子树，或者同时位于右子树，那么我们分别来讨论：
若p和q要么分别位于左右子树中，那么对左右子结点调用递归函数，会分别返回p和q结点的位置，而当前结点正好就是p和q的最小共同父结点，直接返回当前结点即可，这就是题目中的例子1的情况。
若p和q同时位于左子树，这里有两种情况，一种情况是left会返回p和q中较高的那个位置，而right会返回空，所以我们最终返回非空的left即可，这就是题目中的例子2的情况。还有一种情况是会返回p和q的最小父结点，就是说当前结点的左子树中的某个结点才是p和q的最小父结点，会被返回。
若p和q同时位于右子树，同样这里有两种情况，一种情况是right会返回p和q中较高的那个位置，而left会返回空，所以我们最终返回非空的right即可，还有一种情况是会返回p和q的最小父结点，就是说当前结点的右子树中的某个结点才是p和q的最小父结点，会被返回
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q)  return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null)   return root;
        return left != null ? left : right;
    }


上述代码可以进行优化一下，如果当前结点不为空，且既不是p也不是q，那么根据上面的分析，p和q的位置就有三种情况，p和q要么分别位于左右子树中，要么同时位于左子树，或者同时位于右子树。我们需要优化的情况就是当p和q同时为于左子树或右子树中，而且返回的结点并不是p或q，那么就是p和q的最小父结点了，已经求出来了，就不用再对右结点调用递归函数了

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       if (!root || p == root || q == root) return root;
       TreeNode *left = lowestCommonAncestor(root->left, p, q);
       if (left && left != p && left != q) return left;
       TreeNode *right = lowestCommonAncestor(root->right, p , q);　　　　if (left && right) return root;
       return left ? left : right;
    }

此题还有一种情况，题目中没有明确说明p和q是否是树中的节点，如果不是，应该返回NULL，而上面的方法就不正确了，对于这种情况请参见 Cracking the Coding Interview 5th Edition 的第233-234页。
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        CounterNode n = helper(root, p, q);
        return n.node;
    }
 
    public CounterNode helper(TreeNode root, TreeNode p, TreeNode q){
        if(root==null){
            return new CounterNode(null, 0);
        }
 
        CounterNode left = helper(root.left, p, q);
        if(left.count==2){
            return left;
        }
 
        CounterNode right = helper(root.right, p, q);
        if(right.count==2){
            return right;
        }
 
        int c=left.count+right.count+(root==p?1:0)+(root==q?1:0);
 
        return new CounterNode(root, c);
 
    }
}
 
class CounterNode{
    public int count;
    public TreeNode node;
 
    public CounterNode(TreeNode node, int count){
        this.count=count;
        this.node=node;
    }

https://leetcode.com/articles/lowest-common-ancestor-of-a-binary-tree/
X. Post Order traverse
cases: the relationship between current node and target nodes
The approach is pretty intuitive. Traverse the tree in a depth first manner. The moment you encounter either of the nodes p or q, return some boolean flag. The flag helps to determine if we found the required nodes in any of the paths. The least common ancestor would then be the node for which both the subtree recursions return a True flag. It can also be the node which itself is one of p or q and for which one of the subtree recursions returns a True flag.
Let us look at the formal algorithm based on this idea.
Algorithm
  1. Start traversing the tree from the root node.
  2. If the current node itself is one of p or q, we would mark a variable mid as True and continue the search for the other node in the left and right branches.
  3. If either of the left or the right branch returns True, this means one of the two nodes was found below.
  4. If at any point in the traversal, any two of the three flags left, right or mid become True, this means we have found the lowest common ancestor for the nodes p and q.

private TreeNode ans;

public Solution() {
    // Variable to store LCA node.
    this.ans = null;
}

private boolean recurseTree(TreeNode currentNode, TreeNode p, TreeNode q) {
    // If reached the end of a branch, return false.
    if (currentNode == null) {
        return false;
    }
    // Left Recursion. If left recursion returns true, set left = 1 else 0
    int left = this.recurseTree(currentNode.left, p, q) ? 1 : 0;
    // Right Recursion
    int right = this.recurseTree(currentNode.right, p, q) ? 1 : 0;
    // If the current node is one of p or q
    int mid = (currentNode == p || currentNode == q) ? 1 : 0;
    // If any two of the flags left, right or mid become True
    if (mid + left + right >= 2) {
        this.ans = currentNode;
    }
    // Return true if any one of the three bool values is True.
    return (mid + left + right > 0);
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // Traverse the tree
    this.recurseTree(root, p, q);
    return this.ans;
}

Approach 3: Iterative without parent pointers

// Three static flags to keep track of post-order traversal.
// Both left and right traversal pending for a node.
// Indicates the nodes children are yet to be traversed.
private static int BOTH_PENDING = 2;
// Left traversal done.
private static int LEFT_DONE = 1;
// Both left and right traversal done for a node.
// Indicates the node can be popped off the stack.
private static int BOTH_DONE = 0;

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    Stack<Pair<TreeNode, Integer>> stack = new Stack<Pair<TreeNode, Integer>>();
    // Initialize the stack with the root node.
  stack.push(new Pair<TreeNode, Integer>(root, Solution.BOTH_PENDING));
  // This flag is set when either one of p or q is found.
  boolean one_node_found = false;
  // This is used to keep track of the LCA.
  TreeNode LCA = null;
  // Child node
  TreeNode child_node = null;
  // We do a post order traversal of the binary tree using stack
  while (!stack.isEmpty()) {
      Pair<TreeNode, Integer> top = stack.peek();
      TreeNode parent_node = top.getKey();
      int parent_state = top.getValue();
      // If the parent_state is not equal to BOTH_DONE,
      // this means the parent_node can't be popped off yet.
      if (parent_state != Solution.BOTH_DONE) {
          // If both child traversals are pending
          if (parent_state == Solution.BOTH_PENDING) {
              // Check if the current parent_node is either p or q.
              if (parent_node == p || parent_node == q) {
                  // If one_node_found was set already, this means we have found
                  // both the nodes.
                  if (one_node_found) {
                      return LCA;
                  } else {
                      // Otherwise, set one_node_found to True,
                      // to mark one of p and q is found.
                      one_node_found = true;
                      // Save the current top element of stack as the LCA.
                      LCA = stack.peek().getKey();
                  }
              }
              // If both pending, traverse the left child first
              child_node = parent_node.left;
          } else {
              // traverse right child
              child_node = parent_node.right;
          }
          // Update the node state at the top of the stack
          // Since we have visited one more child.
          stack.pop();
          stack.push(new Pair<TreeNode, Integer>(parent_node, parent_state - 1));
          // Add the child node to the stack for traversal.
          if (child_node != null) {
              stack.push(new Pair<TreeNode, Integer>(child_node, Solution.BOTH_PENDING));
          }
      } else {
          // If the parent_state of the node is both done,
          // the top node could be popped off the stack.
          // Update the LCA node to be the next top node.
            if (LCA == stack.pop().getKey() && one_node_found) {
                LCA = stack.peek().getKey();
            }
        }
    }
    return null;
}

Approach 2: Iterative using parent pointers
If we have parent pointers for each node we can traverse back from p and q to get their ancestors. The first common node we get during this traversal would be the LCA node. We can save the parent pointers in a dictionary as we traverse the tree.
  1. Start from the root node and traverse the tree.
  2. Until we find p and q both, keep storing the parent pointers in a dictionary.
  3. Once we have found both p and q, we get all the ancestors for p using the parent dictionary and add to a set called ancestors.
  4. Similarly, we traverse through ancestors for node q. If the ancestor is present in the ancestors set for p, this means this is the first ancestor common between p and q (while traversing upwards) and hence this is the LCA node.

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Stack for tree traversal
        Deque<TreeNode> stack = new ArrayDeque<>();
        // HashMap for parent pointers
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        parent.put(root, null);
        stack.push(root);
        // Iterate until we find both the nodes p and q
        while (!parent.containsKey(p) || !parent.containsKey(q)) {
            TreeNode node = stack.pop();
            // While traversing the tree, keep saving the parent pointers.
            if (node.left != null) {
                parent.put(node.left, node);
                stack.push(node.left);
            }
            if (node.right != null) {
                parent.put(node.right, node);
                stack.push(node.right);
            }
        }
        // Ancestors set() for node p.
        Set<TreeNode> ancestors = new HashSet<>();
        // Process all ancestors for node p using parent pointers.
        while (p != null) {
            ancestors.add(p);
            p = parent.get(p);
        }
        // The first ancestor of q which appears in
        // p's ancestor set() is their lowest common ancestor.
        while (!ancestors.contains(q))
            q = parent.get(q);
        return q;
    }


X. http://buttercola.blogspot.com/2015/08/leetcode-lowest-common-ancestor-of.html
What if there is a pointer to the parent?
Method 2: without using extra space
public Node findLCA(Node root, Node p, Node q) {
   if (root == null || p == null || q == null) return null;
   int depth1 = getDepth(root, p);
   int depth2 = getDepth(root, q);
   if (depth1 > depth2) {
      swap(depth1, depth2);
      swap(p, q);
   }
   for (int i = 0; i < depth1 - depth2; i++) {
      q = q.parent;
   }
   while (p) {
      if (p == q) return p;
      p = p.parent;
      q = q.parent;
   }
   return null;
}
public int getDepth(Node root, Node n) {
   if (root == null || n == null) return null;
   int depth = 0;
   while (root != n) {
      depth++;
      n = n.parent;
   }
   return depth;
}
xMethod 1 (By Storing root to n1 and root to n2 paths):
Following is simple O(n) algorithm to find LCA of n1 and n2.
1) Find path from root to n1 and store it in a vector or array.
2) Find path from root to n2 and store it in another vector or array.
3) Traverse both paths till the values in arrays are same. Return the common element just before the mismatch.
bool findPath(Node *root, vector<int> &path, int k)
{
    // base case
    if (root == NULL) return false;
    // Store this node in path vector. The node will be removed if
    // not in path from root to k
    path.push_back(root->key);
    // See if the k is same as root's key
    if (root->key == k)
        return true;
    // Check if k is found in left or right sub-tree
    if ( (root->left && findPath(root->left, path, k)) ||
         (root->right && findPath(root->right, path, k)) )
        return true;
    // If not present in subtree rooted with root, remove root from
    // path[] and return false
    path.pop_back();
    return false;
}
// Returns LCA if node n1, n2 are present in the given binary tree,
// otherwise return -1
int findLCA(Node *root, int n1, int n2)
{
    // to store paths to n1 and n2 from the root
    vector<int> path1, path2;
    // Find paths from root to n1 and root to n1. If either n1 or n2
    // is not present, return -1
    if ( !findPath(root, path1, n1) || !findPath(root, path2, n2))
          return -1;
    /* Compare the paths to get the first different value */
    int i;
    for (i = 0; i < path1.size() && i < path2.size() ; i++)
        if (path1[i] != path2[i])
            break;
    return path1[i-1];
}

Method 2 (Using Single Traversal)
If any of the given keys (n1 and n2) matches with root, then root is LCA (assuming that both keys are present). If root doesn’t match with any of the keys, we recur for left and right subtree. The node which has one key present in its left subtree and the other key present in right subtree is the LCA. If both keys lie in left subtree, then left subtree has LCA also, otherwise LCA lies in right subtree.
// This function returns pointer to LCA of two given values n1 and n2.
// This function assumes that n1 and n2 are present in Binary Tree
struct Node *findLCA(struct Node* root, int n1, int n2)
{
    // Base case
    if (root == NULL) return NULL;
    // If either n1 or n2 matches with root's key, report
    // the presence by returning root (Note that if a key is
    // ancestor of other, then the ancestor key becomes LCA
    if (root->key == n1 || root->key == n2)
        return root;
    // Look for keys in left and right subtrees
    Node *left_lca  = findLCA(root->left, n1, n2);
    Node *right_lca = findLCA(root->right, n1, n2);
    // If both of the above calls return Non-NULL, then one key
    // is present in once subtree and other is present in other,
    // So this node is the LCA
    if (left_lca && right_lca)  return root;
    // Otherwise check if left subtree or right subtree is LCA
    return (left_lca != NULL)? left_lca: right_lca;
}
    //Root of the Binary Tree
    Node root;
    Node findLCA(int n1, int n2)
    {
        return findLCA(root, n1, n2);
    }
    // This function returns pointer to LCA of two given
    // values n1 and n2. This function assumes that n1 and
    // n2 are present in Binary Tree
    Node findLCA(Node node, int n1, int n2)
    {
        // Base case
        if (node == null)
            return null;
        // If either n1 or n2 matches with root's key, report
        // the presence by returning root (Note that if a key is
        // ancestor of other, then the ancestor key becomes LCA
        if (node.data == n1 || node.data == n2)
            return node;
        // Look for keys in left and right subtrees
        Node left_lca = findLCA(node.left, n1, n2);
        Node right_lca = findLCA(node.right, n1, n2);
        // If both of the above calls return Non-NULL, then one key
        // is present in once subtree and other is present in other,
        // So this node is the LCA
        if (left_lca!=null && right_lca!=null)
            return node;
        // Otherwise check if left subtree or right subtree is LCA
        return (left_lca != null) ? left_lca : right_lca;

    }
Note that the above method assumes that keys are present in Binary Tree. If one key is present and other is absent, then it returns the present key as LCA (Ideally should have returned NULL).
We can extend this method to handle all cases by passing two boolean variables v1 and v2. v1 is set as true when n1 is present in tree and v2 is set as true if n2 is present in tree.
// This function returns pointer to LCA of two given values n1 and n2.
// v1 is set as true by this function if n1 is found
// v2 is set as true by this function if n2 is found
struct Node *findLCAUtil(struct Node* root, int n1, int n2, bool &v1, bool &v2)
{
    // Base case
    if (root == NULL) return NULL;
    // If either n1 or n2 matches with root's key, report the presence
    // by setting v1 or v2 as true and return root (Note that if a key
    // is ancestor of other, then the ancestor key becomes LCA)
    if (root->key == n1)
    {
        v1 = true;
        return root;
    }
    if (root->key == n2)
    {
        v2 = true;
        return root;
    }
    // Look for keys in left and right subtrees
    Node *left_lca  = findLCAUtil(root->left, n1, n2, v1, v2);
    Node *right_lca = findLCAUtil(root->right, n1, n2, v1, v2);
    // If both of the above calls return Non-NULL, then one key
    // is present in once subtree and other is present in other,
    // So this node is the LCA
    if (left_lca && right_lca)  return root;
    // Otherwise check if left subtree or right subtree is LCA
    return (left_lca != NULL)? left_lca: right_lca;
}
// Returns true if key k is present in tree rooted with root
bool find(Node *root, int k)
{
    // Base Case
    if (root == NULL)
        return false;
    // If key is present at root, or in left subtree or right subtree,
    // return true;
    if (root->key == k || find(root->left, k) ||  find(root->right, k))
        return true;
    // Else return false
    return false;
}
// This function returns LCA of n1 and n2 only if both n1 and n2 are present
// in tree, otherwise returns NULL;
Node *findLCA(Node *root, int n1, int n2)
{
    // Initialize n1 and n2 as not visited
    bool v1 = false, v2 = false;
    // Find lca of n1 and n2 using the technique discussed above
    Node *lca = findLCAUtil(root, n1, n2, v1, v2);
    // Return LCA only if both n1 and n2 are present in tree
    if (v1 && v2 || v1 && find(lca, n2) || v2 && find(lca, n1))
        return lca;
    // Else return NULL
    return NULL;
}
    // Root of the Binary Tree
    Node root;
    static boolean v1 = false, v2 = false;
    // This function returns pointer to LCA of two given
    // values n1 and n2.
    // v1 is set as true by this function if n1 is found
    // v2 is set as true by this function if n2 is found
    Node findLCAUtil(Node node, int n1, int n2)
    {
        // Base case
        if (node == null)
            return null;
        // If either n1 or n2 matches with root's key, report the presence
        // by setting v1 or v2 as true and return root (Note that if a key
        // is ancestor of other, then the ancestor key becomes LCA)
        if (node.data == n1)
        {
            v1 = true;
            return node;
        }
        if (node.data == n2)
        {
            v2 = true;
            return node;
        }
        // Look for keys in left and right subtrees
        Node left_lca = findLCAUtil(node.left, n1, n2);
        Node right_lca = findLCAUtil(node.right, n1, n2);
        // If both of the above calls return Non-NULL, then one key
        // is present in once subtree and other is present in other,
        // So this node is the LCA
        if (left_lca != null && right_lca != null)
            return node;
        // Otherwise check if left subtree or right subtree is LCA
        return (left_lca != null) ? left_lca : right_lca;
    }
    // Finds lca of n1 and n2 under the subtree rooted with 'node'
    Node findLCA(int n1, int n2)
    {
        // Initialize n1 and n2 as not visited
        v1 = false;
        v2 = false;
        // Find lca of n1 and n2 using the technique discussed above
        Node lca = findLCAUtil(root, n1, n2);
        // Return LCA only if both n1 and n2 are present in tree
        if (v1 && v2)
            return lca;
        // Else return NULL
        return null;

    }
We will soon be discussing more solutions to this problem. Solutions considering the following.
1) If there are many LCA queries and we can take some extra preprocessing time to reduce the time taken to find LCA.
2) If parent pointer is given with every node.
http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-tree-set-2-using-parent-pointer/
Node *LCA(Node *n1, Node *n2)
{
   // Creata a map to store ancestors of n1
   map <Node *, bool> ancestors;
   // Insert n1 and all its ancestors in map
   while (n1 != NULL)
   {
       ancestors[n1] = true;
       n1 = n1->parent;
   }
   // Check if n2 or any of its ancestors is in
   // map.
   while (n2 != NULL)
   {
       if (ancestors.find(n2) != ancestors.end())
           return n2;
       n2 = n2->parent;
   }
   return NULL;
}

A O(h) time and O(1) Extra Space Solution

      erse up using parent pointers of both nodes, the first common node in the path to root is lca.
      The idea is to find depths of given nodes and move up the deeper node pointer by the difference between depths. Once both nodes reach same level, traverse them up and return the first common node.
// A utility function to find depth of a node
// (distance of it from root)
int depth(Node *node)
{
    int d = -1;
    while (node)
    {
        ++d;
        node = node->parent;
    }
    return d;
}
// To find LCA of nodes n1 and n2 in Binary Tree
Node *LCA(Node *n1, Node *n2)
{
    // Find depths of two nodes and differences
    int d1 = depth(n1), d2 = depth(n2);
    int diff = d1 - d2;
    // If n2 is deeper, swap n1 and n2
    if (diff < 0)
    {
        Node * temp = n1;
        n1 = n2;
        n2 = temp;
        diff = -diff;
    }
    // Move n1 up until it reaches the same level as n2
    while (diff--)
        n1 = n1->parent;
    // Now n1 and n2 are at same levels
    while (n1 && n2)
    {
        if (n1 == n2)
            return n1;
        n1 = n1->parent;
        n2 = n2->parent;
    }
    return NULL;
}
Read full article from Lowest Common Ancestor in a Binary Tree | Set 1 | GeeksforGeeks
at
Labels: , , , , ,

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

  • Archives
  • LeetCode 471 - Encode String with Shortest Length
    Related:  LeetCode 394 - Decode String http://bookshadow.com/weblog/2016/12/11/leetcode-encode-string-with-shortest-length/ Given a  non...
  • Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks
    Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks Huffman coding is a lossless data compression algorithm. The idea is to assign ...
  • Buttercola: Buddy System
    Buttercola: Buddy System Given a complete binary tree with nodes of values of either 1 or 0, the following rules always hold: 1. A node...
  • Minimum area of a square enclosing given set of points
    Problem solving with programming: Minimum area of a square enclosing given set of points Given a set of coordinates in a two dimensional ...
  • HackerRank: N Puzzle
    HackerRank: N Puzzle N Puzzle is a sliding blocks game that takes place on a k * k grid with ((k * k) - 1) tiles each numbered from 1 to ...
  • LeetCode 394 - Decode String
    Follow up:  LeetCode 471 - Encode String with Shortest Length https://leetcode.com/problems/decode-string/ Given an encoded string, retu...
  • Hilbert Curve - Airbnb
    airbnb面试题汇总 Hilbert Curve Hilbert曲线可以无限阶下去，从1阶开始，落在一个矩阵里，让你写个function，三个参数（x,y,阶数），return 这个点（x,y）是在这阶curve里从原点出发的第几步 int hilbertCurve(...
  • Simple Text Editor - HackerRank
    https://www.hackerrank.com/challenges/simple-text-editor In this problem, your task is to implement a simple text editor. Initially, a fi...
  • LeetCode 291 - Word Pattern II
    leetcode 291 Word Pattern II Given a  pattern  and a string  str , find if  str  follows the same pattern. Here  follow  means a full m...