Important Questions

Fill Water questions

84. Largest Rectangle in Histogram (https://leetcode.com/problems/largest-rectangle-in-histogram/description/)

• Needs to build a increasing stack and it will allow you let where is left boundary.

85. Maximal Rectangle (https://leetcode.com/problems/maximal-square/description/) (Question 84's further question)

Square && Rectangle

836. Rectangle Overlap (https://leetcode.com/problems/rectangle-overlap/description/)

• Good question and you just make sure rec2's x1 >= rec1's x2 ... 4 conditions

223. Rectangle Area (https://leetcode.com/problems/rectangle-area/description/)

• 836 题升级版

Matrix

54. Spiral Matrix (https://leetcode.com/problems/spiral-matrix/description/)

• You need to traverse more nodes in horizontal.
• Mark top-left and bottom-right point.
• See https://leetcode.com/problems/spiral-matrix/solution/

Frequent Questions

What's difference between Comparator and Comparable?

1. PriorityQueue<Cell> heap = new PriorityQueue<Cell>(16);
- class Cell implements Comparable<Cell>!

2. PriorityQueue<Cell> heap = new PriorityQueue<Cell>(16n new MyComparator());
- class MyComparator implements Comparator<Cell>!

// Class whose objects to be sorted must implement this Comparable interface
public interface Comparable {
   public int compareTo(Object obj);
}

// Some third class can implement this interface to sort.
public interface Comparator {
    public boolean equals(Object obj);

    public int compare(T o1, T o2);
}

LCA Tree

236. Lowest Common Ancestor of a Binary Tree (https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/)
237. Lowest Common Ancestor of a Binary Search Tree (https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/)

Q5.3:Lowest common ancestors of k nodes.

public TreeNode LCA(TreeNode root, Set<TreeNode> set) {
    if (root == null || set.contains(root)) {
        return root;
    }

     TreeNode left = LCA(root.left, set);
     TreeNode right = LCA(root.right, set);

     if (left != null && right != null) {
         return root;
     }

     return left == null ? right : left;
}

Q5.4 LCA for two nodes in k-nary tree

Q5.5 Lowest common ancestors for k nodes of K nodes.

class TreeNode {
    int val;
    List<TreeNode> children;
}

public TreeNode LCA(TreeNode root, Set<TreeNode> nodes) {
    if (root == null || nodes.contains(root)) {
        return root;
    }

    int counter = 0;
    TreeNode tmp = null;
    for (TreeNode child : root.children) {
        TreeNode node = LCA(child, nodes);
        if (node != null) {
            counter++;
            if (counter > 1) {
                 return root;
            }
             tmp = node;
        }
    }

     return tmp;
}

Q5.6 LCA for two nodes a and b in a very large tree that contains billions of nodes.