maximum subarray: two pointers algorithm. Can be considered as 1D DP. There is a divide and conquer solution which is divided in three scenarios.
maximum subarray II: Divide left and right. 2 X 1D DP
maximum subarray III: 2D DP with optimization
maximum product subarray: use maximum and minimum to keep track of results. 1D DP.
num sum series
two sum (number not sorted): hash map to store <number, position> pairs
two sum II (sorted): two pointers algorithm.
two sum IV: hashset
three sum: two pointers algorithm. Use one to sweep from start to end, the other to sweep backwards
three sum closest: basically two pointers algorithm
four sum: same two pointers algorithm as three sum. Remember to skip duplicate numbers
four sum II: hash map to store <sum of elements in A, B; occurrences> pairs
valid series
valid number
best time to buy and sell stock series
I and II: sweep. Consider this as 1D DP.
III: divide left and right, do DP twice
IV: 2D dynamic programming
intervals series
merge interval: In Java, use Collections.sort(), so that insert interval is unnecessary. We can add one by one.
insert interval: The first interval should be found by comparing old interval's ends with new interval's start. Condition for inserting is newInterval.end < nextInterval.start
longest series
longest substring without repeating characters: Use hashmap to map characters to their indices.
palindrome series
longest palindromic substring
Maximum common substring between reversed string (some tweak) - Dynamic programming
Dynamic programming: p(i,j) if string(i,j) is palindrome
Expand around center: be careful of even length palindrome
Manacher algorithm
shortest palindrome
brutal force: reverse the string and compare the beginning and end
KMP: Construct s + # + inv(s), and construct the prefix = suffix array
two pointers algorithm: use the counting property.
stair shape stack series
largest rectangle in histogram: increasing stack to find border, left and right sweep, left to right sweep is enough, when decrease, current bar is right border. Upside down with container with most waster.
maximal rectangle: loop of largest rectangle in histogram
container with most water: decreasing stack to find border, left sweep is enough
trapping rain water: decreasing stack
trapping rain water II: actually BFS. Use queue to maintain spots that need to be checked again. Only check spots where water level is reduced, and their neighbors.
calculator series
evaluate reverse polish notation: stack
basic calculator: solved with two stacks: one for operands one for numbers. Can be solved with just one stack. Use number to track current number. Use result to track current result. Use 1 and -1 trick to track sign. Use stack to track parenthesis. We push result = 0 and sign = 1 for multiple consecutive parenthesis.
basic calculator II: one stack with pushing 1 trick. Be careful with negative number at the beginning. Open a new stack when seeing "+,-", not "x,/"!
expression and operators: DFS is sufficient. Iterate through length of number. Break by operator position is enough.
loop series
find the duplicate number: duplicated number forms a loop. Use two pointers to find the entrance. Return index.
Arrays
set matrix zeros: use first row and column to keep flags
search 2D matrix: binary search
search 2D matrix II: search by corner from top right to bottom left.
longest consecutive sequence: use set to get union
majority element: Moore's algorithm. Count up and down
majority element II: Moore's algorithm variation. Notice how we have to add before subtract
can place flowers: pay attention to all cases
Backtracking
subsets, word search: backtracking
permutations, permutations II
Binary search
Bit shift
divide two integers: bit shift
pow(x,n)
three pointers
search in rotated sorted array: use three pointers
Search in Rotated Sorted Array II: skip duplicated boundary
Find Minimum in Rotated Sorted Array
Find Minimum in Rotated Sorted Array II
search for a range
search insertion position
sqrt(x)
valid perfect square: basically sqrt
Search a 2D Matrix: I think converting 2D matrix to 1D by index mapping is better than searching rows and columns separately. At least code can be easier.
Find Peak Element: compare mid with mid-1 and mid+1
h-index II
first bad version
guess number higher or lower: be careful of overflow!
find right interval
arranging coins: overflow
heaters
find k closest element
search of answer
median of two sorted array: binary search of k in the kth element
kth smallest element in a sorted matrix: binary search of guessed number and find its position in matrix
kth smallest number in multiplication table: basically kthe smallest element in a sorted matrix. Guess the answer and binary search for it.
split array largest sum: search of largest sum since it is bounded
smallest good base: search of the power of the base-converted number. There is a formula for finding based given the base-converted number
search of sum
max sum of rectangle no larger than k: basically brute force version of 1D max sum of sub array no larger than k. Do a binary search to find any value > sum - k among previous sums.
Binary search tree
count complete tree nodes
kth smallest element in a BST: in order traversal
Divide and conquer
count complete tree nodes: count left and right. Perfect tree short cut
Dynamic programming
1D dynamic programming
triangle: DP backwards
maximum product subarray: use maximum and minimum to keep track of results. Don't use positive and negative!
product of array except self: two sweeps
house robber, house robber II
valid parenthesis string: Use two variables to track the min and max number of open parenthesis. Notice that the number of valid open parenthesis can not be less than zero.
With optimization
coin change: DP[i] stores the value of minimum coins for amount i. Need to optimize over coins.
longest increasing subsequence: DP[i] stores the longest subsequence using nums[i]
perfect squaresDP[i] stores the number of squares for integer i
Wildcard Matching: 3 cases: character before * used 0, 1, multiple times
regular expression matching: 3 cases: character before * used 0, 1, multiple times
is subsequence: 2D DP. Two rows are sufficient. Actually two pointers algorithm is sufficient.
With optimization
Split Array Largest Sum: optimize over previous results
Game Theory
minimax
can I win: can be solved with negamax algorithm since this is zero sum game. Use hash map to remember result. Can reduce from O(n!) to O(2^n)
Hash
hash set
intersection of two arrays: hash set
hash map
intersection of two arrays II: hash map
isomorphic strings LinkedIn: Use array of size 256 for character mapping! hash map or hash table
max points on a line: gcd works great when calculating the slope
Linked List
double linked list
LRU cache: Map from key to double linked list
misc
merge two sorted list
merge k sorted list: priority queue or heap
Math
overflow
Pow(x,n): x=0, x overflow, 1/x overflow, n min_val
prime factors
count primes: find a prime, remove all of none primes from it.
ugly number
ugly number II: When facing with factors problems, can use multiple pointers to track factors.
super ugly number: Remember that all pointers of primes after multiplication that equal to the minimum should move forward.
Sort
insertion sort
insertion sort list: Dummy head
counting sort
radix sort
bucket sort
sort colors: Since there are only three colors, move numbers to the sides - throw 0s to the left throw 2s to the right.
remove duplicates from sorted array: bucket sort
maximum gap: buckets are of length (max-min)/(n-1), and use pigeon hole
valid anagram: alphabet buckets
quick sort
sort list: have to use list trick and maybe find middle?
merge sort
sort list: merge sort can also solve the problem
merge sorted array: merge from back to front
count of smaller number after self: merge sort can count the numbers to the right/left when merging
misc
largest number: Just sort. Use a_b and b_a to decide which comes at first
wiggle sort: sort pair by pair
wiggle sort II: Quick select algorithm to find the kth largest element in array. Can be used to find median. Remember to use three way partition and index mapping.
Stack
stair shape series
misc
longest increasing subsequence, Russian envelope: although these are tagged as binary search, the key idea is to keep a "stack" of visited numbers
Strings
substring in window
minimum window substring: HashMap and two pointers. Two while loops: one to make solution valid/invalid, the other to make solution invalid/valid.
test of edge cases
valid number: + - e .
atoi: + - invalid number overflow. Overflow can be solved by Integer.MAX_VALUE/10 and Integer.MAX_VALUE%10
validate IP address
misc
word ladder: breadth first search, use string builder and hash set
word ladder II: bfs, then dfs. Use map to track backwards path. We need DFS since BFS can not backtrack. It might be too expensive to store all the possible routes. For DFS, we need a map from words to its shortest distance to start. We need a map from words to previous words.
text justification: special case: one word in a line
zigzag conversion: math and be careful of edge cases.
Tree
traversal
in-order
binary tree in-order traversal:
Morris traversal in O(1) space.
Follow dot graph using stack: root not empty: push stack and go to left; root empty: pop stack and go to pop right
binary search tree iterator: in-order traversal using stack
recover binary search tree: In order traversal. Morris traversal algorithm
kth smallest number in a BST
find mode in BST
pre-order
binary tree pre-order traversal: Stack: Push root, right child, left child
same tree, symmetric tree, subtree of another tree: pre-order traversal
flatten binary tree to linked list: not exactly pre-order traversal. Process left then right. Need to return the right most child of left and right sub trees.
find duplicate subtrees: same idea as serialize and de-serialize
post-order
binary tree post-order traversal:
opposite of pre-order traversal when looking backwards, use stack. Use another stack to reverse result.
Follow dot graph using stack: root not null: push stack go to left; root null: (1) if stack top has right, go to that (2) pop stack, and pop all right branch
construct string from binary tree
level-order
binary tree level order traversal: BFS using queue. Can use queue.size instead of two queues.
binary tree level order traversal II: BFS using queue.
binary tree zig-zag level order traversal: BFS using stack.
populating next right pointers in each node II and II: very special level order traversal. Need to keep track of this level's node, and next level's last visited node. This level can be visited by using this level's node's next.
binary tree right side view: level order traversal find the last node of every level
find bottom left tree value: level order
find largest value in each tree row: level order
average of levels in binary tree
construct tree
construct binary tree from preorder and inorder traversal: pre-order starts with root
construct binary tree from postorder and inorder traversal: post-order ends with root
convert sorted array to BST: use middle element as root. Remember to use tree pointers instead of recursion.
serialization
serialize and deserialize binary tree: pre-order or level order
serialize and deserialize binary search tree: find divider of left and right sub-trees first
delete
delete node in a BST: Return the new root is convenient. Three cases: no child, one child, two children. Two children case can be solved by moving the value to the current root, and then do a deletion.
width
maximum width of binary tree: trick is to assign 2i and 2i+1 to children
sum
path sum: pay attention to not leaf paths
path sum II: not all functions of LinkedList is available in List. new LinkedList(oldList) can be sed to clone a list.
path sum III: need to separate recursion with path finding logic
binary tree maximum path sum: can use an array to return multiple values of the same type!
house robbery III: return two values
most frequent subtree sum: hash table
convert BST to greater tree
binary tree tilt
merge two binary trees
pass down
validate binary search tree: can pass down min and max. Don't have to return them. Also, be careful of minimum and maximum values of integer.
sum root to leaf numbers: pass current number down
sum of left leaves: sum!
binary tree right side view: traverse right sub tree first and add any node whose level is larger than the maximum level so far
misc
unique binary search tree I: permutation of left and right
unique binary search tree II: List<TreeNode> can add null
lowest common ancestor of a binary search tree: Use property of BST
lowest common ancestor of a binary tree: return found element or common parent
maximum depth of binary tree: DFS
minimum depth of binary tree: DFS. Pay attention to not leaf path
balanced binary tree: return -1 as not balanced
count complete tree nodes: use left depth and right depth to shortcut some calculation
invert binary tree: BFS can also work, I think
binary tree path: string builder
diameter of binary tree: use int[] to pass two values
trim a BST
Trie
trie service
implement trie
trie seralization: n node tree seralization
Two pointers
minimum size subarray sum: two pointers
sum of square numbers
validate palindrome, validate palindrome II
System Design
mini twitter: Check if Hash map contains key before accessing the value
consistent hashing: can call set on Integer
memcache
mini cassandra: TreeMap is implemented by Red-black tree (balanced BST). TreeSet is implemented by TreeMap.
tiny url: unique ID
consistent hashing II: TreeMap for the rescue
GFS client
MISC
Java int can not be null. Integer is nullable. Collection contains objects.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent