Leetcode

Array and Linked List

• Medium - 19 Remove Nth Node From End of List
• Medium - 24 Swap Nodes in Pairs
• Hard - 26 Reverse Nodes in k-Group
• Medium - 61 Rotate List
• Medium - 86 Partition List
• Medium - 92 Reverse Linked List II
• Medium - 138 Copy List with Random Pointer
• Medium - 148 Sort List
• Medium - Lintcode 42 - Maximum Subarray II
• Medium - Lintcode - 838 Subarray Sum Equals K

Sequence

General Method :

​ Two pointers (sliding window):

• Two onward pointers (sliding window)
• One onward pointer + One backward pointer

General Implementation Steps:

1. Use two pointers: start and end to represent a window.
2. Move end to find a valid window.
3. When a valid window is found, move start to find a smaller window.

Template :

int findSubstring(string s){
        int[] map = new int[256];
        int counter; // check whether the substring is valid
        int begin=0, end=0; //two pointers, one point to tail and one  head
        int d; //the length of substring

        for() { /* initialize the hash map here */ }

        while(end<s.size()){

            if(map[s[end++]]-- ?){  /* modify counter here */ }

            while(/* counter condition */){ 
                 
                 /* update d here if finding minimum*/

                //increase begin to make it invalid/valid again
                
                if(map[s[begin++]]++ ?){ /*modify counter here*/ }
            }  

            /* update d here if finding maximum*/
        }
        return d;
  }

Key Concepts :

Similar to binary search. Try to find a condition that can make pointers keep moving to one direction until they meet in the middle (onward + backward) or meet at the end of the given array (sliding window)

Notation : Try not to use while loop because it is easy to write bugs.

Application :

1. Find all results that satisfy some conditions in a given array
2. Do particular permutation to a given array.

Extension : 3 pointers (Keep one pointer and do two pointer to the rest of the given array)

Common corner cases:

1. end = s.length()

• Medium - 15 3Sum
• Medium - 16 3Sum closest
• Medium - 75 Sort Colors
• Hard - 76 Minimum Window Substring
• Easy - 121 Best Time to Buy and Sell Stock
• Easy - 141 Linked List Cycle
• Medium - 142 Linked List Cycle II
• Hard - 304 Longest Substring with At Most K Distinct Characters
• Medium - 424 Longest Repeating Character Replacement
• Medium - 567 Permutation in String
• Medium - 763 Partition Labels (Sweep - Line + Two pointers)
• Medium - 1055 Shortest Way to Form String
• Medium - 1100 Find K-Length Substrings With No Repeated Characters
• Medium - Lintcode 143 Sort Colors (rainbow sort)

Greedy

• Medium - 435 Non-overlapping Intervals

Subsets

• Easy - 28 Implement_strStr()
• Medium - 78 Subsets
• Medium - 90 Subsets II

Sort(Divide Conquer in Array)

• Hard 4 Medium of Two Sorted List
• Easy - lintcode 463. Merge Sort
• Easy - Lintcode 463 Quick Sort

Binary Search

• Medium - 33 Search in Rotated Sorted Array
• Medium - 34 Find First and Last Position of Element in Sorted Array
• Medium - 74 Search a 2D Matrix
• Medium - 81 Search in Rotated Sorted Array_II
• Medium - 153 Find Minimum in Rotated Sorted Array
• Easy - 278 First Bad Version
• Hard - 302 Smallest Rectangle Enclosing Black Pixels
• Hard - 410 Split Array Largest Sum
• Medium - 547 Friend Circles
• Hard - 644 Maximum_Average_Subarray_II
• Medium - 658 Find K Closest Elements
• Medium - 702 Search in a big sorted Array
• Easy - 704 Binary Search
• Easy - 852 Peak Index in a Mountain Array
• Hard - Lintcode183 Wood Cut
• Hard - Lintcode 437 Copy Books

BFS

Application :

1. Shortest path problem (especially for the case that each step counts 1, i.e. Matrix)
2. Topological sorting
3. Go through a graph
4. Matrix problem

General Implementation Step:

1. Traverse and collect all the start nodes and push them in a queue.
2. Construct corresponding graph with given edges.
3. while the queue becomes empty (Add extra Set if needed):
   • Poll one node from the queue each time and find its neighbors.
   • (if Set does not contains neighbors)Push the neighbors (in some conditions) into the queue.
4. Return.

• Medium - 102 Binary Tree Level Order Traversal
• Medium - 103 Binary Tree Zigzag Level Order Traversal
• Medium - 133 Clone Graph
• Medium - 200 Number of Islands
• Medium - 207 Course Schedule
• Medium - 210 Course Schedule II
• Medium - 216 Graph Valid Tree
• Hard - 297 Serialize and Deserialize Binary Tree
• Hard - 317 Shortest Distance from All Buildings
• Medium - 323 Number of Connected Components in an Undirected Graph
• Medium 417 Pacific Atlantic Water Flow
• Medium - 444 Sequence Reconstruction
• Medium - 529 Minesweeper
• Medium - 909 Snakes and Ladders
• Medium - 1091 Shortest Path In Binary Matrix
• Medium - Lintcode 127 Topological Sorting

Binary Tree and Divide Conquer

General Implementation step:

1. Set a global value if we need to find the max(min) value in Binary Tree.

2. Set divide conquer rule :

   • What should we calculate for each node?
   • To achieve this, what value should we get from the return value of root.left and root.right?
   • How many possible cases root.left and root.right have (i.e. : common cases illustrated below)
   • What is the corresponding value for those cases? How to deal with those cases to write clearest code for if..else.. condition.

3. Dealing with return statement like root == null

4. Return result in main function

Common corner case:

1. 4 cases when merging : root , root with left, root with right, root with left and right.

2. root == null (especially, take extra care of the original root is null)

3. leaf node can only be root.left == null && root.right == null

• Medium - 98 Validate Binary Search Tree
• Easy - 110 Balanced Binary Tree
• Easy - 111 Minimum Depth of Binary Tree
• Easy - 112 Path Sum
• Medium - 114 Flatten Binary Tree to Linked List
• Hard - 124 Binary Tree Maximum Path Sum
• Medium - 94 Binary Tree Inorder Traversal(iterative) --- (Template need to remember)
• Medium - 144 Binary Tree Preorder Traversal(iterative) --- (Template need to remember)
• Hard - 145 Binary Tree Postorder Traversal(iterative) --- (Template need to remember)
• Medium - 230 Kth Smallest Element in a BST
• Medium - 236 Lowest Common Ancestor of a Binary Tree
• Medium - 285 Inorder Successor in BST
• Hard - 297 Serialize and Deserialize Binary Tree
• Medium - 298 Binary Tree Longest Consecutive Sequence
• Medium - 426 Convert Binary Search Tree to Sorted Doubly Linked List
• Easy - 437 Path Sum III
• Medium - 549 BInary Tree Longest Consecutive Sequence II
• Easy - 559 Maximum Depth of N-ary Tree
• Medium - 666 Path Sum IV
• Medium - 1120 Maximum Average Subtree
• Hard - 1569 Number of Ways to Reorder Array to Get Same BST
• Easy - Lintcode 376 Binary Tree Path Sum
• Easy - Lintcode 480 Binary Tree Paths
• Easy - Lintcode 596 Minimum Subtree

DFS

• Medium - 39 Combination Sum
• Medium - 40 Combination Sum II
• Medium - 46 Permutations
• Medium - 47 Permutations II
• Hard - 126 Word Ladder II
• Medium - 130 Surrounded Regions
• Medium - 131 Palindrome Partitioning
• Hard - 140 Word Break II
• Medium - 216 Combination Sum III
• Hard - 301 Remove Invalid Parentheses
• Medium - 332 Reconstruct Itinerary
• Hard - 488 Zuma Game
• Medium - 490 The Maze

Dynamic Programming

Dynamic Programming is DFS/Divide Conquer + Memorization

General Implementation step:

1. States:

   • The final state
   • The relation between final state and sub-states

2. Transformation equation

3. The first state and corner cases : ie. f[0] and f[< 0]

4. The order of DP : Bottom-up or Up-bottom

Coordinates DP:

f[i] represents some property that end at ai

Common Corner cases: i == 0 || j == 0

• Easy - 53 Maximum Subarray

• Medium - 63 Unique Paths II

• Medium - 64 Minimum Path Sum

• Medium - 131 Palindromic Substrings

• Medium - 152 Maximum Product Subarray

• Medium - 322 Coins Change

• Hard - 354 Russian Doll Envelopes

Sequence DP:

f[i] represents some property of a0 to ai-1

• Medium - 139 Word Break
• Hard 265 Paint House II

Union Find

Template:

public class ConnectingGraph3 {
    int father[];
    int[] size;
    int count;

    public ConnectingGraph3(int n) {
        father = new int[n + 1];
        size = new int[n + 1];
        count = n;
        for (int i = 0; i <= n; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    public void connect(int a, int b) {
        int fatherA = find(a);
        int fatherB = find(b);
        if (fatherA != fatherB) {
            father[fatherA] = fatherB;
            count--;
            size[fatherA] += size[fatherB];
        }
    }

    public int query(int a) {
        return count;//Or return size[find(a)];
    }
    
    public int find(int a) {
        if (father[a] == a) {
            return a;
        }
        
        return father[a] = find(father[a]);
    }
}

Common corner cases :

1. We want to create or connect a node but the node is already created in the father array(has father already)
2. We want to find a node but the node haven't created in the father array

• Hard 305 Number of Islands II
• Medium - 990 Satisfiability of Equality Equations