Algorithm
Leetcode ALG study plan list I
- Day 1 Binary Search
- Day 2 Two Pointers
- Day 3 Two Pointers
- Day 4 Two Pointers
class Solution {
public:
int search(vector<int>& nums, int target) {
int lo=0, hi=nums.size() - 1, mid;
while (lo <= hi) {
mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
};
class Solution {
public:
int firstBadVersion(int n) {
int lo=0, hi=n, mid;
while (lo < hi){
mid = lo + (hi - lo) / 2;
if (isBadVersion(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
};
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int lo = 0, hi = nums.size(), mid;
while (lo < hi){
mid = lo + (hi - lo) / 2;
if (nums[mid] >= target) hi = mid;
else lo = mid + 1;
}
return lo;
}
};
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
vector<int> result;
while (l <= r) {
if (abs(nums[l]) < abs(nums[r]))
result.push_back(nums[r] * nums[r--]);
else
result.push_back(nums[l] * nums[l++]);
}
reverse(result.begin(), result.end());
return result;
}
};
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
int prev, curr, next, temp;
k %= n;
for (int start=0; start < gcd(n, k); start++){
curr = start, prev = nums[start];
while (true) {
next = (curr + k) % n;
temp = nums[next];
nums[next] = prev;
prev = temp;
curr = next;
if (curr == start) break;
}
}
}
};
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int l = 0, r = 0;
while (r < nums.size()) {
while (r < nums.size() and nums[r] == 0) r++;
if (r < nums.size()) swap(nums[l], nums[r]);
l++;
r++;
}
}
};
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int l = 0, r = numbers.size() - 1;
vector<int> result;
while (l < r) {
int s = numbers[l] + numbers[r];
if (s == target) {
result.push_back(l+1);
result.push_back(r+1);
break;
}
if (s > target) r--;
if (s < target) l++;
}
return result;
}
};
Leetcode ALG study plan list III
- Day 1 Binary Search
- 1060. Missing Element in Sorted Array
- Binary search on co-domain
- 1901. Find a Peak Element II
- Binary search on un sorted co-domain, only looking for a local min/max
- 1060. Missing Element in Sorted Array
- Day 2 Binary Search
- 1231. Divide Chocolate
- Binary search on boolean co-domain.
- 1182. Shortest Distance to Target Color
- Binary search on sorted array, careful with the two possiblilites.
- Sweep Line is better. Do both direction, annotate each location with min distance to targets.
- 1231. Divide Chocolate
- Day 3 Two Pointers
- 287. Find the Duplicate Number
- Cycle detection. First phase slow meets fast. Second phase, reset slow, set fast to slow speed. When they meet again.
- 1229. Meeting Scheduler
- Sort two peoples schedule and do two pointers sweep line. min(e1, e2) >= max(s1, s2) + d then return. Otherwise, advance the people with smallest e.
- Can be done with min priority queue, push all opening longer than duration on to it. keep checking the top two. Since one person’s schedule don’t allow overlap, if overlap, they must be two people.
- 287. Find the Duplicate Number
- Day 4 Two Pointers
- 42. Trapping Rain Water
- Sweep Line. Bidirection with a level line. level line is max(level, min(l, r)), it never goes down, and only goes as if both side archieve this new height. Alwasy move the shorter side
- 1868. Product of Two Run-Length Encoded Arrays
- For each RLE, use two variables indicating the ith entry we are accessing and how many of it used up already.
- 42. Trapping Rain Water
- Day 5 Sliding Window
- 159. Longest Substring with At Most Two Distinct Characters
- Sliding window with hashmap. Hash char to count, maintain a window with at most two keys.
- 340. Longest Substring with At Most K Distinct Characters
- Sliding window with hashmap, or better LRU (LinkedHashMap/orderedDict).
- 159. Longest Substring with At Most Two Distinct Characters
- Day 6 Sliding Window
- 1004. Max Consecutive Ones III
- Sliding window with a counter.
- 239. Sliding Window Maximum
- Sliding window with monotonic queue.
- 1004. Max Consecutive Ones III
- Day 7 Breadth-First Search / Depth-First Search
- 286. Walls and Gates
- BFS for shortest path.
- 417. Pacific Atlantic Water Flow
- DFS for reachability.
- 286. Walls and Gates
- Day 8 Breadth-First Search / Depth-First Search
- 1469. Find All The Lonely Nodes
- BFS/DFS, check xor between two childrens each node in the tree.
- 582. Kill Process
- Make parent pid to children pids mapping. Then DFS/BFS from killed pid.
- 1469. Find All The Lonely Nodes
- Day 9 Breadth-First Search / Depth-First Search
- 863. All Nodes Distance K in Binary Tree
- Traverse once to generate parent pointers. Then BFS from target node for K rounds.
- 752. Open the Lock
- BFS for shortest path to target
- 863. All Nodes Distance K in Binary Tree
- Day 10 Breadth-First Search / Depth-First Search
- 1319. Number of Operations to Make Network Connected
- DFS connected components count
- 1368. Minimum Cost to Make at Least One Valid Path in a Grid
- 0-1 BFS
- 1192. Critical Connections in a Network
- DFS cycle detection, backtrack back depth.
- 1319. Number of Operations to Make Network Connected
- Day 11 Recursion / Backtracking
- 254. Factor Combinations
- Backtrack on [list of factors, previous factor, remainder], choice is new factor in range(previous factor, remainder ** .5)
- 394. Decode String
- When encounter [ recurse call with index + 1, return string built and index. Can be solved with stack too.
- 254. Factor Combinations
- Day 12 Recursion / Backtracking
- 51. N-Queens
- Candidate / state is the set of queen position. Go row by row, at given row consider each valid column and dfs on.
- main diagonal and off diagnoal can be identified by r + c and r - c
- 37. Sudoku Solver
- Candidate / state is board. Go through each unfilled locations, consider each valid guess and dfs on.
- the subbox given point is in is range(r // 3 * 3, r // 3 * 3 + 3), range(c // 3 * 3, c // 3 * 3 + 3)
- 51. N-Queens
- Day 13 Recursion / Backtracking
- Day 14 Recursion / Backtracking
- 301. Remove Invalid Parentheses
- Backtrack
- 489. Robot Room Cleaner
- Backtrack
- 301. Remove Invalid Parentheses
- Day 15 Divide and Conquer
- 53. Maximum Subarray
- Greedy. Abandon a prefix when window sum + num < num.
- 4. Median of Two Sorted Arrays
- Binary Search
- 315. Count of Smaller Numbers After Self
- Binary Search
- 53. Maximum Subarray
- Day 16 Dynamic Programming
- 309. Best Time to Buy and Sell Stock with Cooldown
- DP state is max_profit with hold, sold, rest
- 714. Best Time to Buy and Sell Stock with Transaction Fee
- DP state is max_profit with hold, sold
- 309. Best Time to Buy and Sell Stock with Cooldown
- Day 17 Dynamic Programming
- 410. Split Array Largest Sum
- Verify a guess in O(N), apply binary search.
- 337. House Robber III
- DFS
- 410. Split Array Largest Sum
- Day 18 Dynamic Programming
- 221. Maximal Square
- f(i, j) = max side length of square with bottom right corner at (i, j)
- 85. Maximal Rectangle
- Precompute maximum height from top(or bottom or left or right) at each location. Then use largest rectangle area functions to columns(or rows).
- 221. Maximal Square
- Day 19 Dynamic Programming
- 486. Predict the Winner
- dp[l][r] = max(nums[l] - dp[l+1][r], nums[r] - dp[l][r-1]) - if l != r = dp[l][r] = nums[l] if l == r
- 131. Palindrome Partitioning
- Backtracking is optimal
- 132. Palindrome Partitioning II
- DP with center expansion
- 486. Predict the Winner
- Day 20 Dynamic Programming
- Day 21 Dynamic Programming
- 123. Best Time to Buy and Sell Stock III
- DP / State transition
- 174. Dungeon Game
- 2D DP / reverse the problem, from bottom right to top left, relaxation
- 123. Best Time to Buy and Sell Stock III
- Day 22 Topological Sort
- Day 23 Topological Sort
- Day 24 Topological Sort
- Day 25 Bit Manipulation
- Day 26 Others
- Day 27 Others
1868. Product of Two Run-Length Encoded Arrays
class Solution:
def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:
i1 = i2 = u1 = u2 = 0
result = []
while i1 < len(encoded1) and i2 < len(encoded2):
(v1, c1), (v2, c2) = encoded1[i1], encoded2[i2]
n1, n2 = c1 - u1, c2 - u2
product, reps = v1 * v2, min(n1, n2)
if result and product == result[-1][0]: result[-1][1] += reps
else: result.append([product, reps])
if n1 > reps: u1 += reps
else: i1 += 1; u1 = 0
if n2 > reps: u2 += reps
else: i2 += 1; u2 = 0
return result
159. Longest Substring with At Most Two Distinct Characters
class Solution:
def lengthOfLongestSubstringTwoDistinct(self, s: str, k: int = 2) -> int:
n = len(s)
max_length = 0
window = dict()
l, r = 0, 0
while r != n:
window[s[r]] = window.get(s[r], 0) + 1
while len(window) > k:
window[s[l]] -= 1
if window[s[l]] == 0: window.pop(s[l])
l += 1
max_length = max(max_length, r - l + 1)
r += 1
return max_length
340. Longest Substring with At Most K Distinct Characters
class LRU(OrderedDict):
'Store items in the order the keys were last added'
def __init__(self, k):
super().__init__()
self.k = k
def add(self, key, value):
super().__setitem__(key, value)
self.move_to_end(key)
def pop(self):
if len(self) <= self.k: return None
_, v = self.popitem(last=False)
return v
class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
if not s or not k: return 0
max_len = 0
l = -1
window = LRU(k)
for r, char in enumerate(s): # O(N)
window.add(char, r)
pos = window.pop()
if pos is not None: l = pos
max_len = max(max_len, r-l)
return max_len
1469. Find All The Lonely Nodes
class Solution:
def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:
lonely = []
stack = [root]
while stack:
node = stack.pop()
if node.left and not node.right: lonely.append(node.left.val)
if node.right and not node.left: lonely.append(node.right.val)
if node.left: stack.append(node.left)
if node.right: stack.append(node.right)
return lonely
863. All Nodes Distance K in Binary Tree
class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
parents = {root: None}
stack = [root]
while stack:
node = stack.pop()
for child in [node.left, node.right]:
if not child: continue
parents[child] = node
stack.append(child)
visited = set([target])
queue = deque([target])
for _ in range(k):
for i in range(len(queue)):
node = queue.popleft()
for next_node in [node.left, node.right, parents[node]]:
if not next_node or next_node in visited: continue
queue.append(next_node)
visited.add(next_node)
return [nd.val for nd in queue]
752. Open the Lock
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
if target in deadends or "0000" in deadends: return -1
def get_nei(n):
if n == "0": return "19"
if n == "9": return "08"
return f"{int(n)+1}{int(n)-1}"
def get_next(state):
for i in range(4):
for n in get_nei(state[i]):
new_state = state[:i] + n + state[i+1:]
yield new_state
seen = set()
queue = deque(["0000"])
k = 0
while queue:
for _ in range(len(queue)):
state = queue.popleft()
if state == target: return k
for new_state in get_next(state):
if new_state in seen or new_state in deadends: continue
seen.add(new_state)
queue.append(new_state)
k += 1
return -1
1319. Number of Operations to Make Network Connected
class Solution:
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
if len(connections) < n - 1: return -1
n_components = 0
adj_list = defaultdict(set)
for p1, p2 in connections:
adj_list[p1].add(p2)
adj_list[p2].add(p1)
visited = set()
for p in range(n):
if p in visited: continue
n_components += 1
stack = [p]
while stack:
pc = stack.pop()
if pc in visited: continue
visited.add(pc)
stack.extend(adj_list[pc])
return n_components - 1
1192. Critical Connections in a Network
class Solution:
def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
# graph processing from edge lists to adjacency lists
adj_lists = defaultdict(set)
for n1, n2 in connections:
adj_lists[n1].add(n2)
adj_lists[n2].add(n1)
connections = set(tuple(sorted(edge)) for edge in connections)
rank = dict()
def dfs(node, depth):
if node in rank: return rank[node]
rank[node] = depth
min_back_depth = n
for neighbor in adj_lists[node]:
if rank.get(neighbor, None) == depth - 1: continue
back_depth = dfs(neighbor, depth + 1)
if back_depth <= depth:
connections.discard(tuple(sorted((node, neighbor))))
min_back_depth = min(min_back_depth, back_depth)
return min_back_depth
dfs(0, 0)
return list(connections)
51. N-Queens
class Solution:
def solveNQueens(self, n):
rows = ["." * c + "Q" + "." * (n - c - 1) for c in range(n)]
queens = [None] * n
columns = [0] * n
main_diag, off_diag = [0] * (2 * n), [0] * (2 * n)
def add_queen(r, c):
queens[r] = c
main_diag[r + c] = 1
off_diag[r - c + n] = 1
columns[c] = 1
def remove_queen(r, c):
queens[r] = None
main_diag[r + c] = 0
off_diag[r - c + n] = 0
columns[c] = 0
def valid(r, c):
if columns[c]: return False
if main_diag[r + c]: return False
if off_diag[r - c + n]: return False
return True
def form_board(queens):
board = [rows[c] for c in queens]
return board.copy()
def backtrack(queens, r):
if r == n: return solution.append(form_board(queens))
for c in range(n):
if not valid(r, c): continue
add_queen(r, c)
backtrack(queens, r + 1)
remove_queen(r, c)
solution = []
backtrack(queens, 0)
return solution
37. Sudoku Solver
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
nrow, ncol = len(board), len(board[0])
digits = set('123456789')
not_visited = [(r, c) for r in range(9) for c in range(9) if board[r][c] == '.']
def valid_choices(r, c):
row = board[r]
col = [board[i][c] for i in range(9)]
square = [board[i][j] for i in range(r // 3 * 3, r // 3 * 3 + 3)
for j in range(c // 3 * 3, c // 3 * 3 + 3)]
choices = digits.difference(row).difference(col).difference(square)
return choices
def backtrack(board, not_visited):
if not not_visited: return True
(r, c) = not_visited.pop()
for digit in valid_choices(r, c):
board[r][c] = digit
if backtrack(board, not_visited): return True
board[r][c] = '.'
not_visited.append((r, c))
return False
backtrack(board, not_visited)
10. Regular Expression Matching
- DP
- Hard
- O(MN)
DP[i,j] isMatch s[i:-1] and p[j:-1]
class Solution:
def isMatch(self, s: str, p: str) -> bool:
@cache
def dp(i, j):
if j == len(p): return i == len(s)
single_char_match = i < len(s) and p[j] in [s[i], '.']
if j + 1 < len(p) and p[j + 1] == '*':
return dp(i, j + 2) or (single_char_match and dp(i + 1, j))
return single_char_match and dp(i + 1, j + 1)
return dp(0, 0)
def isMatch(self, s, p):
dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
dp[-1][-1] = True
for i in reversed(range(len(s) + 1)):
for j in reversed(range(len(p))):
single_char_match = i < len(s) and p[j] in [s[i], '.']
if j + 1 < len(p) and p[j + 1] == '*':
dp[i][j] = dp[i][j+2] or (single_char_match and dp[i + 1][j])
else:
dp[i][j] = single_char_match and dp[i+1][j+1]
return dp[0][0]
241. Different Ways to Add Parentheses
- Recurrsion
- Medium
- O(2^N)
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
nums, ops = [], []
num = 0
for c in expression:
if c.isdigit(): num = 10 * num + int(c)
else:
ops.append(c)
nums.append(num)
num = 0
nums.append(num)
@cache
def calculate(l, r):
if l == r: return [nums[l]]
result = []
for k in range(l, r):
result.extend([
eval(f"l_val {ops[k]} r_val")
for l_val, r_val in product(
calculate(l, k),
calculate(k + 1, r)
)
])
return result
total = calculate(0, len(nums) - 1)
return total
309. Best Time to Buy and Sell Stock with Cooldown
class Solution:
def maxProfit(self, prices: List[int]) -> int:
hold, sold, rest = -prices[0], 0, 0
for price in prices:
hold, sold, rest = max(hold, rest - price), hold + price, max(rest, sold)
return max(hold, sold, rest)
714. Best Time to Buy and Sell Stock with Transaction Fee
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
sold, hold = 0, -prices[0]
for price in prices[1:]:
sold, hold = max(sold, hold + price - fee), max(hold, sold - price)
return sold
1136. Parallel Courses
class Solution:
def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
taken = set()
edge_list = defaultdict(set)
n_prereqs = defaultdict(int)
for pre, seq in relations:
edge_list[pre].add(seq)
n_prereqs[seq] += 1
curr_semester = set(range(1, n + 1)) - set([seq for pre, seq in relations])
if not curr_semester: return -1
semester = 0
while curr_semester:
semester += 1
next_semester = set()
for course in curr_semester:
if course in taken: return -1
for seq in edge_list[course]:
n_prereqs[seq] -= 1
if n_prereqs[seq] == 0:
next_semester.add(seq)
taken.update(curr_semester)
curr_semester = next_semester
return semester if len(taken) == n else -1
1396. Design Underground System
class UndergroundSystem:
def __init__(self):
self.ids = set()
self.memo = dict()
self.avg_time = dict()
def checkIn(self, id: int, stationName: str, t: int) -> None:
if id in self.ids: return
self.ids.add(id)
self.memo[id] = (stationName, t)
def checkOut(self, id: int, stationName: str, t: int) -> None:
if id not in self.ids: return
self.ids.remove(id)
start_station, start_time = self.memo[id]
self.memo.pop(id)
end_station, end_time = stationName, t
route = (start_station, end_station)
delta_t = end_time - start_time
average_time, count = self.avg_time.get(route, (0, 0))
self.avg_time[route] = ((average_time * count + delta_t) / (count + 1), count + 1)
def getAverageTime(self, startStation: str, endStation: str) -> float:
return self.avg_time[(startStation, endStation)][0]