Checklist to Solve Algorithm Problems

logn
- bisection
- divide and conquer

X. Quick select to find kth O(n) - compare with heap nlog(k)


X. DP
- find sub-problems and relation
- dp: [i, j]; or dp[len-1] just start/or end
X. BFS
- Model it as a graph
X. DFS

X. Divide and Conquer

- find subproblems and relations

X. Bisection/Binary search
O(nlogn) - logn*n(merge sort) or n*logn(3 sum) binary search/bisection

X. Merge sort
X. Slide Window
X. Two pointers

Data Structures

X. Trie
- use trie so no need to scan every candidate(O(n))

X. Binary search tree

X. ordered stack/stack

X. Union Find

Data structures

X. augmented tree

X. bst

TreeSet, TreeMap

X. heap, map

X. Bit trick
- O(32n) - loop and check every bit
- bit trie, use xor

X. Interval
- First sort these intervals somehow
- Think as different events - start, end
- sort interval + greedy
- merge interval

X. Game theory

Palindrome

-- Scan from center

Graph - O(V+E)
- topological sort

- Eulerian path/circuit

Save space
- reuse input
- rolling array for dp

Common tricks

check last loop

whether we need do extra things after loop

Use char[] to avoid string concatenation

Backtrack

- Don't forget to clear state

Binary tree

- usually expected runtime for tree is O(n)

ask
- sorted?
- can we change input, use extra space