Neetcode2H2

Cheatsheet Content

1. Minimum Obstacle Removal to Reach Corner (BFS/Dijkstra) Notes: This is a 0-1 BFS problem. Since obstacle removal costs 1 and no obstacle costs 0, a deque-based BFS (0-1 BFS) or Dijkstra's algorithm can find the shortest path. Use a deque to prioritize 0-cost moves (add to front) over 1-cost moves (add to back). import collections import heapq class Solution: def minimumObstacles(self, grid: list[list[int]]) -> int: rows, cols = len(grid), len(grid[0]) dist = [[float('inf')] * cols for _ in range(rows)] dist[0][0] = 0 # 0-1 BFS using deque dq = collections.deque([(0, 0, 0)]) # (cost, r, c) while dq: cost, r, c = dq.popleft() if r == rows - 1 and c == cols - 1: return cost for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols: new_cost = cost + grid[nr][nc] if new_cost < dist[nr][nc]: dist[nr][nc] = new_cost if grid[nr][nc] == 0: dq.appendleft((new_cost, nr, nc)) else: dq.append((new_cost, nr, nc)) return -1 # Should not happen if path exists # Alternative: Dijkstra using heapq import heapq class Solution: def minimumObstacles(self, grid: list[list[int]]) -> int: rows, cols = len(grid), len(grid[0]) dist = [[float('inf')] * cols for _ in range(rows)] dist[0][0] = 0 pq = [(0, 0, 0)] # (cost, r, c) while pq: cost, r, c = heapq.heappop(pq) if cost > dist[r][c]: continue if r == rows - 1 and c == cols - 1: return cost for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols: new_cost = cost + grid[nr][nc] if new_cost < dist[nr][nc]: dist[nr][nc] = new_cost heapq.heappush(pq, (new_cost, nr, nc)) return -1 2. Trapping Rain Water II (Multi-source BFS/Dijkstra) Notes: This is an extension of "Trapping Rain Water" to 2D. Imagine water filling from the 'lowest' cells on the border. Use a min-priority queue to process cells with the smallest height first. The water level at any internal cell is limited by the minimum height of its surrounding 'walls'. import heapq class Solution: def trapRainWater(self, heightMap: list[list[int]]) -> int: if not heightMap or not heightMap[0]: return 0 m, n = len(heightMap), len(heightMap[0]) visited = [[False] * n for _ in range(m)] pq = [] # (height, r, c) # Add all border cells to the priority queue for r in range(m): for c in range(n): if r == 0 or r == m - 1 or c == 0 or c == n - 1: heapq.heappush(pq, (heightMap[r][c], r, c)) visited[r][c] = True water_trapped = 0 max_height_so_far = 0 # This represents the current water level while pq: height, r, c = heapq.heappop(pq) max_height_so_far = max(max_height_so_far, height) for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]: nr, nc = r + dr, c + dc if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]: visited[nr][nc] = True # If current cell is lower than max_height_so_far, it can trap water if heightMap[nr][nc] < max_height_so_far: water_trapped += (max_height_so_far - heightMap[nr][nc]) heapq.heappush(pq, (heightMap[nr][nc], nr, nc)) return water_trapped 3. Parallel Courses III (Topological Sort + DP) Notes: This problem asks for the minimum time to complete all courses. This is a classic application of topological sort (Kahn's algorithm using BFS) combined with dynamic programming. The time to complete a course depends on the completion time of its prerequisites. The DP state $dp[i]$ stores the minimum time to complete course $i$ and all its prerequisites. import collections class Solution: def minimumTime(self, n: int, relations: list[list[int]], time: list[int]) -> int: adj = collections.defaultdict(list) in_degree = [0] * (n + 1) for prev, next_course in relations: adj[prev].append(next_course) in_degree[next_course] += 1 # dp[i] will store the minimum time to complete course i # and all its prerequisites dp = [0] * (n + 1) # Initialize queue with courses that have no prerequisites q = collections.deque() for i in range(1, n + 1): if in_degree[i] == 0: q.append(i) dp[i] = time[i-1] # time array is 0-indexed while q: course = q.popleft() for next_course in adj[course]: # The time to complete next_course is its own time # plus the maximum time taken by any of its prerequisites. dp[next_course] = max(dp[next_course], dp[course] + time[next_course-1]) in_degree[next_course] -= 1 if in_degree[next_course] == 0: q.append(next_course) return max(dp) 4. Find All People With Secret (Graph Traversal + Time Sorting) Notes: The key is that secrets are shared only if people meet at the same time. Sort meetings by time. For each time slot, process all meetings. If a person knows the secret and attends a meeting, everyone in their connected component for that meeting time learns the secret. Crucially, if a person learns the secret at a specific time, they retain it. If they don't learn it, any previous secret status from a later meeting (which shouldn't be possible due to sorting) must be revoked. Use a Disjoint Set Union (DSU) or BFS/DFS for connected components. import collections class Solution: def findAllPeople(self, n: int, meetings: list[list[int]], firstPerson: int) -> list[int]: # Sort meetings by time meetings.sort(key=lambda x: x[2]) # Keep track of who knows the secret knows_secret = [False] * n knows_secret[0] = True knows_secret[firstPerson] = True i = 0 while i < len(meetings): current_time = meetings[i][2] # Find all meetings at current_time meetings_at_current_time = [] j = i while j < len(meetings) and meetings[j][2] == current_time: meetings_at_current_time.append(meetings[j]) j += 1 # Build a temporary graph for this time slot # Use a set to store unique people involved in these meetings people_in_this_time_slot = set() graph = collections.defaultdict(list) for p1, p2, _ in meetings_at_current_time: graph[p1].append(p2) graph[p2].append(p1) people_in_this_time_slot.add(p1) people_in_this_time_slot.add(p2) # BFS/DFS to propagate secret within this time slot's components q = collections.deque() for person in people_in_this_time_slot: if knows_secret[person]: q.append(person) visited_for_time_slot = set() while q: p = q.popleft() if p in visited_for_time_slot: continue visited_for_time_slot.add(p) knows_secret[p] = True # This person now knows the secret for neighbor in graph[p]: if not knows_secret[neighbor]: # Only add if not yet known via this path q.append(neighbor) # After processing all meetings at current_time, if someone # was temporarily marked as knowing the secret but wasn't connected # to an initial secret-holder in this time slot, they shouldn't know it. # This is implicitly handled by the BFS/DFS only exploring from known secret holders. # However, if DSU was used, you might need to reset non-secret holders. i = j # Move to the next time slot result = [] for k in range(n): if knows_secret[k]: result.append(k) return result 5. Minimum Number of Days to Eat N Oranges (BFS/Memoized DP) Notes: This is a shortest path problem on a graph where nodes are numbers of oranges and edges are the operations. Since $N$ can be large ($2 \times 10^9$), standard BFS is too slow. However, the number of distinct states reachable is much smaller. Use BFS with memoization (or a dictionary-based DP) to store the minimum days for each $n$ encountered. import collections class Solution: def minDays(self, n: int) -> int: memo = {} # Stores minimum days for a given number of oranges # BFS approach q = collections.deque([(n, 0)]) # (oranges, days) visited = {n} while q: current_n, days = q.popleft() if current_n == 0: return days # Option 1: Eat 1 orange if current_n - 1 not in visited: visited.add(current_n - 1) q.append((current_n - 1, days + 1)) # Option 2: Eat n/2 oranges if n % 2 == 0 if current_n % 2 == 0 and current_n // 2 not in visited: visited.add(current_n // 2) q.append((current_n // 2, days + 1)) # Option 3: Eat 2*n/3 oranges if n % 3 == 0 if current_n % 3 == 0 and current_n // 3 not in visited: visited.add(current_n // 3) q.append((current_n // 3, days + 1)) return -1 # Should not be reached # Memoized DP approach (often more efficient for large N due to implicit pruning) def minDays_dp(self, n: int) -> int: memo = {0: 0, 1: 1} # Base cases: 0 oranges -> 0 days, 1 orange -> 1 day def dp(k): if k in memo: return memo[k] # Option 1: Eat 1 orange. cost = 1 + dp(k-1) # Option 2: Eat k/2 oranges. cost = 1 + dp(k/2) if k%2==0, plus k%2 days for remaining. # Option 3: Eat 2k/3 oranges. cost = 1 + dp(k/3) if k%3==0, plus k%3 days for remaining. # The key insight for large N is that it's always optimal to reach k/2 or k/3 # by first eating 1 orange (k % 2) times or (k % 3) times. # So, for an even number k, the cost is 1 (for k/2 operation) + k%2 (for remainder) + dp(k//2) # which simplifies to 1 + dp(k//2) + (k%2) for the path to k//2 # and 1 + dp(k//3) + (k%3) for the path to k//3 res = 1 + min(dp(k // 2) + (k % 2), dp(k // 3) + (k % 3)) memo[k] = res return res return dp(n) 6. Largest Color Value in a Directed Graph (Topological Sort + DP) Notes: This problem combines topological sort with dynamic programming. Since it's a directed graph, cycles are an issue. If a cycle exists, return -1. Otherwise, use Kahn's algorithm (BFS-based topological sort). For each node, maintain a DP array $dp[node][color]$ representing the maximum count of that color on any path ending at $node$. When processing a node, update its neighbors' DP states. import collections class Solution: def largestPathValue(self, colors: str, edges: list[list[int]]) -> int: n = len(colors) adj = collections.defaultdict(list) in_degree = [0] * n for u, v in edges: adj[u].append(v) in_degree[v] += 1 # dp[node][color_idx] stores the maximum count of color_idx # on any path ending at 'node'. # color_idx: 'a'->0, 'b'->1, ..., 'z'->25 dp = [[0] * 26 for _ in range(n)] q = collections.deque() for i in range(n): if in_degree[i] == 0: q.append(i) dp[i][ord(colors[i]) - ord('a')] = 1 nodes_visited = 0 max_color_value = 0 while q: u = q.popleft() nodes_visited += 1 max_color_value = max(max_color_value, max(dp[u])) for v in adj[u]: # Update dp states for neighbor v for color_idx in range(26): # For neighbor v, the count of `color_idx` on a path ending at v # coming from u, is the count on path ending at u, plus 1 if v itself is that color. new_val = dp[u][color_idx] if color_idx == (ord(colors[v]) - ord('a')): new_val += 1 dp[v][color_idx] = max(dp[v][color_idx], new_val) in_degree[v] -= 1 if in_degree[v] == 0: q.append(v) if nodes_visited != n: return -1 # Cycle detected return max_color_value 7. Sliding Puzzle (BFS) Notes: This is a classic shortest path problem on a state graph. Each state of the puzzle (arrangement of numbers) is a node. An edge exists between two states if one can be transformed into the other by sliding the '0' tile. Use BFS to find the minimum number of moves. The state can be represented as a tuple or string to be hashable for visited set. import collections class Solution: def slidingPuzzle(self, board: list[list[int]]) -> int: target_state = (1, 2, 3, 4, 5, 0) # Convert initial board to a tuple for hashability initial_state = tuple(board[0] + board[1]) # If already solved if initial_state == target_state: return 0 # BFS queue: (current_state_tuple, zero_pos_index, moves) # zero_pos_index: 0-5 representing the position of '0' # The 2D board can be flattened to a 1D array/list: # 0 1 2 # 3 4 5 # Possible moves for '0' at each position # indices: 0, 1, 2, 3, 4, 5 # 0 <-> 1, 3 # 1 <-> 0, 2, 4 # 2 <-> 1, 5 # 3 <-> 0, 4 # 4 <-> 1, 3, 5 # 5 <-> 2, 4 moves_map = { 0: [1, 3], 1: [0, 2, 4], 2: [1, 5], 3: [0, 4], 4: [1, 3, 5], 5: [2, 4] } q = collections.deque() visited = set() # Find initial zero position zero_pos = initial_state.index(0) q.append((initial_state, zero_pos, 0)) visited.add(initial_state) while q: current_state, z_pos, moves = q.popleft() for next_z_pos in moves_map[z_pos]: # Create new state by swapping 0 with its neighbor list_state = list(current_state) list_state[z_pos], list_state[next_z_pos] = list_state[next_z_pos], list_state[z_pos] new_state = tuple(list_state) if new_state == target_state: return moves + 1 if new_state not in visited: visited.add(new_state) q.append((new_state, next_z_pos, moves + 1)) return -1 # Target not reachable 8. Maximum Number of K-Divisible Components (Tree DP / DFS) Notes: This is a tree DP problem. For each subtree, we want to know the sum of its node values modulo K. If a subtree's sum is divisible by K, we can "cut" the edge connecting it to its parent and increment our count of K-divisible components. The DP state for a node $u$ would be $dp[u] = (\sum_{v \in \text{subtree}(u)} \text{values}[v]) \pmod K$. A DFS traversal is suitable for this. The root itself can also be a component if its total sum is divisible by K. import collections class Solution: def maxKDivisibleComponents(self, n: int, edges: list[list[int]], values: list[int], k: int) -> int: adj = collections.defaultdict(list) for u, v in edges: adj[u].append(v) adj[v].append(u) self.components = 0 # DFS function returns the sum of values in the subtree rooted at 'u' modulo k def dfs(u, parent): current_subtree_sum = values[u] for v in adj[u]: if v == parent: continue current_subtree_sum += dfs(v, u) # If the current subtree sum is divisible by k, # we can form a component here. This edge (u-parent) can be cut. # We increment the component count and "reset" the current_subtree_sum # for the parent to 0, as this component is now handled. if current_subtree_sum % k == 0: self.components += 1 return 0 # This subtree forms a component, its sum doesn't propagate up return current_subtree_sum # Start DFS from node 0 (arbitrary root) with no parent (-1) # The return value of the initial DFS call matters if the entire graph is a single component. # However, the problem statement implies component count, which is handled by self.components. dfs(0, -1) return self.components 9. Maximum Number of Points From Grid Queries (Offline Queries + DSU/BFS) Notes: This problem combines grid traversal with query processing. Since queries can be answered independently, an "offline" approach (sorting queries) is often beneficial. Sort queries by their limit. As the limit increases, more cells become accessible. We can use a BFS-like approach or a Disjoint Set Union (DSU) structure to expand reachable cells and count points. Either approach involves processing cells in increasing order of their values. import heapq class Solution: def maxPoints(self, grid: list[list[int]], queries: list[int]) -> list[int]: m, n = len(grid), len(grid[0]) # Store (query_value, original_index) for sorting sorted_queries = sorted([(q, i) for i, q in enumerate(queries)]) ans = [0] * len(queries) # Priority queue for cells to visit: (cell_value, r, c) pq = [(grid[0][0], 0, 0)] visited = [[False] * n for _ in range(m)] visited[0][0] = True current_points = 0 query_idx = 0 while pq or query_idx < len(sorted_queries): query_val, original_idx = sorted_queries[query_idx] # Process all cells that are smaller than the current query_val # This is where the offline processing magic happens. # We keep expanding reachable cells as long as their value is less than query_val. while pq and pq[0][0] < query_val: val, r, c = heapq.heappop(pq) current_points += 1 for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]: nr, nc = r + dr, c + dc if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]: visited[nr][nc] = True heapq.heappush(pq, (grid[nr][nc], nr, nc)) # Now all cells reachable with value < query_val have been processed. # The current_points count is valid for this query. ans[original_idx] = current_points query_idx += 1 if query_idx == len(sorted_queries): break # All queries processed return ans 10. Stickers to Spell Word (Dynamic Programming with Bitmask) Notes: This is a variation of the "subset sum" or "knapsack" problem. Since the target word length is small (max 15), we can use a bitmask to represent the letters already "spelled" from the target word. The DP state $dp[mask]$ would be the minimum number of stickers needed to spell the letters represented by $mask$. Preprocessing stickers to count their characters helps. For each sticker, try to apply it to all possible masks. The key is to optimize how a sticker is applied: only use characters from the sticker that are needed and not yet covered by the mask. import collections class Solution: def minStickers(self, stickers: list[str], target: str) -> int: n = len(target) # Preprocess stickers into character counts sticker_counts = [] for sticker in stickers: counts = collections.Counter(sticker) sticker_counts.append(counts) # dp[mask] = minimum stickers to form letters in 'target' represented by 'mask' # mask is a bitmask of length n, where the i-th bit is 1 if target[i] is covered. dp = {} dp[0] = 0 # 0 stickers needed for an empty target (mask 0) # Use BFS-like approach to explore masks q = collections.deque([0]) while q: mask = q.popleft() # If we've reached the target mask, return its value if mask == (1 << n) - 1: return dp[mask] # Try applying each sticker for s_counts in sticker_counts: next_mask = mask temp_s_counts = s_counts.copy() # Use a copy for current sticker application # Try to use characters from the sticker to cover target letters for i in range(n): # If target[i] is not yet covered AND the sticker has target[i] if not (next_mask >> i) & 1 and temp_s_counts[target[i]] > 0: next_mask |= (1 << i) temp_s_counts[target[i]] -= 1 # Use one character # After initial greedy attempt, if the sticker has more characters, # use them to cover *other* remaining target letters (if any). # This is important: a sticker might contribute to multiple letters. # The above loop only covers letters *not yet covered*. # To fully utilize a sticker, we need to consider all its characters. # A more robust approach for `next_mask` update: # Iterate through target, and for each char, find if sticker has it. # However, the problem solution usually implies a slightly different approach. # The typical DP transition for this problem is: # `for sticker in stickers: calculate new_mask by applying sticker to current_mask` # The calculation of `new_mask` is the tricky part. # A more correct way to calculate next_mask: # Find the first uncovered character in target idx_to_cover = -1 for i in range(n): if not (mask >> i) & 1: idx_to_cover = i break if idx_to_cover == -1: # All covered continue # Only consider stickers that contain the first uncovered character if s_counts[target[idx_to_cover]] == 0: continue current_sticker_mask = mask temp_s_counts = s_counts.copy() for i in range(n): if not (current_sticker_mask >> i) & 1 and temp_s_counts[target[i]] > 0: current_sticker_mask |= (1 << i) temp_s_counts[target[i]] -= 1 if current_sticker_mask not in dp or dp[current_sticker_mask] > dp[mask] + 1: dp[current_sticker_mask] = dp[mask] + 1 q.append(current_sticker_mask) return -1 # Should not be reached if target is spelleable Correction/Simpler DP Transition for Stickers: The typical approach for next_mask involves finding the first character in target that is not yet covered by mask . Then, for each sticker, if it contains that character, apply the sticker to cover as many *remaining* characters as possible. This ensures we don't try stickers that don't help cover new characters. import collections class Solution: def minStickers(self, stickers: list[str], target: str) -> int: n = len(target) # Preprocess stickers into character counts # We only care about characters present in the target word sticker_char_counts = [] for sticker in stickers: counts = [0] * 26 for char_s in sticker: counts[ord(char_s) - ord('a')] += 1 sticker_char_counts.append(counts) # dp[mask] = minimum stickers to form letters in 'target' represented by 'mask' dp = [-1] * (1 << n) # Initialize with -1 (infinity) dp[0] = 0 # 0 stickers needed for an empty target (mask 0) # Iterate through all possible masks from 0 to (1 << n) - 1 for mask in range(1 << n): if dp[mask] == -1: # If this mask is not reachable, skip continue # Find the first character in target that is not covered by 'mask' first_uncovered_char_idx = -1 for i in range(n): if not (mask >> i) & 1: # If i-th bit is 0 (uncovered) first_uncovered_char_idx = i break if first_uncovered_char_idx == -1: # All characters are covered continue # Try applying each sticker for s_counts in sticker_char_counts: # Only consider stickers that contain the `first_uncovered_char_idx` # of the target. This prunes redundant sticker applications. # If a sticker doesn't help cover the *first* missing char, # it's better to use a sticker that does. # Convert target[first_uncovered_char_idx] to its char code char_code = ord(target[first_uncovered_char_idx]) - ord('a') if s_counts[char_code] == 0: continue # This sticker doesn't have the first needed char # Calculate the new mask by applying this sticker next_mask = mask temp_s_counts = list(s_counts) # Create a mutable copy for i in range(n): # If target[i] is not yet covered in next_mask # AND the sticker has target[i] available if not (next_mask >> i) & 1 and temp_s_counts[ord(target[i]) - ord('a')] > 0: next_mask |= (1 << i) temp_s_counts[ord(target[i]) - ord('a')] -= 1 # Update dp value if we found a shorter path if dp[next_mask] == -1 or dp[next_mask] > dp[mask] + 1: dp[next_mask] = dp[mask] + 1 return dp[(1 << n) - 1] # Return the min stickers for the full target mask 11. Divide Nodes into the Maximum Number of Groups (BFS + Bipartite Check) Notes: This problem asks to divide nodes into groups such that adjacent nodes are in adjacent groups (e.g., group $i$ and $i+1$). This is essentially a multi-level bipartite coloring problem. For each connected component, perform a BFS. During BFS, assign a 'level' or 'group number' to each node. If an edge connects two nodes that should be in the same group (i.e., same level) or whose levels differ by more than 1, it's impossible. The 'maximum number of groups' for a component is the maximum level reached. The total maximum groups is the sum of maximum groups from each component. import collections class Solution: def magnificentSets(self, n: int, edges: list[list[int]]) -> int: adj = collections.defaultdict(list) for u, v in edges: adj[u-1].append(v-1) # 0-indexed adj[v-1].append(u-1) visited = [False] * n total_max_groups = 0 for i in range(n): if not visited[i]: # Find all nodes in the current connected component component_nodes = [] q_comp = collections.deque([i]) temp_visited = [False] * n temp_visited[i] = True component_nodes.append(i) head = 0 while head < len(q_comp): u = q_comp[head] head += 1 for v in adj[u]: if not temp_visited[v]: temp_visited[v] = True q_comp.append(v) component_nodes.append(v) # For each connected component, find the max_depth (max_groups) # This needs to be done by starting BFS from *every* node in the component # to find the longest path (diameter) for that component. # The 'groups' are layers in an unweighted BFS. max_depth_in_component = 0 for start_node in component_nodes: q_bfs = collections.deque([(start_node, 1)]) # (node, depth) depths = [-1] * n depths[start_node] = 1 current_max_depth = 1 while q_bfs: u, d = q_bfs.popleft() current_max_depth = max(current_max_depth, d) for v in adj[u]: if depths[v] == -1: # Not visited in this BFS run depths[v] = d + 1 q_bfs.append((v, d + 1)) elif abs(depths[v] - d) != 1: # Bipartite check failure (or more than 1 diff) return -1 # Impossible to group max_depth_in_component = max(max_depth_in_component, current_max_depth) total_max_groups += max_depth_in_component # Mark all nodes in this component as globally visited for node in component_nodes: visited[node] = True return total_max_groups 12. Greatest Common Divisor Traversal (Disjoint Set Union + Prime Factorization) Notes: The problem states that you can traverse between $nums[i]$ and $nums[j]$ if $gcd(nums[i], nums[j]) > 1$. This means all numbers sharing a common prime factor are implicitly connected. Use DSU. For each number, find its prime factors. For each prime factor, unite the current number's index with the index of the *first* number encountered that had this prime factor. This effectively groups all numbers sharing common prime factors. Finally, check if all numbers belong to the same DSU set (i.e., if there's only one root). Edge case: numbers with value 1 are problematic as they don't share prime factors. class DSU: def __init__(self, n): self.parent = list(range(n)) self.size = [1] * n self.num_components = n def find(self, i): if self.parent[i] == i: return i self.parent[i] = self.find(self.parent[i]) return self.parent[i] def union(self, i, j): root_i = self.find(i) root_j = self.find(j) if root_i != root_j: if self.size[root_i] < self.size[root_j]: root_i, root_j = root_j, root_i self.parent[root_j] = root_i self.size[root_i] += self.size[root_j] self.num_components -= 1 return True return False class Solution: def canTraverseAllPairs(self, nums: list[int]) -> bool: n = len(nums) if n == 1: return True # Handle case where 1 is present and makes it impossible to connect if 1 in nums: return False dsu = DSU(n) # Map prime factors to the index of the first number encountered with that factor prime_to_idx = {} for i, num in enumerate(nums): # Optimized prime factorization (sqrt(num)) d = 2 temp_num = num while d * d <= temp_num: if temp_num % d == 0: if d not in prime_to_idx: prime_to_idx[d] = i else: dsu.union(i, prime_to_idx[d]) while temp_num % d == 0: temp_num //= d d += 1 if temp_num > 1: # Remaining `temp_num` is a prime factor if temp_num not in prime_to_idx: prime_to_idx[temp_num] = i else: dsu.union(i, prime_to_idx[temp_num]) # All numbers are traversable if they all belong to a single connected component return dsu.num_components == 1 13. Build a Matrix With Conditions (Topological Sort) Notes: This problem requires building a matrix where values follow two sets of conditions (row and column). Both sets of conditions define partial orders, which can be modeled as directed acyclic graphs (DAGs). The problem boils down to performing two independent topological sorts: one for rows and one for columns. The topological sort gives the correct ordering of numbers. Once the orderings are found, place numbers into the matrix accordingly. If a cycle is detected in either graph, it's impossible, return empty. import collections class Solution: def buildMatrix(self, k: int, rowConditions: list[list[int]], colConditions: list[list[int]]) -> list[list[int]]: def topological_sort(conditions): adj = collections.defaultdict(list) in_degree = [0] * (k + 1) for u, v in conditions: adj[u].append(v) in_degree[v] += 1 q = collections.deque() for i in range(1, k + 1): if in_degree[i] == 0: q.append(i) order = [] while q: node = q.popleft() order.append(node) for neighbor in adj[node]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: q.append(neighbor) # If the length of the order is not k, a cycle was detected if len(order) != k: return [] return order row_order = topological_sort(rowConditions) col_order = topological_sort(colConditions) if not row_order or not col_order: return [] # Cycle detected in either conditions # Create mapping from number to its row/col index num_to_row_idx = {num: i for i, num in enumerate(row_order)} num_to_col_idx = {num: i for i, num in enumerate(col_order)} matrix = [[0] * k for _ in range(k)] for num in range(1, k + 1): r = num_to_row_idx[num] c = num_to_col_idx[num] matrix[r][c] = num return matrix 14. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree (Kruskal + Union-Find) Notes: This problem extends Kruskal's algorithm for MST. Critical Edges: An edge is critical if its removal increases the MST weight, or makes the graph disconnected. To find critical edges, for each edge $(u, v, w)$, temporarily remove it and run Kruskal's. If the new MST weight is greater or no MST can be formed, the edge is critical. Pseudo-Critical Edges: An edge is pseudo-critical if it can be part of *some* MST, but it's not critical. To find pseudo-critical edges, for each edge $(u, v, w)$, force it into the MST (by adding it first and uniting $u, v$). Then run Kruskal's on the remaining edges. If the resulting MST weight equals the original MST weight, then this edge is pseudo-critical (or critical). The overall strategy: 1. Calculate the weight of a standard MST ($W_{MST}$). 2. For critical edges: iterate through all edges. For each edge, calculate MST weight *excluding* it. If $W_{MST\_exclude} > W_{MST}$ or no MST formed, it's critical. 3. For pseudo-critical edges: iterate through all edges. For each edge, calculate MST weight *including* it (force add). If $W_{MST\_include} == W_{MST}$, and it's not critical, it's pseudo-critical. class DSU: def __init__(self, n): self.parent = list(range(n)) self.num_components = n def find(self, i): if self.parent[i] == i: return i self.parent[i] = self.find(self.parent[i]) return self.parent[i] def union(self, i, j): root_i = self.find(i) root_j = self.find(j) if root_i != root_j: self.parent[root_i] = root_j self.num_components -= 1 return True return False class Solution: def findCriticalAndPseudoCriticalEdges(self, n: int, edges: list[list[int]]) -> list[list[int]]: # Add original index to each edge for later retrieval indexed_edges = [] for i, (u, v, w) in enumerate(edges): indexed_edges.append((w, u, v, i)) indexed_edges.sort() # Sort by weight # 1. Calculate the standard MST weight def calculate_mst_weight(block_edge_idx=-1, force_include_edge=None): dsu = DSU(n) current_mst_weight = 0 edges_count = 0 # Force include edge if specified if force_include_edge: w, u, v, original_idx = force_include_edge dsu.union(u, v) current_mst_weight += w edges_count += 1 for w, u, v, original_idx in indexed_edges: if original_idx == block_edge_idx: # Skip this edge continue if force_include_edge and original_idx == force_include_edge[3]: # Already added continue if dsu.union(u, v): current_mst_weight += w edges_count += 1 # Check if all nodes are connected if dsu.num_components == 1: return current_mst_weight else: return float('inf') # No MST formed standard_mst_weight = calculate_mst_weight() critical_edges = [] pseudo_critical_edges = [] for w, u, v, original_idx in indexed_edges: # Check for critical edges (by excluding) mst_weight_excluding_current = calculate_mst_weight(block_edge_idx=original_idx) if mst_weight_excluding_current > standard_mst_weight: critical_edges.append(original_idx) for w, u, v, original_idx in indexed_edges: if original_idx in critical_edges: continue # Already identified as critical # Check for pseudo-critical edges (by forcing inclusion) mst_weight_including_current = calculate_mst_weight(force_include_edge=(w, u, v, original_idx)) if mst_weight_including_current == standard_mst_weight: pseudo_critical_edges.append(original_idx) return [critical_edges, pseudo_critical_edges] 15. Number of Ways to Rearrange Sticks With K Sticks Visible (Dynamic Programming) Notes: This is a classic DP problem. Consider $dp[n][k]$ as the number of ways to arrange $n$ sticks such that exactly $k$ sticks are visible. Base Cases: - $dp[n][0] = 0$ for $n > 0$ (cannot have 0 visible if there are sticks) - $dp[0][0] = 1$ (1 way to arrange 0 sticks with 0 visible - empty arrangement) - $dp[n][n] = 1$ (only one way: arrange in increasing order of height) Recurrence: To calculate $dp[n][k]$: 1. Place the tallest stick ($n$). If it's the first stick from the left, it's visible. The remaining $n-1$ sticks must be arranged to have $k-1$ visible sticks: $dp[n-1][k-1]$ ways. 2. Place the tallest stick ($n$) somewhere *after* the first position. In this case, it will hide some other stick. The tallest stick itself is not visible (unless it's the first, covered by case 1). The remaining $n-1$ sticks can be arranged in $dp[n-1][k]$ ways, and the tallest stick can be placed in any of the $n-1$ positions *after* the first visible stick. So, $(n-1) \times dp[n-1][k]$ ways. $dp[n][k] = dp[n-1][k-1] + (n-1) \times dp[n-1][k]$ Remember to take modulo $10^9 + 7$. class Solution: def rearrangeSticks(self, n: int, k: int) -> int: MOD = 10**9 + 7 # dp[i][j] = number of ways to arrange i sticks such that j sticks are visible dp = [[0] * (k + 1) for _ in range(n + 1)] # Base cases dp[0][0] = 1 # 0 sticks, 0 visible, 1 way (empty arrangement) # dp[i][0] = 0 for i > 0 (cannot have 0 visible if there are sticks) # dp[i][i] = 1 (only one way: all sticks in increasing order) for i in range(1, n + 1): for j in range(1, k + 1): if j == i: # All sticks visible dp[i][j] = 1 elif j > i: # Cannot have more visible sticks than total sticks dp[i][j] = 0 else: # Case 1: Place the tallest stick (i) at the first position. # It is visible. We need k-1 visible sticks from the remaining i-1 sticks. term1 = dp[i-1][j-1] # Case 2: Place the tallest stick (i) at any of the other i-1 positions. # It will be hidden by some other stick. # We need k visible sticks from the remaining i-1 sticks. # There are (i-1) choices for where to place the tallest stick among the other i-1 sticks. term2 = (dp[i-1][j] * (i - 1)) % MOD dp[i][j] = (term1 + term2) % MOD return dp[n][k] 16. Count Vowels Permutation (Dynamic Programming) Notes: This is a dynamic programming problem where the state depends on the last character. Let $dp[i][char]$ be the number of valid permutations of length $i$ ending with $char$. The rules define transitions: - 'a' can only be followed by 'e'. - 'e' can only be followed by 'a' or 'i'. - 'i' can only be followed by 'a', 'e', 'o', 'u'. - 'o' can only be followed by 'i' or 'u'. - 'u' can only be followed by 'a'. We can define $dp[i][0]$ for 'a', $dp[i][1]$ for 'e', etc. $dp[i][a] = dp[i-1][e] + dp[i-1][i] + dp[i-1][u]$ $dp[i][e] = dp[i-1][a] + dp[i-1][i]$ $dp[i][i] = dp[i-1][e] + dp[i-1][o]$ $dp[i][o] = dp[i-1][i]$ $dp[i][u] = dp[i-1][i] + dp[i-1][o]$ (corrected, 'u' can be after 'i' or 'o') The rules given in the problem statement are: - Each character is a lowercase vowel ('a', 'e', 'i', 'o', 'u') - 'a' may only be followed by 'e'. - 'e' may only be followed by 'a' or 'i'. - 'i' may not be followed by another 'i'. - 'o' may only be followed by 'i' or 'u'. - 'u' may only be followed by 'a'. Let $dp[k][vowel\_idx]$ be the number of strings of length $k$ ending with $vowel\_idx$. $vowel\_idx: 0='a', 1='e', 2='i', 3='o', 4='u'$ $dp[k][0]$ (ends with 'a') = $dp[k-1][1]$ (prev 'e') + $dp[k-1][2]$ (prev 'i') + $dp[k-1][4]$ (prev 'u') $dp[k][1]$ (ends with 'e') = $dp[k-1][0]$ (prev 'a') + $dp[k-1][2]$ (prev 'i') $dp[k][2]$ (ends with 'i') = $dp[k-1][1]$ (prev 'e') + $dp[k-1][3]$ (prev 'o') $dp[k][3]$ (ends with 'o') = $dp[k-1][2]$ (prev 'i') $dp[k][4]$ (ends with 'u') = $dp[k-1][2]$ (prev 'i') + $dp[k-1][3]$ (prev 'o') Base case: $dp[1][0..4] = 1$ (each vowel can form a string of length 1) class Solution: def countVowelPermutation(self, n: int) -> int: MOD = 10**9 + 7 # dp[i][char_idx] = count of permutations of length i ending with char_idx # char_idx: 0='a', 1='e', 2='i', 3='o', 4='u' # For n=1, each vowel can form a string dp_prev = [1, 1, 1, 1, 1] for _ in range(2, n + 1): dp_curr = [0] * 5 # Ends with 'a'. Can be preceded by 'e', 'i', 'u'. dp_curr[0] = (dp_prev[1] + dp_prev[2] + dp_prev[4]) % MOD # Ends with 'e'. Can be preceded by 'a', 'i'. dp_curr[1] = (dp_prev[0] + dp_prev[2]) % MOD # Ends with 'i'. Can be preceded by 'e', 'o'. (Rule: 'i' may not be followed by another 'i') dp_curr[2] = (dp_prev[1] + dp_prev[3]) % MOD # Ends with 'o'. Can be preceded by 'i'. dp_curr[3] = (dp_prev[2]) % MOD # Ends with 'u'. Can be preceded by 'i', 'o'. dp_curr[4] = (dp_prev[2] + dp_prev[3]) % MOD dp_prev = dp_curr return sum(dp_prev) % MOD 17. Shortest Common Supersequence (Dynamic Programming) Notes: This problem is closely related to the Longest Common Subsequence (LCS) problem. The length of the Shortest Common Supersequence (SCS) is $len(str1) + len(str2) - len(LCS)$. To reconstruct the SCS, we can use the DP table from LCS. When $str1[i-1] == str2[j-1]$, we add this character once to SCS and move diagonally up-left in the DP table. When $str1[i-1] \neq str2[j-1]$, we pick the character from the string that corresponds to the larger LCS value. If $dp[i-1][j] > dp[i][j-1]$, it means $str1[i-1]$ was not part of the LCS found via $dp[i][j-1]$, so we add $str1[i-1]$ to SCS and move up. Otherwise, add $str2[j-1]$ and move left. This reconstruction usually involves starting from $dp[m][n]$ and moving back to $dp[0][0]$. class Solution: def shortestCommonSupersequence(self, str1: str, str2: str) -> str: m, n = len(str1), len(str2) # dp[i][j] stores the length of LCS of str1[0...i-1] and str2[0...j-1] dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if str1[i-1] == str2[j-1]: dp[i][j] = 1 + dp[i-1][j-1] else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # Reconstruct SCS scs = [] i, j = m, n while i > 0 and j > 0: if str1[i-1] == str2[j-1]: scs.append(str1[i-1]) i -= 1 j -= 1 elif dp[i-1][j] > dp[i][j-1]: # str1[i-1] leads to longer LCS path scs.append(str1[i-1]) i -= 1 else: # str2[j-1] leads to longer LCS path scs.append(str2[j-1]) j -= 1 # Add remaining characters from str1 (if any) while i > 0: scs.append(str1[i-1]) i -= 1 # Add remaining characters from str2 (if any) while j > 0: scs.append(str2[j-1]) j -= 1 return "".join(scs[::-1]) # Reverse to get correct order 18. Student Attendance Record II (Dynamic Programming) Notes: This is a complex DP problem with multiple constraints. A valid attendance record of length $n$ must not contain: 1. More than one 'A' (absent). 2. More than two consecutive 'L's (late). Let $dp[i][a][l]$ be the number of valid records of length $i$ with $a$ 'A's used (0 or 1) and $l$ consecutive 'L's at the end (0, 1, or 2). States: - $i$: current length of record - $a$: count of 'A's (0 or 1) - $l$: count of consecutive 'L's at the end (0, 1, or 2) Transitions: For $dp[i][a][l]$: 1. Appending 'P': From $dp[i-1][a][0]$ (ending with P), $dp[i-1][a][1]$ (ending with L), $dp[i-1][a][2]$ (ending with LL). Result: $dp[i][a][0] += dp[i-1][a][0] + dp[i-1][a][1] + dp[i-1][a][2]$ 2. Appending 'L': From $dp[i-1][a][0]$ (ending with P) $\rightarrow dp[i][a][1]$ From $dp[i-1][a][1]$ (ending with L) $\rightarrow dp[i][a][2]$ Result: $dp[i][a][1] += dp[i-1][a][0]$ $dp[i][a][2] += dp[i-1][a][1]$ 3. Appending 'A': Only if $a=0$ (no 'A's yet). From $dp[i-1][0][0]$, $dp[i-1][0][1]$, $dp[i-1][0][2]$. Result: $dp[i][1][0] += dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2]$ Base case: $dp[0][0][0] = 1$ (empty string) The final answer is the sum of all $dp[n][a][l]$ states. This can be optimized by only keeping track of the previous length's states. Let $P_n, L_n, A_n$ be counts of valid records of length $n$ ending in P, L, A respectively. Further refine to $P_n(a,l), L_n(a,l), A_n(a,l)$. A common approach is to use a 6-state DP for previous length: $dp[i][0]$: # of valid seqs of length $i$ with 0 'A's ending with P $dp[i][1]$: # of valid seqs of length $i$ with 0 'A's ending with L $dp[i][2]$: # of valid seqs of length $i$ with 0 'A's ending with LL $dp[i][3]$: # of valid seqs of length $i$ with 1 'A' ending with P $dp[i][4]$: # of valid seqs of length $i$ with 1 'A' ending with L $dp[i][5]$: # of valid seqs of length $i$ with 1 'A' ending with LL Then sum up all $dp[n][0..5]$. class Solution: def checkRecord(self, n: int) -> int: MOD = 10**9 + 7 # dp[i][j][k]: number of valid attendance records of length i # j: count of 'A's (0 or 1) # k: count of consecutive 'L's at the end (0, 1, or 2) # dp[j][k] for current length, and dp_prev[j][k] for previous length # Base case: length 0. One way (empty string), with 0 A's and 0 consecutive L's. # dp_prev[a_count][consecutive_l_count] dp_prev = [[0] * 3 for _ in range(2)] # dp_prev[a][l_consecutive] dp_prev[0][0] = 1 # 0 A's, 0 L's, 1 way (empty string) for i in range(1, n + 1): dp_curr = [[0] * 3 for _ in range(2)] # Case 1: Append 'P' # Can come from any (a, l) state of previous length for a in range(2): for l in range(3): dp_curr[a][0] = (dp_curr[a][0] + dp_prev[a][l]) % MOD # Case 2: Append 'L' # If previous state ended with L, it becomes LL (l=2) # If previous state ended with P, it becomes L (l=1) for a in range(2): # From (a, 0) -> (a, 1) dp_curr[a][1] = (dp_curr[a][1] + dp_prev[a][0]) % MOD # From (a, 1) -> (a, 2) dp_curr[a][2] = (dp_curr[a][2] + dp_prev[a][1]) % MOD # Case 3: Append 'A' # Only if a_count was 0. New a_count becomes 1. Consecutive L's reset to 0. # Can come from any (0, l) state of previous length for l in range(3): dp_curr[1][0] = (dp_curr[1][0] + dp_prev[0][l]) % MOD dp_prev = dp_curr total_ways = 0 for a in range(2): for l in range(3): total_ways = (total_ways + dp_prev[a][l]) % MOD return total_ways 19. Maximum Sum of 3 Non-Overlapping Subarrays (Dynamic Programming) Notes: This problem asks for three non-overlapping subarrays of a fixed size $k$ with maximum sum. First, compute prefix sums or a sliding window sum array to quickly get the sum of any subarray of length $k$. Let $W[i]$ be the sum of the subarray $nums[i \dots i+k-1]$. Then, we need to pick three starting indices $i, j, p$ such that $W[i] + W[j] + W[p]$ is maximized, and $i+k \le j$, $j+k \le p$. This can be solved with DP. - $left[i]$: stores the starting index of the maximum sum subarray of length $k$ in $W[0 \dots i]$. - $right[i]$: stores the starting index of the maximum sum subarray of length $k$ in $W[i \dots \text{end}]$. Iterate for the middle subarray's starting index $j$ from $k$ to $n-2k$. The first subarray's best starting index will be $left[j-1]$. The third subarray's best starting index will be $right[j+k]$. Calculate the sum using these three indices and find the maximum. class Solution: def maxSumOfThreeSubarrays(self, nums: list[int], k: int) -> list[int]: n = len(nums) # Calculate window sums W[i] = sum(nums[i...i+k-1]) window_sums = [0] * (n - k + 1) current_sum = sum(nums[0:k]) window_sums[0] = current_sum for i in range(1, n - k + 1): current_sum = current_sum - nums[i-1] + nums[i+k-1] window_sums[i] = current_sum # left[i]: stores the starting index of the max sum window in window_sums[0...i] left = [0] * len(window_sums) best_left_idx = 0 for i in range(len(window_sums)): if window_sums[i] > window_sums[best_left_idx]: best_left_idx = i left[i] = best_left_idx # right[i]: stores the starting index of the max sum window in window_sums[i...end] right = [0] * len(window_sums) best_right_idx = len(window_sums) - 1 for i in range(len(window_sums) - 1, -1, -1): # Use >= for tie-breaking: prefer smaller index for left, larger for right if window_sums[i] >= window_sums[best_right_idx]: best_right_idx = i right[i] = best_right_idx max_total_sum = -1 result = [] # Iterate for the middle subarray's starting index `j` # `j` can range from k (inclusive) to `len(window_sums) - k` (exclusive) # This ensures there's enough space for left and right subarrays. for j in range(k, len(window_sums) - k): idx1 = left[j - k] # best start for first subarray, ending before j idx3 = right[j + k] # best start for third subarray, starting after j+k-1 current_total_sum = window_sums[idx1] + window_sums[j] + window_sums[idx3] if current_total_sum > max_total_sum: max_total_sum = current_total_sum result = [idx1, j, idx3] return result 20. Number of Ways to Divide a Long Corridor (Dynamic Programming / Combinatorics) Notes: The problem requires dividing a corridor into segments, where each segment must contain exactly two 'S' (seats). This is a combinatorial problem. Identify the positions of all 'S's. If the total number of 'S's is odd or zero, it's impossible to divide into segments of two 'S's, so return 0. Otherwise, group the 'S's into pairs: $(S_1, S_2), (S_3, S_4), \dots, (S_{2k-1}, S_{2k})$. A division point can be placed anywhere between $S_{2i}$ and $S_{2i+1}$. The number of plants between $S_{2i}$ and $S_{2i+1}$ determines the number of ways to place a divider. If there are $P$ plants between $S_{2i}$ and $S_{2i+1}$, there are $P+1$ ways to place a divider. The total number of ways is the product of $(P_i+1)$ for all $i$. Example: `P S P P S P S P S P` Seats at indices: `1, 4, 6, 8` Pairs: $(S_1, S_2)$ are at `1, 4`. $(S_3, S_4)$ are at `6, 8`. The division must be between $S_2$ (idx 4) and $S_3$ (idx 6). Plants between them: `P` at index `5`. Count of plants: $pos(S_3) - pos(S_2) - 1 = 6 - 4 - 1 = 1$. Number of ways to divide: $1 + 1 = 2$. Total ways = 2. class Solution: def numberOfWays(self, corridor: str) -> int: MOD = 10**9 + 7 seat_indices = [] for i, char in enumerate(corridor): if char == 'S': seat_indices.append(i) num_seats = len(seat_indices) # If no seats or odd number of seats, it's impossible if num_seats == 0 or num_seats % 2 != 0: return 0 # If exactly two seats, there's only one way (the whole corridor is the segment) if num_seats == 2: return 1 # Group seats into pairs: (S_0, S_1), (S_2, S_3), ..., (S_{num_seats-2}, S_{num_seats-1}) # The divisions must occur between the end of one pair and the start of the next. # i.e., between S_1 and S_2, S_3 and S_4, etc. total_ways = 1 # Iterate through the gaps between pairs of seats # The first pair is (seat_indices[0], seat_indices[1]) # The second pair is (seat_indices[2], seat_indices[3]) # The gap is between seat_indices[1] and seat_indices[2] # We need to consider gaps from (S_1, S_2), (S_3, S_4), ..., (S_{N-3}, S_{N-2}) # These are `seat_indices[2i+1]` and `seat_indices[2i+2]` for i in range(1, num_seats - 1, 2): # Current pair ends at seat_indices[i] # Next pair starts at seat_indices[i+1] # Number of plants between these two seats plants_between = seat_indices[i+1] - seat_indices[i] - 1 # Number of ways to place a divider in this gap (plants_between + 1) total_ways = (total_ways * (plants_between + 1)) % MOD return total_ways