## Leetcode ALG study plan list I

1. Day 1 Binary Search
2. Day 2 Two Pointers
3. Day 3 Two Pointers
4. 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 lo=0, hi=n, mid;
while (lo < hi){
mid = lo + (hi - lo) / 2;
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

1. Day 1 Binary Search
2. Day 2 Binary Search
3. 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.
4. 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.
5. Day 5 Sliding Window
6. Day 6 Sliding Window
7. Day 7 Breadth-First Search / Depth-First Search
8. Day 8 Breadth-First Search / Depth-First Search
9. Day 9 Breadth-First Search / Depth-First Search
10. Day 10 Breadth-First Search / Depth-First Search
11. 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.
12. 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)
13. Day 13 Recursion / Backtracking
14. Day 14 Recursion / Backtracking
15. Day 15 Divide and Conquer
16. Day 16 Dynamic Programming
17. Day 17 Dynamic Programming
18. 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).
19. Day 19 Dynamic Programming
20. Day 20 Dynamic Programming
21. Day 21 Dynamic Programming
22. Day 22 Topological Sort
23. Day 23 Topological Sort
24. Day 24 Topological Sort
25. Day 25 Bit Manipulation
26. Day 26 Others
27. 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

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)
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)

return [nd.val for nd in queue]


### 752. Open the Lock

class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
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
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

for p1, p2 in connections:

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

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
for n1, n2 in connections:

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
if rank.get(neighbor, None) == depth - 1: continue

back_depth = dfs(neighbor, depth + 1)
if back_depth <= depth:
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)

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
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)


### 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:
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:
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.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]