Leetcode category

tags: `interview`

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

input 的數量或是值有限:

counting sort
binary search
segment tree

找出答案的決策流程很複雜:

backtracking
DP
- 知道 subproblem 的答案的話可以幫助算出原問題嗎?
- backtracking 的 solution 可以 memoize 嗎?
greedy
monostack

input 之間有 connection 的概念:

union find
- https://leetcode.com/problems/last-day-where-you-can-still-cross/
- https://leetcode.com/problems/bricks-falling-when-hit/
graph alg

input 是 sorted 或是可以 sort:

sort + greedy
binary search
two pointers (find sum)

需要 partially sorted:

priority queue with size limited to k
- O(nlogk)/O(k)
quick select
- O(n) in avg/O(1) iterative

最短路徑 / 最少開銷從 A 到 B:

BFS (equally weighted edge)
- O(V+E)/O(V+E)
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

有大小、先後關係，要求排列或是否矛盾:

topological sort

Dynamic Programming:

問自己假設知道 subproblem 的答案，能夠解出現在問題的答案嗎？
Reverse thinking，從 N -> 0
- 如果為了節省空間，只存前一個 subproblem，而宣告一堆變數來暫存 state 時，想想能不能倒著做(從 n 到 0)，讓 state 在更新前就使用完就不用暫存了
- https://leetcode.com/problems/pascals-triangle-ii/
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)
- https://leetcode.com/problems/find-the-shortest-superstring/
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. 迴圈

迴圈最後要加的東西沒有加進











ans = []
acc = 0
for i in range(n):
    if arr[i] match condition:
        ans.append(acc)
        acc = 0
    else:
        acc += 1
# make sure the last part is added.
if acc > 0:
    ans.append(acc)

記得迴圈用的區域變數不要跟其他變數衝突



def func(k):
    for k, v in mp.items():
        # k is overrided!

2. Boolean

檢查 AND/OR 不要搞反

小心 short circuit

如果 dfs(left)==False，dfs(right) 就不會執行：


return dfs(left) and dfs(right)

如果有些邏輯是不管怎樣都要對每個 node 執行，務必寫成這樣：



l = dfs(left)
r = dfs(right)
return l and r

3. Complexity

permutation:
$n!$

combination:
$2^{n}$

dfs for "path":
$2^{n}$




def dfs(i):
    vis[i] = 1
    dfs(next)
    vis[i] = 0

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)
- T(n) = T(n-1) + O(1)
O(nlogn)
- T(n) = 2T(n/2) + O(n)
O(logn)
- T(n) = T(n/2) + O(1)
O(n2)
- T(n) = T(n/2) + O(n2)

Data structures

priority queue
stack
hash map
hash set
segment tree
trie

Category

Knapsack

0/1 knapsack

find number of valid subset
https://leetcode.com/problems/profitable-schemes/
find least item used

unbounded knapsack

find least item used
https://leetcode.com/problems/coin-change/
find number of valid subset
https://leetcode.com/problems/coin-change-2/

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 指向最後一個 ?

0000111????????2222
    ^  ^      ^
    L  M      R

def dutchsort(arr):
    def swap(i, j):
        arr[i], arr[j] = arr[j], arr[i]

    l = m = 0
    r = len(arr)-1
    while m <= r:
        if arr[m] == 0:
            swap(m, l)
            l += 1
            m += 1
        elif arr[m] == 1:
            m += 1
        else:
            swap(m, r)
            r -= 1

majority voting

https://leetcode.com/problems/majority-element-ii/

linked list cycle

https://leetcode.com/problems/linked-list-cycle-ii/

prefix sum

sliding window / 2-3 pointers

快慢 pointer
- 滿足條件的最小 subarray
左右 pointer 往中間夾
- sorted 找 target

hash map (2Sum)

在 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.






left = [-1] * n            
for i in range(1, n):
    p = i - 1
    while p >= 0 and nums[p] >= nums[i]:
        p = left[p]
    left[i] = p

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

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:










int n = input.size();
int l = 0;
int r = 0;
for (int r = 0; r < n; r++) {
  while (l <= r && match(input, l, r)) {
    // do something.
    l++;
  }
}

`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

dfs:























vector<int> sorted;
bool dfs(int n, vector<vector<int>>& g, vector<int>& vis) {
    // Check visited.
    if (vis[c]==1) return true;
    if (vis[c]==2) return false;
    
    vis[n] = 1;
    for (int c: g[n])
      if (dfs(c, g, vis)) return true;
    vis[n] = 2;

    sorted.push_back(n);
    return false;
}

void main() {
    for (int i = 0; i < n; i++)
        if (dfs(i, g, vis)) {
            cout << "has cycle" << endl;
            return;
        }
    reverse(sorted.begin(), sorted.end());
}

bfs:





























vector<int> sorted;
vector<int> degree(n);
vector<vector<int>> g(n);
for (auto e: edges) {
    degree[e[1]]++;
    g[e[0]].push_back(e[1]);
}

queue<int> q;
for (int i = 0; i < n; i++)
    if (degree[i]==0) q.push(i);

int seen = 0;
while (!q.empty()) {
    seen++;
    int f = q.front();
    sorted.push_back(f);
    q.pop();
    for (int neighbor: g[f]) {
        degree[neighbor]--;
        if (degree[neighbor]==0) q.push(neighbor);
    }
}

if (seen!=n) {
    cout << "has cycle!" << endl;
    return;
}

1591. Strange Printer II
- discussion
329. Longest Increasing Path in a Matrix
- single source shortest path
1857. Largest Color Value in a Directed Graph

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的缺點是你不知道從左到右的路上

_
 \_????_...
   \xx/     
    --
01234567

遇到小水坑你只能蒐集這個水坑裡的水(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

vector<vector<int>> table(n);

for (int i = 0; i < n; i++) {
  table[i] = vector<int> (i+1, 1);
  for (int j = 1; j < i; j++) {
    table[i][j] = table[i-1][j-1] + table[i-1][j]];
  }
}

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

void permute(vector<int>& a, int l, int r) {
    if (l==r) {
        // one permutation.
        return;
    }
    for (int i = l; i <= r; i++) {
        swap(a[l], a[i]);
        permute(a, l+1, r);
        swap(a[i], a[l]);
    }
}

void btrack(vector<int>& arr, int index = 0) {
  for (int i = index + 1; i < arr.size(); i++) {
    btrack(arr, i)
  }
}

Segment Tree

https://leetcode.com/tag/segment-tree/

307. Range Sum Query - Mutable

Fenwick Tree

Need to be 1-based

range query + node 會swap位置
1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits

只加下一個 parent


























# 假設tree已經有原始資料
def build(arr):
    tree = [0] + arr
    for i in range(tree[1:]):
        j += lsb(i)
        if j < len(tree):
            tree[j] += tree[i]
    return tree

def query(tree, l, r):
    def prefix(i):
        res = 0
        while i:
            res += tree[i]
            i -= lsb(i)
        return res
        
    return prefix(r) - prefix(l-1)

def update(tree, i, val):
    while i < len(tree):
        tree[i] += val
        i += lsb(i)

def lsb(x):
    return x & -x

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) {
    // case 1. covered by left.
    return query(tree, idx<<1, l, m, i, j);
  } else if (m < i) {
    // case 2. covered by right.
    return query(tree, idx<<1|1, m+1 ,r, i, j);
  } else {
    // case 3. a mix.
    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);
  // 要1-index!
  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 the node is not lazy.
    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;

    // fully covered by query range.
    if (l>=i && r<=j) {
        // suppose the merge is addition.
        tree[idx] += (r-l+1) * val;
        lazy[idx<<1] += val;
        lazy[idx<<1|1] += val;
        return;
    }

    // mix
    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);
    }

    // mix.
    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

327. Count of Range Sum
- inplace_merge(begin, middle, end)

Quick sort

148. Sort List

Random

470. Implement Rand10() Using Rand7()

String

316. Remove Duplicate Letters
Greedy + string

KMP

youtube
template:

int kmp(string s, string p) {

  // build KMP table (longest proper prefix).
  int lps[p.size()];
  lps[0] = 0;
  int i = 0, j = 1;
  while (j < p.size()) {
    if (p[i] != p[j]) {
      if (i!=0) {
        i = lps[i-1];
        continue;
      }
      lps[j] = 0;
      i = 0;
    } else {
      lps[j] = i + 1;
      i++;
    }
    j++;
  }

  // start matching.
  int pi = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == p[pi]) {
      if (++pi == p.size()) return i - p.size();
    } else {
      if (pi==0) continue;

      pi = lps[pi-1];
      i--;
    }
  }
  return -1;
}

28. Implement strStr()
796. Rotate String

palindrome

214. Shortest Palindrome
看回文 abc#bca

5. Longest Palindromic Substring
336. Palindrome Pairs

Rabin Karp

power 的部分可以用%prime來防止overflow

for (i = 1 ; i < S.length(); i++)
  power[i] = (power[i - 1] * 26) % prime;

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:

class UF {
public:
  vector<int> uf;
  
  UF(int n) {
    uf = vector<int>(n);
    for (int i = 0; i < n; i++)
      uf[i] = i;
  }
  
  void uni(int x, int y) {
    uf[find(y)] = uf[find(x)];
  }
  
  int find(int x) {
    // path compression
    if (uf[uf[x]] != uf[x]) {
      uf[x] = find(uf[x]);
    }
    return uf[x];
  }
}

924. Minimize Malware Spread
- union 完之後還是要再每一個node都find一次才會達到path compression
947. Most Stones Removed with Same Row or Column
- 決定union的方式比較複雜
1579. Remove Max Number of Edges to Keep Graph Fully Traversable
- 多個union find
1584. Min Cost to Connect All Points
- mst

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

221. Maximal Square
84. Largest Rectangle in Histogram
85. Maximal Rectangle
887. Super Egg Drop
1594. Maximum Non Negative Product in a Matrix
- 乘法找最大
- 處理負數的case，不能像加法單純存subproblem的最大值
1626. Best Team With No Conflicts
- dp[i]存1~i並且選擇i最大的解
- 最佳解不是dp[n]而是max(dp[0...n])
1130. Minimum Cost Tree From Leaf Values
- tree
- divide&conquer
- 兩種運算: 加和乘
- ＊任意相鄰的leaf都能配對在同一個parent下
- 例如[1,2,3,4]，2,3是可以配對在一起的
```
 x
| \
x  4
| \
1  x
   |\
   2 3
```
- 仔細觀察可以發現能用stack做(GREEDY思維)

template:

Bottom-up (tabulation)

int main() {
  for (i)
    for (j)
      for (k in i+1 to j) {
        dp[i][j] = f(dp[i][k], dp[k][y]);
      }
  return dp[i][j];
}

Top Down (memoization)

int topdown(i, j) {
  for (k in i+1 to j) {
    // memoization
    int dpik, dpkj;
    if (dp[i][k] != -1) dpik = dp[i][k];
    else dpik = topdown(i, k);
    if (dp[k][k] != -1) dpkj = dp[k][j];
    else dpkj = topdown(k, j);
    
    dp[i][j] = f(dpik, dpkk);
  }
  return dp[i][j];
}

int main() {
  return topdown(0, size-1);
}

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

int d2, d3;
if (mp.find(n/2) != mp.end()) {
  d2 = mp[n/2];
} else {
  d2 = minDays(n/2);
}
if (mp.find(n/3) != mp.end()) {
  d3 = mp[n/3];
} else {
  d3 = minDays(n/3);
}
mp[n] = 1 + min(n%2 + d2, n%3 + d3);

983. Minimum Cost For Tickets

N variable

如果遞迴關係只固定用到前N個，例如

dp[i] = someFunc(dp[i-1], dp[i-2], ..., dp[i-N]);

可以不用存整個input size的memo
只需要存N個，退化成像是prefix sum的結構。

Binary Search

template:

// Initially
L                                         R
v                                         v
[      valid      ] [       invalid       ]

// Finally
                  R L
                  v v
[      valid      ] [       invalid       ]

bool valid(int m) {
}

// find the largest valid
int binarySearch(int l, int r) {
  while (l <= r) {
    int mid = l + (r-l)/2;
    if (valid(mid)) l = mid + 1;
    else r = mid - 1;
  }
  return r;
}

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








int gcd(int a, int b) {
  while (b > 0) {
    int tmp = a % b;
    a = b;
    b = tmp;
  }
  return a;
}

多個gcd:





arr=[12,45,26,90,68...]
g=arr[0]
for a in arr:
    g = gcd(g, a)
return g

lcm:










int lcm(int a, int b) {
  return a * b / gcd(a, b);
}

int lcm(vector<int> a) {
  int l = a[0];
  for (int i = 1; i < a.size(); i++)
    l = lcm(l, a[i]);
  return l;
}

858. Mirror Reflection
1589. Maximum Sum Obtained of Any Permutation
range: 1-n, m個區間
1094. Car Pooling
求每個位置被多少個區間包住 O(n)：

for (int[] r: interval) {
    count[r[0]] += 1;
    if (r[1] + 1 < n)
        count[r[1] + 1] -= 1;
}
for (int i = 1; i < n; ++i)
    count[i] += count[i - 1];

Leetcode category

tags: interview

General SOP

Asking Clarifying Questions (2 mins)

Proposing valid solution (8-10 mins)

Code & Implement (5 mins)

Dry run (5 mins)

When stuck

Reactions to scenario

input 的數量或是值有限:

找出答案的決策流程很複雜:

input 之間有 connection 的概念:

input 是 sorted 或是可以 sort:

需要 partially sorted:

最短路徑 / 最少開銷從 A 到 B:

tree:

constant space (不能用額外 data structure):

get max/min:

subset:

palindrome:

有大小、先後關係，要求排列或是否矛盾:

Dynamic Programming:

Clarifying questions

Common mistake

1. 迴圈

2. Boolean

檢查 AND/OR 不要搞反

小心 short circuit

3. Complexity

permutation: n!

combination: 2n

dfs for "path": 2n

Time Complexity

Data structures

Category

Knapsack

0/1 knapsack

unbounded knapsack

Array

Quickselect

Dutch National Flag

majority voting

linked list cycle

prefix sum

sliding window / 2-3 pointers

hash map (2Sum)

left/right extend arr

reverse all + reverse partial 技巧

square root decomposition

Priority Queue

Game / MinMax

Rectangles

Stack

Monotonic Queue

Floyd-Warshall

Counting sort

Sliding Window

map::lower_bound, map::upper_bound

Unicode character

Longest Increasing Subsequence

Topological

Trie

Prefix Sum

Kadane's algorithm

Two pointer

Linked List

Bucket

Permutation

Pascal Traingle

Backtracking

Segment Tree

Fenwick Tree

Segment Tree

Array based

lazy propagation

Bit manipulation

Merge Sort

Quick sort

Random

String

tags: `interview`

permutation:
$n!$

combination:
$2^{n}$

dfs for "path":
$2^{n}$

`map::lower_bound`, `map::upper_bound`