0 Overview

1. Bit manipulation
   Basically the idea is examining the bits of each number
   • Majority Number
   • Single Number II and Single Number III
2. HashMap + two pointers
   To process substring problems. Use HashMap to store characters information and use two pointers to update the HashMap.
   • Longest Substring with at most two distinct characters
   • Longest substring without repeating characters
   • Minimum window substring
   • Longest Substring with At Most K Distinct Characters
3. Stack
   • Largest Rectangle in histogram
   • Largest valid parentheses
   • Trapping rain water
     Store index in stack
4. compute modulo
   Basically use (n-1)%base to deal with edge cases
   • Excel Sheet Column Title
   • permutation sequence, given a number n, return the nth permutation sequence
5. Divide and Conquer
   • Different Ways to Add Parentheses (this one is good)

     a+c*c+d*e --> (a) + (c*c+d*e) or (a+c) * (c+d*e)...
     

     Basically divide the input into two by an operator and then fed the substrings to the same function
   • Burst Balloons
     This is pretty special divide and conquer
6. Memorized Dynamic Programming
   Basically take advantage of the results computed before. (what kind of DP is not suitable for memorized DP)
   • Guess Number Higher or Lower II
   • IntegerBreak
7. Combination sum like algorithm
   • Subset
   • Coin Change
8. Memorized DFS
   Think about the time complexity of memorized DFS.
   • Longest increasing path in a matrix
     This is pretty good. One thing that worth thinking is in what situation we can use memorized DFS.
9. MergeSort plus counting
   • count of range sum
     Another way to merge two subarrays. Instead of using two pointers, you can iterate through one of them. Another important thing is how to calculate the number of subarrays whose sum is in [lower, upper]. You don't have to start from the very beginning to count for each i in the first array.
   • Count of smaller numbers after self
     pay attention to the case where nums[p1] == nums[p2], which one goes to the result array first
10. List all possible solution
    • Create Maximum Number
      The most difficult part is how to merge two subarrays to create the maximum number (I made mistakes at this step every time)
11. Stack + HashMap
    The idea is create a hash map storing all the characters and then use a stack to get a max or min order. I feel like that Stack is extremely good for ordering things
    • Remove Duplicate Letters
    • Create Maximum Number
12. plain two pointers
    • Trapping rain water nice idea
13. Heap
    • Merge k sorted list
    • Find Median from Data Stream
14. Binary Search
    Binary search comes in different ways. The following examples should give you an good idea about the binary search problem patterns.
    • Find peak element
15. BFS
    • Walls and Gates
      This problem is nice. It has multiple initial values which is the box that with value 0. Then start from all the boxes that has value 0 (gates) then do BFS. Multiple point BFS.
16. Binary search tree
    Use a count in each node. You can walk the tree and count the number of elements smaller or greater than the current value. The nice about this technique is that you can preserve the order of the elements you insert into the BST.
    • Count of smaller number
    • Largest BST Subtree
      For BST problem, if you want to check if it's a BST or not, you have to get max and min of all the descendantes. You can not just look at it's left and right children and decide.
17. Divide Triple into Pairs
    The idea is divide triple into two paris and put all the pairs in one container. Sort all the pairs properly and iterate through the container in order and provide you the info you want.
    • The skyline problem
    • Range Addition
    • Course Schedule
    • Number of flights in sky
18. Use String as a pattern
    • Group Shifted Strings
19. DFS
    DFS comes in different forms.
    • Smallest Rectangle Enclosing Black Pixels
      This DFS is pretty interesting. You don't have to find all possible routes. you just need to cover every back pixel. So you don't have to set visited[x][y] to false when you exit the DFS method.
    • Expression add operator
      Memorized the previous operator and deal with * carefully. The first number also need to generated before doing dfs
20. Sum array plus HashMap or TreeMap
    *Maximum Size Subarray Sum Equals k