Leetcode category
General SOP
- 簡單的 20 min 內,難的 30-40 min
- 討論出解法及確認 TC / SC 沒問題再實作
Asking Clarifying Questions (2 mins)
- 問問題 (see here),dry run 一次範例
Proposing valid solution (8-10 mins)
- 解釋做法,分析複雜度,可以的話提出多種做法並討論 trade-off。
Code & Implement (5 mins)
Dry run (5 mins)
When stuck
- ask for hint
- observation
- 用 interviewer 給的範例人工解題
- 試著發現可以寫成 algorithm 的 pattern
- 如果是那種找出最小/大的 XXX 的問題,然後要做很多 decision (可以畫出 decision tree 的形式):
- 嘗試去感覺有沒有 greedy solution
- 很難做決定的話可能是 backtrack 或 dp
Reactions to scenario
- counting sort
- binary search
- segment tree
找出答案的決策流程很複雜:
- backtracking
- DP
- 知道 subproblem 的答案的話可以幫助算出原問題嗎?
- backtracking 的 solution 可以 memoize 嗎?
- greedy
- monostack
- sort + greedy
- binary search
- two pointers (find sum)
需要 partially sorted:
- priority queue with size limited to k
- quick select
- O(n) in avg/O(1) iterative
最短路徑 / 最少開銷從 A 到 B:
- BFS (equally weighted edge)
- Dijkstra
- O(ElogV) using indexed priority queue
- total update E time, priority queue stays at most size V
- O(ElogE) = O(ElogV) using lazy update
- total update E time, priority queue may have duplicate val, size E
- but since O(logE) = O(2logV) = O(logV), the order is the same.
- O(V+E) space
tree:
- path w/o cycle
- single root
constant space (不能用額外 data structure):
- majority voting
- linked list cycle
- bitwise
get max/min:
- prefix sum/min/max
- priority queue (hard to update, only lazy rm, or use indexed pq)
- binary search tree (easy to update)
- segment tree (range query/update)
subset:
- backtracking
- 0/1 knapsack
palindrome:
- 可先用 lookup table 把
str[i:j]
是否為 palindrom 記錄在 memo[i, j]
- O(n^2) for create table
- O(1) for furthur application
有大小、先後關係,要求排列或是否矛盾:
Dynamic Programming:
- 問自己假設知道 subproblem 的答案,能夠解出現在問題的答案嗎?
- Reverse thinking,從 N -> 0
- prefix DP dp[i] = arr[0…i] 的答案
- range DP dp[i][j] = arr[i…j] 的答案
- knapsack
- 給定一些 item 選與不選,item 有 value/cost,題目有 cost 上限,求:
- cost 上限內,最大/小 value or 選擇的 set
- TSP (travling salesman problem)
- augmented DP
- 如果原本的 dp table 不能完整敘述 subproblem,需要再加一維 dp[i] –> dp[i][j],用這一維存下多的資訊
Clarifying questions
- size of input, can be empty?
- what's the range of value, positive? negative? including 0?
- is there duplicated value? or all unique?
- is it sorted?
- is it guarantee to have a valid ans?
- what to return if no valid ans?
Common mistake
1. 迴圈
迴圈最後要加的東西 沒有加進
記得迴圈用的區域變數不要跟其他變數衝突
2. Boolean
檢查 AND/OR 不要搞反
小心 short circuit
如果 dfs(left)==False
,dfs(right)
就不會執行:
如果有些邏輯是不管怎樣都要對每個 node 執行,務必寫成這樣:
3. Complexity
permutation:
combination:
dfs for "path":
- String
invalid number string:
leading zero: 000012
negative zero: -0
Time Complexity
n! –> 2^n –> polynomial
-
n! permutation
T(n) = nT(n-1)
-
2^n combination
T(n) = 2T(n-1)
-
polynomial combination (reuse subset of combination)
-
O(n)
-
O(nlogn)
-
O(logn)
-
O(n2)
Data structures
- priority queue
- stack
- hash map
- hash set
- segment tree
- trie
Category
Knapsack
0/1 knapsack
unbounded knapsack
Array
Quickselect
O(n) / O(1)
得到 k-th 大/小的元素
https://leetcode.com/problems/kth-largest-element-in-an-array/
Dutch National Flag
L 指向 0 後的第一個 idx
M 指向第一個 ?
R 指向最後一個 ?
majority voting
https://leetcode.com/problems/majority-element-ii/
linked list cycle
https://leetcode.com/problems/linked-list-cycle-ii/
prefix sum
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
sliding window / 2-3 pointers
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
- 快慢 pointer
- 左右 pointer 往中間夾
hash map (2Sum)
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
在 loop 的過程中將 arr[i] 加進 map,在 map 尋找 target - arr[i] 的 idx/count。
可搭配 prefix,將 prefix 存進 map,便能在 map 尋找某區間的和是否等於 target。
https://leetcode.com/problems/longest-well-performing-interval/
https://leetcode.com/problems/subarray-sum-equals-k/
https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/
https://leetcode.com/problems/contiguous-array/
https://leetcode.com/problems/binary-subarrays-with-sum/
left/right extend arr
用 left[i] 紀錄往左邊看第一個比 arr[i] 還大/小的 idx
用 right[i] 紀錄往右邊看第一個比 arr[i] 還大/小的 idx
便能計算以 arr[i] 為最大/小值的最大 subarray,搭配 prefix sum 能進一步算該 subarray 的和。
e.g.
reverse all + reverse partial 技巧
https://leetcode.com/problems/rotate-array/
https://leetcode.com/problems/reverse-words-in-a-string-iii/
square root decomposition
https://leetcode.com/problems/design-most-recently-used-queue/
Priority Queue
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Use extra field to mark element as "removed".
https://leetcode.com/problems/exam-room/discuss/139941/Python-O(log-n)-time-for-both-seat()-and-leave()-with-heapq-and-dicts-Detailed-explanation
improvement (using bucket):
https://codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068cb14
-> bucket O(1) popmax / insert
if the value range is limited, use each value as key, store the elements with that value in array or hashset.
Game / MinMax
https://leetcode.com/problems/cat-and-mouse/submissions/
Rectangles
84. Largest Rectangle in Histogram
221. Maximal Square
85. Maximal Rectangle
1727. Largest Submatrix With Rearrangements
Stack
1673. Find the Most Competitive Subsequence
1425. Constrained Subsequence Sum
239. Sliding Window Maximum
Monotonic Queue
https://leetcode.com/problems/shortest-unsorted-continuous-subarray/
https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/
https://leetcode.com/problems/next-greater-element-i/
https://leetcode.com/problems/largest-rectangle-in-histogram/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
TODO:
907. Sum of Subarray Minimums
901. Online Stock Span
856. Score of Parentheses
503. Next Greater Element II
496. Next Greater Element I
Floyd-Warshall
1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance
Counting sort
49. Group Anagrams
Sliding Window
pattern: subarray
that match some condition
template:
map::lower_bound
, map::upper_bound
map::lower_bound(k)
gives the iterator that its key that >= k
map::upper_bound(k)
gives the iterator that its key > k
Unicode character
- unicode contains 1 OR 2 character.
Longest Increasing Subsequence
Topological
Trie
root is dmy
check if next node exist
if not exist: return
else: check if "next" node is endNode and add to ans
421. Maximum XOR of Two Numbers in an Array
1707. Maximum XOR With an Element From Array
Trie search with limitation
Prefix Sum
Kadane's algorithm
Bitset
Two pointer
11. Container With Most Water
42. Trapping Rain Water
算裝水的問題可以用stack或two pointer來做
用stack的缺點是你不知道從左到右的路上
遇到小水坑你只能蒐集這個水坑裡的水(x的部分)
但水坑上方的的空間你不確定有沒有水(?的部分)
儘管左邊有更高的山(1)
但你不知道右邊有沒有高山可以困住(?)的水
要直到遇到了才能蒐集(?)
two pointer則很巧妙的用這個問題greedy的性質
從兩側往中間逼近
總是移動矮的那一邊,所以你可以保證另一邊一定有比這邊更高的山
所以每次蒐集雨水時可以直接算出每個位置會淹到哪裡
713. Subarray Product Less Than K
1574. Shortest Subarray to be Removed to Make Array Sorted
Linked List
Reverse
Slow-Fast pointers
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/discuss/35476/Share-my-JAVA-solution-1ms-very-short-and-concise.
Bucket
220. Contains Duplicate III
a solution for 36. Valid Sudoku
Permutation
46. Permutations
Pascal Traingle
table[n-1][m] == Cn取m
1569. Number of Ways to Reorder Array to Get Same BST
Backtracking
gfg
1239. Maximum Length of a Concatenated String with Unique Characters
Segment Tree
https://leetcode.com/tag/segment-tree/
Fenwick Tree
Need to be 1-based
range query + node 會swap位置
1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits
只加下一個 parent
Segment Tree
Array based
假設要建segment tree的資料有n筆
如果n是2的power,tree size = 2n-1
如果不是,tree size是2x-1,x是比n大的最小的2的power
所以一定可以涵蓋的array大小會是n<<2 (4n)
vector<int> tree(N<<2);
void build_tree(vector<int>& tree, int idx, int l, int r) {
if (l==r) {
tree[idx] = nums[l];
return;
}
int m = l + (r-l)/2;
tree[idx] = merge(
build_tree(tree, idx<<1, l, m),
build_tree(tree, idx<<1|1, m+1, r)
);
}
int query(vector<int>& tree, int idx, int l, int r, int i, int j) {
if (i==l && j==r) {
return tree[idx];
}
int m = l + (r-l)/2;
if (j <= m) {
return query(tree, idx<<1, l, m, i, j);
} else if (m < i) {
return query(tree, idx<<1|1, m+1 ,r, i, j);
} else {
int lft = query(tree, idx<<1, l, m, i, m);
int rgh = query(tree, idx<<1|1, m+1, r, m+1, j);
return merge(lft, rgh);
}
}
void update(vector<int>& tree, int idx, int l, int r, int i, int val) {
if (l==r) {
tree[idx] += val;
return;
}
int m = l + (r-l)/2;
if (idx <= m) {
update(tree, idx<<1, l, m);
} else {
update(tree, idx<<1|1, m+1, r);
}
tree[idx] = merge(tree[idx<<1], tree[idx<<1|1]);
}
int sg(vector<int>& nums) {
int n = nums.size();
tree = vector<int>(n<<2);
build_tree(tree, nums, 1, 0, n-1);
}
lazy propagation
當要做range update時,可用lazy update
要另外管理一個跟tree
一樣大的array: lazy
- lazy只會紀錄到樹的某一層,在lazy紀錄到之下的都還沒被更新
- 如果query到lazy紀錄的node,就更新那一層,再把lazy傳到下一層
void update_lazy(vector<int>& tree, vector<int>& lazy, int idx, int l, int r, int i, int j, int val) {
if (lazy[idx]!=0) {
tree[idx] += (r-l+1) * val;
if (l!=r) {
lazy[idx<<1] += lazy[idx];
lazy[idx<<1|1] += lazy[idx];
}
lazy[idx] = 0;
}
if (l>r || l>j || r<i) return;
if (l>=i && r<=j) {
tree[idx] += (r-l+1) * val;
lazy[idx<<1] += val;
lazy[idx<<1|1] += val;
return;
}
int m = l + (r-l)/2;
update_lazy(tree, lazy, idx<<1, l, m, i, m, val);
update_lazy(tree, lazy, idx<<1|1, m+1, r, m+1, j, val);
tree[idx] = merge(tree[idx<<1], tree[idx<<1|1]);
}
int query_lazy(vector<int>& tree, vector<int>& lazy, int idx, int l, int r, int i, int j) {
if (l>r || l>j || r<i) return 0;
if (lazy[idx]!=0) {
tree[idx] += (r-l+1) * lazy[idx];
if (l!=r) {
lazy[idx<<1] += lazy[idx];
lazy[idx<<1|1] += lazy[idx];
}
lazy[idx] = 0;
}
if (i==l && j==r) return tree[idx];
int m = l + (r-l)/2;
if (j<=m) {
return query_lazy(tree, lazy, idx<<1, l, m, i, j);
} else if (i > m) {
return query_lazy(tree, lazy, idx<<1|1, m+1, r, i, j);
}
int lft = query_lazy(tree, lazy, idx<<1, l, m, i, m);
int rgh = query_lazy(tree, lazy, idx<<1|1, m+1, r, m+1, r);
return tree[idx] = merge(lft, rgh);
}
Bit manipulation
Merge Sort
Quick sort
Random
470. Implement Rand10() Using Rand7()
String
316. Remove Duplicate Letters
Greedy + string
KMP
youtube
template:
28. Implement strStr()
796. Rotate String
palindrome
214. Shortest Palindrome
看回文 abc#bca
5. Longest Palindromic Substring
336. Palindrome Pairs
Rabin Karp
power 的部分可以用%prime來防止overflow
1044. Longest Duplicate Substring
- map放global比較慢,會TLE
- 存string的index就好,不要存string,會爆memory
- 在Rabin Karp減去hash的時候:
hash = (hash - ((S[i-m] - 'a') * (long long)power[m-1]) % prime) % prime;
有時因為目前的hash已經超過prime,導致hash回到一個很小的數,讓hash - ((S[i-m] - 'a') * (long long)power[m-1]) % prime
變成負數,所以要再加一個prime讓他變回正數
hash = (hash - ((S[i-m] - 'a') * (long long)power[m-1]) % prime + prime) % prime;
Union Find
template:
Greedy
Interval scheduling
wiki
- Selecting the intervals that start earliest is not an optimal solution, because if the earliest interval happens to be very long, accepting it would make us reject many other shorter requests.
- Selecting the shortest intervals or selecting intervals with the fewest conflicts is also not optimal.
435. Non-overlapping Intervals
…
56. Merge Intervals
252. Meeting Rooms
253. Meeting Rooms II
452. Minimum Number of Arrows to Burst Balloons
1605. Find Valid Matrix Given Row and Column Sums
Dynamic Programming
切割子問題
dp[i] = 範圍從0到i的子問題 且選擇i
template:
Bottom-up (tabulation)
Top Down (memoization)
1
638. Shopping Offers
1553. Minimum Number of Days to Eat N Oranges
1575. Count All Possible Routes
Top down
Bottom up
- hashmap
- Large scale –> use hashmap rather than array to skip unnecessary computing
- bucket
983. Minimum Cost For Tickets
N variable
如果遞迴關係只固定用到前N個,例如
可以不用存整個input size的memo
只需要存N個,退化成像是prefix sum的結構。
Binary Search
template:
1552. Magnetic Force Between Two Balls
1482. Minimum Number of Days to Make m Bouquets
1300. Sum of Mutated Array Closest to Target valid() 難寫
…
410. Split Array Largest Sum (Hard)
1044. Longest Duplicate Substring (Hard)
668. Kth Smallest Number in Multiplication Table (Hard)
719. Find K-th Smallest Pair Distance (Hard)
33. Search in Rotated Sorted Array
MISC
gcd
多個gcd:
lcm: