AlgoH1

Cheatsheet Content

1. Guess the Word Concept: Interactive problem, MiniMax strategy, filtering. Notes: The key is to pick a word that minimizes the maximum possible size of the remaining word list for any guess result. A simple heuristic is to pick a word that has the most 0-matches with other words. Python Snippet (Core Logic): import random # master.guess is a predefined function def findSecretWord(wordlist, master): for i in range(10): # Max 10 guesses # Pick a random word or apply MiniMax strategy guess = random.choice(wordlist) matches = master.guess(guess) if matches == 6: return new_wordlist = [] for word in wordlist: if sum(c1 == c2 for c1, c2 in zip(guess, word)) == matches: new_wordlist.append(word) wordlist = new_wordlist 2. First Missing Positive Concept: In-place modification, hashing using array indices. Notes: The problem asks for the smallest positive integer. We can use the array itself to mark the presence of positive integers. If $nums[i]$ contains $x$, we try to place $x$ at index $x-1$. Python Snippet: def firstMissingPositive(nums): n = len(nums) for i in range(n): # Place nums[i] at its correct position (nums[nums[i]-1]) if it's within [1, n] while 1 3. Trapping Rain Water Concept: Two pointers, dynamic programming (precomputing max heights). Notes: For each bar, the amount of water it can trap depends on the maximum height of bars to its left and right. $water_i = \min(max\_left_i, max\_right_i) - height_i$. A two-pointer approach can do this in $O(N)$ time and $O(1)$ space. Python Snippet (Two Pointers): def trap(height): if not height: return 0 left, right = 0, len(height) - 1 max_left, max_right = 0, 0 trapped_water = 0 while left = max_left: max_left = height[left] else: trapped_water += max_left - height[left] left += 1 else: if height[right] >= max_right: max_right = height[right] else: trapped_water += max_right - height[right] right -= 1 return trapped_water 4. Substring with Concatenation of All Words Concept: Sliding window, hash maps. Notes: The window size is fixed (sum of lengths of all words). Iterate through the string, checking if each window contains the exact permutation of words. Start iterating from different offsets ($0$ to $len(word)-1$) to cover all possible starting positions. Python Snippet (Core Logic): from collections import Counter def findSubstring(s, words): if not s or not words: return [] word_len = len(words[0]) num_words = len(words) total_len = word_len * num_words word_counts = Counter(words) result = [] for i in range(word_len): # Iterate through all possible starting offsets left = i words_found = Counter() count = 0 for j in range(i, len(s) - word_len + 1, word_len): word = s[j:j + word_len] if word in word_counts: words_found[word] += 1 count += 1 while words_found[word] > word_counts[word]: words_found[s[left:left + word_len]] -= 1 left += word_len count -= 1 if count == num_words: result.append(left) words_found[s[left:left + word_len]] -= 1 left += word_len count -= 1 else: # Word not in list, reset window words_found.clear() count = 0 left = j + word_len return result 5. Minimum Window Substring Concept: Sliding window, hash maps. Notes: Expand the window to the right until all characters from $T$ are present. Then, shrink the window from the left while maintaining the condition, updating the minimum window found. Python Snippet: from collections import Counter def minWindow(s, t): if not t or not s: return "" dict_t = Counter(t) window_start, matched = 0, 0 min_len = float('inf') substr_start_idx = 0 for window_end in range(len(s)): char_right = s[window_end] if char_right in dict_t: dict_t[char_right] -= 1 if dict_t[char_right] >= 0: # Character needed matched += 1 while matched == len(t): current_len = window_end - window_start + 1 if current_len 6. Reverse Nodes in k-Group Concept: Linked list manipulation, recursion or iteration. Notes: The core idea is to reverse a sub-list of $k$ nodes. You need to handle connecting the reversed sub-list with the previous and next parts of the original list. Can be done iteratively or recursively. Python Snippet (Iterative): # Definition for singly-linked list. class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverseKGroup(head, k): dummy = ListNode(0, head) prev_group_tail = dummy while True: kth_node = prev_group_tail for _ in range(k): kth_node = kth_node.next if not kth_node: return dummy.next # Not enough nodes to reverse group_head = prev_group_tail.next next_group_head = kth_node.next # Reverse the k nodes prev, curr = kth_node.next, group_head for _ in range(k): temp = curr.next curr.next = prev prev = curr curr = temp # Connect to previous and next groups prev_group_tail.next = prev # prev is now the new head of the reversed group group_head.next = next_group_head # group_head is now the new tail prev_group_tail = group_head # update prev_group_tail for next iteration 7. Longest Valid Parentheses Concept: Stack, dynamic programming. Notes: Stack: Push index of '(' onto stack. If ')' encountered, pop. If stack empty, push ')' index. Max length is $current\_idx - stack.top()$. DP: $dp[i]$ is the length of the longest valid parentheses ending at $i$. If $s[i] == ')'$ and $s[i-1] == '(', dp[i] = dp[i-2] + 2$. If $s[i] == ')'$ and $s[i-1] == ')', dp[i] = dp[i - dp[i-1] - 1] + dp[i-1] + 2$ if a match is found. Python Snippet (Stack): def longestValidParentheses(s): max_len = 0 stack = [-1] # Stores indices, -1 for base of valid sequence for i, char in enumerate(s): if char == '(': stack.append(i) else: # char == ')' stack.pop() if not stack: # No matching '(', push current index as new base stack.append(i) else: # Matching '(', calculate current valid length max_len = max(max_len, i - stack[-1]) return max_len 8. Number of Visible People in a Queue Concept: Monotonic stack. Notes: Iterate from right to left. Maintain a decreasing stack. For each person, pop elements from the stack that are shorter or equal. The number of popped elements is the number of people this person can see to their right. If the stack is not empty after popping, the person at the top of the stack is also visible. Python Snippet: def canSeePersonsCount(heights): n = len(heights) ans = [0] * n stack = [] # Monotonically decreasing stack (stores heights) for i in range(n - 1, -1, -1): current_person_visible_count = 0 while stack and stack[-1] 9. Largest Rectangle in Histogram Concept: Monotonic stack. Notes: For each bar, we need to find the first smaller bar to its left and to its right. A monotonic increasing stack can efficiently find this. When a bar is popped, it means we found a bar smaller than it to its right. The bar below it in the stack is the first smaller bar to its left. Python Snippet: def largestRectangleArea(heights): stack = [] # Stores (index, height) max_area = 0 heights.append(0) # Sentinel value to pop all elements from stack for i, h in enumerate(heights): start_idx = i while stack and stack[-1][1] > h: idx, height = stack.pop() max_area = max(max_area, height * (i - idx)) start_idx = idx # This bar can extend at least until 'idx' stack.append((start_idx, h)) return max_area 10. Sliding Window Maximum Concept: Deque (double-ended queue). Notes: Maintain a deque that stores indices of elements in the current window in decreasing order of their values. When a new element comes, remove smaller elements from the back of the deque. Remove elements from the front if they are out of the window. The front of the deque always holds the index of the maximum element. Python Snippet: from collections import deque def maxSlidingWindow(nums, k): if not nums or k == 0: return [] dq = deque() # Stores indices result = [] for i in range(len(nums)): # Remove indices of elements outside the current window if dq and dq[0] == i - k: dq.popleft() # Remove elements smaller than current from the back while dq and nums[dq[-1]] = k - 1: result.append(nums[dq[0]]) return result 11. Max Value of Equation Concept: Deque, $y_j + y_i + |x_j - x_i|$ can be rewritten as $(y_j - x_j) + (y_i + x_i)$ for $x_j > x_i$. Notes: We want to maximize $(y_j - x_j) + (y_i + x_i)$. For a fixed $j$, $y_j + x_j$ is constant. We need to find the maximum $y_i - x_i$ for $i Python Snippet: from collections import deque def findMaxValueOfEquation(points, k): dq = deque() # Stores (y - x, x) max_val = float('-inf') for x_j, y_j in points: # Remove points that are too far to the left (x_j - x_i > k) while dq and x_j - dq[0][1] > k: dq.popleft() if dq: # Current point (x_j, y_j) + best (y_i - x_i) from deque max_val = max(max_val, y_j + x_j + dq[0][0]) # Add current point's (y - x, x) to deque, maintaining decreasing order of y-x while dq and dq[-1][0] 12. Reverse Pairs Concept: Merge Sort modification, Fenwick Tree/Segment Tree. Notes: This is a classic "count inversions" problem with an added condition. A common approach is to modify merge sort. When merging two sorted halves, for each element $nums[i]$ in the left half, count how many elements $nums[j]$ in the right half satisfy $nums[i] > 2 * nums[j]$. This counting can be done efficiently because both halves are sorted. Python Snippet (Merge Sort based): def reversePairs(nums): self.count = 0 def merge_sort(arr): if len(arr) 2 * right[j]: j += 1 self.count += j # All elements from right[:j] satisfy the condition # Standard merge step merged = [] i, j = 0, 0 while i 13. Find in Mountain Array Concept: Binary search. Notes: First, find the peak element's index using binary search. Then, perform two separate binary searches: one on the increasing left side of the peak and one on the decreasing right side of the peak. Python Snippet (Conceptual): # mountain_arr is an object with get(index) and length() methods class MountainArray: def get(self, index: int) -> int: pass def length(self) -> int: pass def findInMountainArray(target: int, mountain_arr: 'MountainArray') -> int: n = mountain_arr.length() # 1. Find peak index low, high = 1, n - 2 peak_idx = -1 while low right_val: peak_idx = mid break elif left_val target: low = mid + 1 # Decreasing, so if target is smaller, go right else: high = mid - 1 # Decreasing, so if target is larger, go left return -1 14. Median of Two Sorted Arrays Concept: Binary search, divide and conquer. Notes: The core idea is to find a split point in both arrays such that the elements to the left of the split are smaller than elements to the right, and the total count of elements to the left equals $(m+n+1)//2$. This allows finding the $k$-th smallest element efficiently. Python Snippet (Conceptual, finding k-th element): def findMedianSortedArrays(nums1, nums2): m, n = len(nums1), len(nums2) # Ensure nums1 is the shorter array if m > n: nums1, nums2, m, n = nums2, nums1, n, m # Binary search on partition point of nums1 low, high = 0, m while low min_right_y: # partition_x is too far right high = partition_x - 1 else: # max_left_y > min_right_x, partition_x is too far left low = partition_x + 1 15. N-Queens Concept: Backtracking. Notes: Place queens one by one, row by row. For each cell, check if placing a queen there is valid (no other queen in the same column, left diagonal, or right diagonal). If valid, recurse. If not, backtrack. Use sets to store occupied columns/diagonals for $O(1)$ lookup. Python Snippet: def solveNQueens(n): cols = set() pos_diag = set() # r + c neg_diag = set() # r - c board = [["."] * n for _ in range(n)] res = [] def backtrack(r): if r == n: res.append(["".join(row) for row in board]) return for c in range(n): if c in cols or (r + c) in pos_diag or (r - c) in neg_diag: continue cols.add(c) pos_diag.add(r + c) neg_diag.add(r - c) board[r][c] = "Q" backtrack(r + 1) cols.remove(c) pos_diag.remove(r + c) neg_diag.remove(r - c) board[r][c] = "." backtrack(0) return res 16. Serialize and Deserialize Binary Tree Concept: Tree traversal (pre-order, post-order, level-order) and string manipulation. Notes: Pre-order traversal is commonly used. Store 'None' or a special marker for null nodes to reconstruct the tree structure correctly. The serialized string should contain values and markers. Python Snippet (Pre-order DFS): # Definition for a binary tree node. class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = None class Codec: def serialize(self, root): res = [] def dfs(node): if not node: res.append("N") # N for Null return res.append(str(node.val)) dfs(node.left) dfs(node.right) dfs(root) return ",".join(res) def deserialize(self, data): vals = data.split(",") self.i = 0 # Use self.i for shared index in recursive calls def dfs(): if vals[self.i] == "N": self.i += 1 return None node = TreeNode(int(vals[self.i])) self.i += 1 node.left = dfs() node.right = dfs() return node return dfs() 17. Binary Tree Maximum Path Sum Concept: Tree recursion (DFS). Notes: A path can either go through the root and split into left/right, or it can go up from a child node. For each node, calculate two values: 1) the maximum path sum that *starts* at this node and goes down (used by parent), and 2) the maximum path sum that *passes through* this node (potentially the global maximum). Python Snippet: # Definition for a binary tree node. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def maxPathSum(root): self.max_sum = float('-inf') def dfs(node): if not node: return 0 # Max path sum from left/right child, taking only positive contributions left_sum = max(0, dfs(node.left)) right_sum = max(0, dfs(node.right)) # Max path sum through the current node (potentially updates global max) # This path uses node.val + left_sum + right_sum self.max_sum = max(self.max_sum, node.val + left_sum + right_sum) # Return max path sum STARTING at current node (for its parent) # This path can only go left or right, not both return node.val + max(left_sum, right_sum) dfs(root) return self.max_sum 18. Word Search II Concept: Trie (Prefix Tree), Backtracking (DFS). Notes: Build a Trie from the given words. Then, for each cell in the board, start a DFS. If the current path forms a prefix present in the Trie, continue. If it forms a complete word, add it to results. Mark visited cells to avoid cycles. Remove words from Trie once found to avoid duplicates and redundant searches. Python Snippet (Conceptual): class TrieNode: def __init__(self): self.children = {} self.is_word = False self.word = None def build_trie(words): root = TrieNode() for word in words: node = root for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] node.is_word = True node.word = word return root def findWords(board, words): root = build_trie(words) ROWS, COLS = len(board), len(board[0]) result = set() def dfs(r, c, node): if r = ROWS or c = COLS or board[r][c] == '#': return char = board[r][c] if char not in node.children: return node = node.children[char] if node.is_word: result.add(node.word) # Optimization: remove word from Trie to avoid duplicates/re-finding # This requires careful Trie node cleanup, or just mark as found. # For simplicity here, we just add to set. # A more robust solution might delete the word from the Trie. temp = board[r][c] board[r][c] = '#' # Mark as visited dfs(r + 1, c, node) dfs(r - 1, c, node) dfs(r, c + 1, node) dfs(r, c - 1, node) board[r][c] = temp # Backtrack for r in range(ROWS): for c in range(COLS): dfs(r, c, root) return list(result) 19. Find Median from Data Stream Concept: Two heaps (min-heap and max-heap). Notes: Maintain two heaps: a max-heap for the smaller half of numbers and a min-heap for the larger half. Ensure that the size difference between the two heaps is at most 1. The median will either be the root of the larger heap (if total count is odd) or the average of the two roots (if total count is even). Python Snippet: import heapq class MedianFinder: def __init__(self): self.max_heap = [] # Stores smaller half, max-heap self.min_heap = [] # Stores larger half, min-heap def addNum(self, num: int) -> None: if not self.max_heap or num len(self.min_heap) + 1: heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap)) elif len(self.min_heap) > len(self.max_heap): heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap)) def findMedian(self) -> float: if len(self.max_heap) == len(self.min_heap): return (-self.max_heap[0] + self.min_heap[0]) / 2.0 else: return float(-self.max_heap[0]) 20. IPO Concept: Greedy approach, two heaps. Notes: At each step, choose the project that yields the maximum profit among all projects that can be started with current capital. Use a min-heap for projects by capital (to quickly find available projects) and a max-heap for profits of available projects (to pick the most profitable). Python Snippet: import heapq def findMaximizedCapital(k, w, profits, capital): n = len(profits) projects = [] for i in range(n): projects.append((capital[i], profits[i])) projects.sort() # Sort by capital requirement max_profit_heap = [] # Max-heap for profits of available projects project_idx = 0 for _ in range(k): # Add all projects that can be started with current capital 'w' while project_idx 21. Sliding Window Median Concept: Two heaps, balanced BST (or `SortedList` in Python). Notes: Similar to "Find Median from Data Stream", but with a sliding window. When an element slides out, it must be removed from the heaps. Removing arbitrary elements from standard heaps is $O(N)$. Use a lazy deletion approach (mark elements for deletion) or a `SortedList` (from `sortedcontainers` library) which supports $O(\log N)$ deletion. Python Snippet (Two Heaps with Lazy Deletion): import heapq from collections import defaultdict class MedianFinderWindow: def __init__(self): self.min_heap = [] # Stores larger half self.max_heap = [] # Stores smaller half (negated) self.deleted = defaultdict(int) # Counts deleted elements def _balance(self): while self.max_heap and self.deleted[-self.max_heap[0]] > 0: self.deleted[-self.max_heap[0]] -= 1 heapq.heappop(self.max_heap) while self.min_heap and self.deleted[self.min_heap[0]] > 0: self.deleted[self.min_heap[0]] -= 1 heapq.heappop(self.min_heap) if len(self.max_heap) > len(self.min_heap) + 1: heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap)) elif len(self.min_heap) > len(self.max_heap): heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap)) self._balance() # Re-balance after moving elements def add(self, num): if not self.max_heap or num 0: self.deleted[num] -= 1 heapq.heappop(self.max_heap) elif num == self.min_heap[0] and self.deleted[num] > 0: self.deleted[num] -= 1 heapq.heappop(self.min_heap) self._balance() def get_median(self): if not self.max_heap and not self.min_heap: return None if len(self.max_heap) == len(self.min_heap): return (-self.max_heap[0] + self.min_heap[0]) / 2.0 else: return float(-self.max_heap[0]) def slidingWindowMedian(nums, k): mf = MedianFinderWindow() result = [] for i in range(len(nums)): mf.add(nums[i]) if i >= k: # Window slides, remove oldest element mf.remove(nums[i-k]) if i >= k - 1: # Window is full result.append(mf.get_median()) return result 22. Merge k Sorted Lists Concept: Min-heap (priority queue), divide and conquer. Notes: Min-heap: Add the head of each list to a min-heap. Repeatedly extract the smallest element from the heap, add it to the merged list, and if the extracted node has a `next`, add `next` to the heap. Divide and Conquer: Merge two lists at a time. Recursively merge halves of the list of lists. Python Snippet (Min-Heap): import heapq # Definition for singly-linked list. class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def mergeKLists(lists): min_heap = [] # Stores (value, list_index, node_object) # Push the head of each list into the heap for i, l in enumerate(lists): if l: heapq.heappush(min_heap, (l.val, i, l)) dummy = ListNode(0) current = dummy while min_heap: val, list_idx, node = heapq.heappop(min_heap) current.next = node current = current.next if node.next: heapq.heappush(min_heap, (node.next.val, list_idx, node.next)) return dummy.next 23. Smallest Range Covering Elements from K Lists Concept: Min-heap, sliding window. Notes: Use a min-heap to keep track of the smallest element from each of the $k$ lists. The range is defined by the minimum element (from the heap) and the maximum element (tracked separately). When an element is extracted from the heap, replace it with the next element from the same list. Python Snippet: import heapq def smallestRange(nums): min_heap = [] # (value, list_idx, element_idx_in_list) max_val = float('-inf') # Initialize heap with first elements of all lists for i, lst in enumerate(nums): if lst: heapq.heappush(min_heap, (lst[0], i, 0)) max_val = max(max_val, lst[0]) min_range = float('inf') start, end = 0, 0 while len(min_heap) == len(nums): # Ensure we have at least one element from each list min_val, list_idx, elem_idx = heapq.heappop(min_heap) if max_val - min_val 24. Maximum Frequency Stack Concept: Hash map of stacks, hash map for frequencies. Notes: Use `freq` map to store count of each number. Use `freq_stack` map where keys are frequencies and values are stacks of numbers that currently have that frequency. Keep track of `max_freq` to know which stack to pop from. Python Snippet: from collections import defaultdict class FreqStack: def __init__(self): self.freq = defaultdict(int) # num -> frequency self.freq_stack = defaultdict(list) # frequency -> stack of numbers self.max_freq = 0 def push(self, val: int) -> None: self.freq[val] += 1 current_freq = self.freq[val] self.max_freq = max(self.max_freq, current_freq) self.freq_stack[current_freq].append(val) def pop(self) -> int: val = self.freq_stack[self.max_freq].pop() self.freq[val] -= 1 if not self.freq_stack[self.max_freq]: # If stack at max_freq becomes empty self.max_freq -= 1 return val 25. Minimum Cost to Hire K Workers Concept: Greedy, sorting, min-heap/max-heap. Notes: The key insight is that for any chosen worker $j$, if $wage_j/quality_j$ is the maximum ratio among the selected $k$ workers, then all $k$ workers must be paid at least $quality_i * (wage_j/quality_j)$. Sort workers by their $wage/quality$ ratio. Iterate through sorted workers, maintaining a max-heap of the $k-1$ smallest $quality$ values seen so far. Python Snippet: import heapq def mincostToHireWorkers(quality, wage, k): workers = [] for i in range(len(quality)): workers.append((wage[i] / quality[i], quality[i])) workers.sort() # Sort by wage/quality ratio min_cost = float('inf') current_quality_sum = 0 max_heap = [] # Max-heap to store qualities of selected workers for ratio, q in workers: current_quality_sum += q heapq.heappush(max_heap, -q) # Push negative quality for max-heap if len(max_heap) > k: current_quality_sum += heapq.heappop(max_heap) # Remove largest quality if len(max_heap) == k: min_cost = min(min_cost, ratio * current_quality_sum) return min_cost 26. Candy Concept: Two passes (left-to-right, right-to-left), greedy. Notes: The problem has two conditions: children with higher ratings get more candy than left neighbor, and higher ratings get more candy than right neighbor. Solve these independently. First pass: iterate left to right, ensuring $candy_i > candy_{i-1}$ if $rating_i > rating_{i-1}$. Second pass: iterate right to left, ensuring $candy_i > candy_{i+1}$ if $rating_i > rating_{i+1}$, taking $\max$ with existing candy count. Python Snippet: def candy(ratings): n = len(ratings) candies = [1] * n # Everyone gets at least one candy # Left to right pass for i in range(1, n): if ratings[i] > ratings[i-1]: candies[i] = candies[i-1] + 1 # Right to left pass for i in range(n - 2, -1, -1): if ratings[i] > ratings[i+1]: candies[i] = max(candies[i], candies[i+1] + 1) # Take max return sum(candies) 27. Minimum Number of Refueling Stops Concept: Dynamic programming, max-heap (greedy). Notes: DP: $dp[i]$ is the maximum distance reachable with $i$ refueling stops. Greedy with Max-Heap: Iterate through stations. If current fuel is enough to reach next station, continue. If not, pick the largest fuel available from all stations passed so far (using max-heap) and add it. Repeat until enough fuel or no more options. Python Snippet (Greedy with Max-Heap): import heapq def minRefuelStops(target, startFuel, stations): max_heap = [] # Max-heap to store available fuel num_stops = 0 current_fuel = startFuel station_idx = 0 while current_fuel 28. Making A Large Island Concept: DFS/BFS, Union-Find. Notes: DFS/BFS: First, find all existing islands and assign them a unique ID, storing their sizes. Then, iterate through all '0' cells. For each '0', consider changing it to '1'. Calculate the size of the potential new island by summing the sizes of all unique adjacent islands (using a set to avoid double counting if an island is adjacent twice). Add 1 for the '0' itself. Python Snippet (DFS): def largestIsland(grid): R, C = len(grid), len(grid[0]) # 1. DFS to find existing islands and store their sizes island_id = 2 # Start IDs from 2 to avoid collision with 0 and 1 island_sizes = {0: 0} # island_sizes[id] = size def dfs(r, c, current_id): if r = R or c = C or grid[r][c] != 1: return 0 grid[r][c] = current_id size = 1 size += dfs(r + 1, c, current_id) size += dfs(r - 1, c, current_id) size += dfs(r, c + 1, current_id) size += dfs(r, c - 1, current_id) return size for r in range(R): for c in range(C): if grid[r][c] == 1: size = dfs(r, c, island_id) island_sizes[island_id] = size island_id += 1 max_island_size = max(island_sizes.values()) if island_sizes else 0 # 2. Iterate through '0's and try flipping for r in range(R): for c in range(C): if grid[r][c] == 0: current_potential_size = 1 # The '0' itself adjacent_islands = set() for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]: nr, nc = r + dr, c + dc if 0 29. Shortest Path in a Grid with Obstacles Elimination Concept: BFS, state tracking. Notes: Use BFS. The state in BFS should be $(row, col, remaining\_obstacles\_elimination\_count)$. Keep track of visited states to avoid cycles and redundant computations. A state $(r, c, k)$ means we are at $(r, c)$ with $k$ eliminations left. Python Snippet: from collections import deque def shortestPath(grid, k): R, C = len(grid), len(grid[0]) if k >= R + C - 2: # If k is large enough, can always reach target without problems return R + C - 2 q = deque([(0, 0, k, 0)]) # (r, c, remaining_k, steps) visited = set([(0, 0, k)]) # (r, c, remaining_k) while q: r, c, remaining_k, steps = q.popleft() if r == R - 1 and c == C - 1: return steps for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]: nr, nc = r + dr, c + dc if 0 = 0 and (nr, nc, new_k) not in visited: visited.add((nr, nc, new_k)) q.append((nr, nc, new_k, steps + 1)) return -1 30. Bus Routes Concept: BFS, graph. Notes: Build a graph where nodes are bus stops and edges represent bus routes. Or, more effectively, nodes can be bus *routes*. An edge exists between two routes if they share a common stop. The goal is to find the shortest path (in terms of routes) from a route that contains `source` to a route that contains `target`. BFS finds the shortest path. Python Snippet: from collections import deque, defaultdict def numBusesToDestination(routes, source, target): if source == target: return 0 # Map stop to list of bus routes that pass through it stop_to_routes = defaultdict(set) for i, route in enumerate(routes): for stop in route: stop_to_routes[stop].add(i) q = deque() # (current_stop, buses_taken) visited_stops = {source} visited_routes = set() # Initialize BFS with all routes that pass through the source stop for route_idx in stop_to_routes[source]: q.append((route_idx, 1)) # (route_index, num_buses_taken) visited_routes.add(route_idx) while q: route_idx, buses_taken = q.popleft() for stop in routes[route_idx]: if stop == target: return buses_taken # Explore other routes accessible from this stop for next_route_idx in stop_to_routes[stop]: if next_route_idx not in visited_routes: visited_routes.add(next_route_idx) q.append((next_route_idx, buses_taken + 1)) return -1