AlgoM3

Cheatsheet Content

1. Lowest Common Ancestor of a Binary Tree Notes: Recursively search for $p$ or $q$. If both are found, the current node is LCA. If only one is found, that one is propagated up. If none, return None . class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if not root or root == p or root == q: return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if left and right: return root return left if left else right 2. Find Duplicate Subtrees Notes: Use post-order traversal to serialize subtrees. Store serializations in a map and count frequencies. If frequency is 2, add the root to result. class Solution: def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]: counts = collections.defaultdict(int) res = [] def traverse(node): if not node: return "#" left = traverse(node.left) right = traverse(node.right) s = f"{node.val},{left},{right}" counts[s] += 1 if counts[s] == 2: res.append(node) return s traverse(root) return res 3. Flatten Binary Tree to Linked List Notes: Use a reverse post-order traversal. Keep track of the previously visited node (which will be the 'next' node in the flattened list). Set node.right = prev and node.left = None . class Solution: prev = None def flatten(self, root: Optional[TreeNode]) -> None: if not root: return self.flatten(root.right) self.flatten(root.left) root.right = self.prev root.left = None self.prev = root 4. Distribute Coins in Binary Tree Notes: Post-order traversal. For each node, calculate the balance of coins ($node.val - 1$). This balance represents coins to give to parent (positive) or coins needed from parent (negative). Sum up absolute values of balances for total moves. class Solution: def distributeCoins(self, root: Optional[TreeNode]) -> int: self.moves = 0 def dfs(node): if not node: return 0 left_balance = dfs(node.left) right_balance = dfs(node.right) self.moves += abs(left_balance) + abs(right_balance) return node.val + left_balance + right_balance - 1 dfs(root) return self.moves 5. Trim a Binary Search Tree Notes: Recursively trim. If $node.val high$, the node and its right subtree are too large, so return $node.left$ trimmed. Otherwise, trim both children and return the node. class Solution: def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]: if not root: return None if root.val high: return self.trimBST(root.left, low, high) root.left = self.trimBST(root.left, low, high) root.right = self.trimBST(root.right, low, high) return root 6. My Calendar I Notes: Maintain a sorted list of intervals. For each new interval $[start, end)$, check if it overlaps with any existing interval $[s, e)$. Overlap occurs if $s class MyCalendar: def __init__(self): self.calendar = [] def book(self, start: int, end: int) -> bool: for s, e in self.calendar: if s 7. My Calendar II Notes: Use two lists: one for single bookings and one for double bookings. A new event creates a double booking if it overlaps with a single booking. It creates a triple booking (invalid) if it overlaps with a double booking. class MyCalendarTwo: def __init__(self): self.calendar = [] # single bookings self.overlaps = [] # double bookings def book(self, start: int, end: int) -> bool: for s, e in self.overlaps: if s 8. Stock Price Fluctuation Notes: Use a dictionary to store price at each timestamp. Use two heaps (min-heap for min price, max-heap for max price) to efficiently get min/max. Store (price, timestamp) in heaps and use lazy deletion: when retrieving from heap, check if timestamp's current price matches heap's price; if not, pop and retry. import heapq class StockPrice: def __init__(self): self.prices = {} self.max_time = 0 self.min_heap = [] # (price, timestamp) self.max_heap = [] # (-price, timestamp) def update(self, timestamp: int, price: int) -> None: self.prices[timestamp] = price self.max_time = max(self.max_time, timestamp) heapq.heappush(self.min_heap, (price, timestamp)) heapq.heappush(self.max_heap, (-price, timestamp)) def current(self) -> int: return self.prices[self.max_time] def maximum(self) -> int: while True: price, timestamp = self.max_heap[0] if self.prices[timestamp] == -price: return -price heapq.heappop(self.max_heap) def minimum(self) -> int: while True: price, timestamp = self.min_heap[0] if self.prices[timestamp] == price: return price heapq.heappop(self.min_heap) 9. Implement Trie (Prefix Tree) Notes: Each node in the Trie represents a character. It has a dictionary of children and a flag indicating if it marks the end of a word. Insert, search, and startsWith operations traverse this structure. class TrieNode: def __init__(self): self.children = {} self.is_end_of_word = False class Trie: def __init__(self): self.root = TrieNode() def insert(self, word: str) -> None: node = self.root for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] node.is_end_of_word = True def search(self, word: str) -> bool: node = self._search_prefix(word) return node is not None and node.is_end_of_word def startsWith(self, prefix: str) -> bool: return self._search_prefix(prefix) is not None def _search_prefix(self, prefix: str) -> TrieNode: node = self.root for char in prefix: if char not in node.children: return None node = node.children[char] return node 10. Design Add and Search Words Data Structure Notes: Similar to Trie, but handle '.' wildcard in search. For '.', recursively try all possible children. This means search will be a DFS/backtracking approach. class TrieNode: def __init__(self): self.children = {} self.is_end_of_word = False class WordDictionary: def __init__(self): self.root = TrieNode() def addWord(self, word: str) -> None: node = self.root for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] node.is_end_of_word = True def search(self, word: str) -> bool: def dfs(node, k): if k == len(word): return node.is_end_of_word char = word[k] if char == ".": for child_char in node.children: if dfs(node.children[child_char], k + 1): return True return False else: if char in node.children: return dfs(node.children[char], k + 1) else: return False return dfs(self.root, 0) 11. Search Suggestions System Notes: Insert all products into a Trie. For each prefix, traverse the Trie and collect up to 3 words. A DFS from the current Trie node can find all words starting with that prefix efficiently. class TrieNode: def __init__(self): self.children = {} self.is_end_of_word = False self.words = [] # Store words that pass through this node, for suggestions class Solution: def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]: products.sort() # Important for lexical order root = TrieNode() def insert(word): node = root for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] node.words.append(word) # Store word at each node it passes node.words.sort() if len(node.words) > 3: # Keep only top 3 lexicographically node.words.pop() node.is_end_of_word = True for p in products: insert(p) res = [] node = root for i, char in enumerate(searchWord): if node and char in node.children: node = node.children[char] res.append(node.words) else: # No more matching prefix node = None res.append([]) return res 12. Longest Word in Dictionary Notes: Insert all words into a Trie. Then, iterate through the words again. A word can be built if all its prefixes (down to length 1) exist in the Trie and are marked as end-of-word. Keep track of the longest valid word found. class TrieNode: def __init__(self): self.children = {} self.is_end_of_word = False class Solution: def longestWord(self, words: List[str]) -> str: root = TrieNode() def insert(word): node = root for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] node.is_end_of_word = True for word in words: insert(word) longest_word = "" # DFS to find the longest word constructible from other words def dfs(node, current_word): nonlocal longest_word if len(current_word) > len(longest_word) or \ (len(current_word) == len(longest_word) and current_word 13. Maximum XOR of Two Numbers in an Array Notes: Build a Trie (binary trie) where each number is represented by its bits (e.g., 31 bits for max integer). To find max XOR for a number, traverse the Trie. At each bit, try to go the opposite path (e.g., if current bit is 1, try to go to 0) to maximize XOR. If opposite path exists, take it; otherwise, take the same path. class TrieNode: def __init__(self): self.children = {} # 0 or 1 class Solution: def findMaximumXOR(self, nums: List[int]) -> int: # Assume numbers are 31-bit integers L = 31 root = TrieNode() # Insert all numbers into the Trie for num in nums: node = root for i in range(L, -1, -1): bit = (num >> i) & 1 if bit not in node.children: node.children[bit] = TrieNode() node = node.children[bit] max_xor = 0 # For each number, find its maximum XOR pair for num in nums: node = root current_xor = 0 for i in range(L, -1, -1): bit = (num >> i) & 1 # Try to find the opposite bit to maximize XOR opposite_bit = 1 - bit if opposite_bit in node.children: current_xor |= (1 14. Furthest Building You Can Reach Notes: Greedy approach using a min-heap. Iterate through buildings. If a jump is needed, use bricks. If we run out of bricks, check if we have any prior jump that used bricks that could have been covered by a ladder. Replace the largest brick-jump with a ladder if possible, and reuse the bricks. Min-heap stores brick-jumps. import heapq class Solution: def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int: # Min-heap to store the heights of jumps covered by bricks # We need to access the smallest brick jump to replace it with a ladder # and reclaim bricks. brick_jumps = [] for i in range(len(heights) - 1): climb = heights[i+1] - heights[i] if climb 0: # And we have ladders left # Use a ladder for the largest jump currently covered by bricks # This is why we use a min-heap: the smallest element in the heap # is the largest climb if we negate values. # Wait, no, we need to replace the *largest* brick jump with a ladder. # So, we need a max-heap, or negate values in a min-heap. # Let's use a min-heap and pop the largest brick jump if bricks 15. Single-Threaded CPU Notes: Use a min-heap. Sort tasks by enqueue time. Simulate CPU processing. When CPU is idle or a task finishes, add all available tasks (enqueue_time import heapq class Solution: def getOrder(self, tasks: List[List[int]]) -> List[int]: # Add original index to tasks for output indexed_tasks = [] for i, (enqueue_time, process_time) in enumerate(tasks): indexed_tasks.append((enqueue_time, process_time, i)) # Sort tasks by enqueue time indexed_tasks.sort() n = len(tasks) result = [] min_heap = [] # (process_time, original_index) current_time = 0 task_ptr = 0 # Pointer to the next task in indexed_tasks while len(result) 16. Process Tasks Using Servers Notes: Use two min-heaps. One for available servers (weight, index) , and one for busy servers (available_time, weight, index) . Simulate time. At each step, move servers from busy to available if their available_time is met. Then, process tasks using available servers. If no servers are available, advance time to when the next busy server becomes free. import heapq class Solution: def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]: n_servers = len(servers) n_tasks = len(tasks) # Min-heap for available servers: (weight, index) available_servers = [(servers[i], i) for i in range(n_servers)] heapq.heapify(available_servers) # Min-heap for busy servers: (available_time, weight, index) busy_servers = [] result = [0] * n_tasks current_time = 0 task_idx = 0 while task_idx 17. Top K Frequent Elements Notes: Count frequencies using a hash map. Then, use a min-heap to keep track of the $k$ most frequent elements. Iterate through the map's items, pushing (frequency, element) to the heap. If heap size exceeds $k$, pop the smallest element (least frequent). import collections import heapq class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: counts = collections.Counter(nums) # Min-heap to store (frequency, number) min_heap = [] for num, freq in counts.items(): heapq.heappush(min_heap, (freq, num)) if len(min_heap) > k: heapq.heappop(min_heap) return [num for freq, num in min_heap] 18. K Closest Points to Origin Notes: Use a max-heap. Store (-distance, x, y) . Iterate through points, calculate distance, push to heap. If heap size exceeds $k$, pop the largest element (furthest point). The negative distance makes it a max-heap for distance. import heapq class Solution: def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]: max_heap = [] # Stores (-distance_squared, x, y) for x, y in points: dist_sq = x*x + y*y heapq.heappush(max_heap, (-dist_sq, x, y)) if len(max_heap) > k: heapq.heappop(max_heap) # Remove the point with largest distance return [[x, y] for (dist_sq, x, y) in max_heap] 19. Merge Intervals Notes: Sort intervals by their start times. Iterate through sorted intervals. If the current interval overlaps with the last merged interval, merge them by updating the end of the last merged interval. Otherwise, add the current interval as a new merged interval. class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key=lambda x: x[0]) merged = [] for interval in intervals: # If the list of merged intervals is empty or if the current # interval does not overlap with the previous, simply append it. if not merged or merged[-1][1] 20. Insert Interval Notes: Similar to merge intervals. Find the position to insert the new interval. Then, merge any overlapping intervals around it. A common pattern is to add non-overlapping intervals before the new one, merge the new one with any overlaps, then add remaining non-overlapping intervals. class Solution: def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: res = [] n = len(intervals) i = 0 # Add all intervals that come before newInterval and don't overlap while i 21. Minimum Number of Arrows to Burst Balloons Notes: Sort balloons by their end points. Iterate through sorted balloons. Shoot an arrow at the end point of the first balloon. This arrow will burst all balloons that start before or at this point and end after or at this point. Increment arrow count and move to the next unburst balloon. class Solution: def findMinArrowShots(self, points: List[List[int]]) -> int: if not points: return 0 # Sort points by their end coordinate points.sort(key=lambda x: x[1]) arrows = 1 # The first arrow is shot at the end of the first balloon end_of_current_arrow = points[0][1] for i in range(1, len(points)): # If the current balloon starts after the current arrow's endpoint, # we need a new arrow. if points[i][0] > end_of_current_arrow: arrows += 1 end_of_current_arrow = points[i][1] # Shoot new arrow at this balloon's end # Else, the current balloon is busted by the current arrow, # no need to update end_of_current_arrow as it's already optimal (furthest left end point) return arrows 22. Maximum Number of Events That Can Be Attended Notes: Sort events by start day. Use a min-heap to keep track of end days of events that are currently available. Iterate through days. On each day, add all new events that start today to the heap. Remove events from the heap that have already ended. If there are events in the heap, attend the one that ends earliest (pop from heap), and increment attended count. import heapq class Solution: def maxEvents(self, events: List[List[int]]) -> int: events.sort() # Sort by start day n = len(events) attended_events = 0 min_heap = [] # Stores end_day of available events day = 0 event_idx = 0 # Loop until all events are considered and all available events are processed while event_idx 23. Non-overlapping Intervals Notes: This is identical to "Minimum Number of Arrows to Burst Balloons" in logic. Sort intervals by end times. Iterate and count non-overlapping intervals. The number of intervals to remove is total intervals minus max non-overlapping intervals. class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: if not intervals: return 0 # Sort intervals by their end coordinate intervals.sort(key=lambda x: x[1]) end_of_last_non_overlapping = intervals[0][1] non_overlapping_count = 1 for i in range(1, len(intervals)): if intervals[i][0] >= end_of_last_non_overlapping: # If current interval starts after or at the end of the last non-overlapping, # it's non-overlapping. non_overlapping_count += 1 end_of_last_non_overlapping = intervals[i][1] # Else, it overlaps, so we "remove" it by doing nothing and moving on. return len(intervals) - non_overlapping_count 24. Find K Pairs with Smallest Sums Notes: Use a min-heap. Initialize with (nums1[0] + nums2[0], 0, 0) . When popping (sum, i, j) , add (nums1[i+1] + nums2[j], i+1, j) (if $i+1 (nums1[i] + nums2[j+1], i, j+1) (if $j+1 (i, j) to avoid duplicates. import heapq class Solution: def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]: m, n = len(nums1), len(nums2) if m == 0 or n == 0 or k == 0: return [] result = [] min_heap = [] # Stores (sum, index1, index2) # Push the first possible pair (nums1[0], nums2[0]) heapq.heappush(min_heap, (nums1[0] + nums2[0], 0, 0)) # Use a set to keep track of visited pairs (index1, index2) to avoid duplicates visited = set([(0, 0)]) while min_heap and len(result) 25. Kth Smallest Element in a Sorted Matrix Notes: Use a min-heap. Initialize with the first element of each row (matrix[i][0], i, 0) . When popping (val, r, c) , add the next element from that row (matrix[r][c+1], r, c+1) if it exists. import heapq class Solution: def kthSmallest(self, matrix: List[List[int]], k: int) -> int: m, n = len(matrix), len(matrix[0]) min_heap = [] # Stores (value, row_idx, col_idx) # Initialize heap with the first element of each row for r in range(min(k, m)): # Only need to consider first k rows initially heapq.heappush(min_heap, (matrix[r][0], r, 0)) # Pop k-1 times, then the k-th pop is the answer for _ in range(k - 1): val, r, c = heapq.heappop(min_heap) if c + 1 26. Design Browser History Notes: Use two stacks (or lists acting as stacks): history for backward navigation and forward_history for forward navigation. visit clears forward_history . back and forward move URLs between stacks. class BrowserHistory: def __init__(self, homepage: str): self.history = [homepage] self.current_idx = 0 def visit(self, url: str) -> None: # Clear forward history self.history = self.history[:self.current_idx + 1] self.history.append(url) self.current_idx = len(self.history) - 1 def back(self, steps: int) -> str: self.current_idx = max(0, self.current_idx - steps) return self.history[self.current_idx] def forward(self, steps: int) -> str: self.current_idx = min(len(self.history) - 1, self.current_idx + steps) return self.history[self.current_idx] 27. Time Based Key-Value Store Notes: Use a dictionary where keys map to a list of (timestamp, value) pairs. The list should be sorted by timestamp. For get , use binary search (bisect_right) to find the largest timestamp less than or equal to the given timestamp. import collections import bisect class TimeMap: def __init__(self): self.store = collections.defaultdict(list) # key -> [(timestamp, value)] def set(self, key: str, value: str, timestamp: int) -> None: self.store[key].append((timestamp, value)) def get(self, key: str, timestamp: int) -> str: if key not in self.store: return "" values = self.store[key] # Binary search to find the rightmost element whose timestamp x. # We are searching for (timestamp, value) where timestamp 28. Snapshot Array Notes: For each index, store a list of (snap_id, value) pairs. snap() increments a global snap_id . get() uses binary search (bisect_right) on the list for the given index to find the value associated with the largest snap_id less than or equal to the query snap_id . import bisect class SnapshotArray: def __init__(self, length: int): # Each index stores a list of (snap_id, value) pairs, sorted by snap_id self.array = [[(0, 0)] for _ in range(length)] self.snap_id = 0 def set(self, index: int, val: int) -> None: # If the last value was set at the current snap_id, update it. # Otherwise, add a new (snap_id, val) entry. if self.array[index][-1][0] == self.snap_id: self.array[index][-1] = (self.snap_id, val) else: self.array[index].append((self.snap_id, val)) def snap(self) -> int: self.snap_id += 1 return self.snap_id - 1 def get(self, index: int, snap_id: int) -> int: # Find the rightmost (snap_id, value) pair where snap_id bisect_right for (7+1, -1) => (8, -1) # It would return index 2 (element (10,20)). We want index 1. So idx-1. # The list stores (snap_id, value). We want the latest value up to the given snap_id. # bisect_right on a list of (snap_id, value) pairs will find the index `i` such that # all `p` in `list[:i]` have `p[0] snap_id`. # So we need `i-1`. # Find the index of the first element whose snap_id is strictly greater than `snap_id`. # `bisect_right` returns `idx` such that all `x` in `a[0...idx-1]` have `x[0] (snap_id, any_val)`. # Since we want the largest snap_id 29. Design Twitter Notes: Use dictionaries for user's tweets and followees. A min-heap (or max-heap depending on implementation) to get the 10 most recent tweets from followed users. When getting news feed, iterate through followees and collect their latest tweets, then merge and select top 10 by timestamp. import collections import heapq class Twitter: def __init__(self): self.timer = 0 self.tweets = collections.defaultdict(list) # userId -> list of (timestamp, tweetId) self.followees = collections.defaultdict(set) # userId -> set of followeeIds def postTweet(self, userId: int, tweetId: int) -> None: self.tweets[userId].append((self.timer, tweetId)) self.timer += 1 def getNewsFeed(self, userId: int) -> List[int]: news_feed = [] # Add self to followees for news feed self.followees[userId].add(userId) # Max-heap to store (timestamp, tweetId) # We want the 10 most recent, so we need to pop largest timestamp # Python's heapq is min-heap, so store (-timestamp, tweetId) max_heap = [] for followee_id in self.followees[userId]: # Get up to 10 latest tweets from each followee # Tweets are already sorted by timestamp (due to self.timer incrementing) for i in range(len(self.tweets[followee_id]) - 1, -1, -1): if len(news_feed) == 10 and self.tweets[followee_id][i][0] 10: # Keep only 10 most recent heapq.heappop(max_heap) # Pop the oldest tweet (smallest timestamp) # Extract tweets from heap, which will be in increasing order of timestamp. # We need decreasing order, so reverse. # Alternative: When building news feed, just add all relevant tweets to a list, # then sort that list by timestamp and take top 10. This is simpler than managing heap size. all_relevant_tweets = [] for followee_id in self.followees[userId]: # Add all tweets from followees (including self) all_relevant_tweets.extend(self.tweets[followee_id]) all_relevant_tweets.sort(key=lambda x: x[0], reverse=True) return [tweet_id for timestamp, tweet_id in all_relevant_tweets[:10]] def follow(self, followerId: int, followeeId: int) -> None: self.followees[followerId].add(followeeId) def unfollow(self, followerId: int, followeeId: int) -> None: if followeeId in self.followees[followerId]: self.followees[followerId].remove(followeeId) 30. LRU Cache Notes: Use a hash map for $O(1)$ access to nodes and a doubly linked list for $O(1)$ updates to recency. The map stores key -> node . The linked list maintains order from most recently used (MRU) to least recently used (LRU). When accessing, move node to MRU. When capacity exceeded, remove LRU node. class Node: def __init__(self, key, val): self.key = key self.val = val self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache = {} # key -> Node # Dummy head and tail for doubly linked list self.head = Node(0, 0) self.tail = Node(0, 0) self.head.next = self.tail self.tail.prev = self.head def _add_node(self, node): # Add node right after head (MRU position) node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def _remove_node(self, node): # Remove node from linked list prev_node = node.prev next_node = node.next prev_node.next = next_node next_node.prev = prev_node def _move_to_front(self, node): self._remove_node(node) self._add_node(node) def get(self, key: int) -> int: if key in self.cache: node = self.cache[key] self._move_to_front(node) # Mark as recently used return node.val return -1 def put(self, key: int, value: int) -> None: if key in self.cache: node = self.cache[key] node.val = value self._move_to_front(node) else: new_node = Node(key, value) self.cache[key] = new_node self._add_node(new_node) # Add to MRU if len(self.cache) > self.capacity: # Remove LRU node (node before tail) lru_node = self.tail.prev self._remove_node(lru_node) del self.cache[lru_node.key] 31. Insert Delete GetRandom O(1) Notes: Use a list to store elements and a dictionary to store value -> index_in_list . This allows $O(1)$ insert and delete (by swapping with last element and popping) and $O(1)$ getRandom (by picking random index). import random class RandomizedSet: def __init__(self): self.val_to_idx = {} # value -> index in self.nums self.nums = [] def insert(self, val: int) -> bool: if val in self.val_to_idx: return False self.val_to_idx[val] = len(self.nums) self.nums.append(val) return True def remove(self, val: int) -> bool: if val not in self.val_to_idx: return False idx_to_remove = self.val_to_idx[val] last_elem = self.nums[-1] # Move the last element to the position of the element to be removed self.nums[idx_to_remove] = last_elem self.val_to_idx[last_elem] = idx_to_remove # Remove the last element (which is now a duplicate or the original element if it was last) self.nums.pop() del self.val_to_idx[val] return True def getRandom(self) -> int: return random.choice(self.nums) 32. Design A Food Rating System Notes: Use three dictionaries: 1. food_rating: food_name -> rating 2. food_cuisine: food_name -> cuisine_name 3. cuisine_ratings: cuisine_name -> min-heap of (-rating, food_name) . Max-heap for ratings, min-heap for lexical order if ratings are equal. Use lazy deletion for updates. import collections import heapq class FoodRatings: def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]): self.food_to_rating = {} # food -> rating self.food_to_cuisine = {} # food -> cuisine # cuisine -> max-heap of (-rating, food_name) # Use a min-heap by storing (-rating, food_name) to get highest rating. # If ratings are same, min-heap on food_name (lexicographical) self.cuisine_to_ratings = collections.defaultdict(list) for i in range(len(foods)): food, cuisine, rating = foods[i], cuisines[i], ratings[i] self.food_to_rating[food] = rating self.food_to_cuisine[food] = cuisine heapq.heappush(self.cuisine_to_ratings[cuisine], (-rating, food)) def changeRating(self, food: str, newRating: int) -> None: self.food_to_rating[food] = newRating cuisine = self.food_to_cuisine[food] # Push to heap. The old entry will be lazily deleted when queried. heapq.heappush(self.cuisine_to_ratings[cuisine], (-newRating, food)) def highestRated(self, cuisine: str) -> str: # Lazily delete outdated entries while True: neg_rating, food = self.cuisine_to_ratings[cuisine][0] if self.food_to_rating[food] == -neg_rating: return food heapq.heappop(self.cuisine_to_ratings[cuisine]) 33. Jump Game II Notes: BFS-like approach. Maintain current_reach (farthest point reachable with current jumps) and next_reach (farthest point reachable with one more jump). When current position exceeds current_reach , increment jump count and update current_reach = next_reach . Greedy: always try to extend next_reach as much as possible. class Solution: def jump(self, nums: List[int]) -> int: n = len(nums) if n = n - 1: # If we can reach or pass the end break return jumps 34. Minimum Add to Make Parentheses Valid Notes: Iterate through the string. Maintain a balance counter. Increment for '(', decrement for ')'. If balance drops below 0 (meaning a ')' without a matching '('), increment ans (representing an needed '(') and reset balance to 0. After iteration, any remaining positive balance means unmatched '(' needing ')'s, so add balance to ans . class Solution: def minAddToMakeValid(self, s: str) -> int: ans = 0 balance = 0 # Counts open parentheses that are not yet closed for char in s: if char == '(': balance += 1 else: # char == ')' balance -= 1 if balance 35. Gas Station Notes: If total gas is less than total cost, no solution. Otherwise, a unique solution exists. Iterate through stations, tracking current tank. If tank drops below 0, it means we cannot start from any station between the last potential start and current. Reset current tank to 0 and set current station as new potential start. class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: if sum(gas) 36. Task Scheduler Notes: Max-heap for frequencies. Count frequencies of each task. The idea is to schedule the most frequent tasks first, separated by n cooldown intervals. Calculate the number of idle slots created by the most frequent task. Then, try to fill these idle slots with other tasks. The formula for minimum intervals is (max_freq - 1) * (n + 1) + count_of_max_freq_tasks , but it can't be less than total tasks. import collections import heapq class Solution: def leastInterval(self, tasks: List[str], n: int) -> int: counts = collections.Counter(tasks) max_freq = 0 for task in counts: max_freq = max(max_freq, counts[task]) # Calculate the number of tasks that have the maximum frequency max_freq_tasks_count = 0 for task in counts: if counts[task] == max_freq: max_freq_tasks_count += 1 # The minimum number of intervals required is determined by the most frequent task. # Consider the slots (max_freq - 1) * n between the occurrences of the most frequent task. # E.g., A _ _ A _ _ A (n=2, max_freq=3) # Total slots created by max_freq_task: (max_freq - 1) * (n + 1) # A _ _ A _ _ A -> (3-1)*(2+1) = 2*3 = 6 slots. A uses 3. Total 6 + 3 = 9. # But if there are multiple tasks with max_freq, they occupy the last slots. # A B _ A B _ A B -> (max_freq - 1) * (n + 1) + max_freq_tasks_count # This formula calculates the length of the schedule if there are enough idle slots # to separate the most frequent tasks by 'n' intervals. min_intervals = (max_freq - 1) * (n + 1) + max_freq_tasks_count # However, the total time cannot be less than the total number of tasks. return max(min_intervals, len(tasks)) 37. Number of Islands Notes: Use BFS or DFS. Iterate through grid. If grid[r][c] == '1' , increment island count and start a traversal (BFS/DFS) from (r, c) to mark all connected '1's as visited (e.g., change to '0') so they aren't counted again. import collections class Solution: def numIslands(self, grid: List[List[str]]) -> int: if not grid or not grid[0]: return 0 rows, cols = len(grid), len(grid[0]) num_islands = 0 def bfs(r, c): q = collections.deque() q.append((r, c)) grid[r][c] = '0' # Mark as visited while q: curr_r, curr_c = q.popleft() for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]: next_r, next_c = curr_r + dr, curr_c + dc if 0 38. Time Needed to Inform All Employees Notes: This is a graph traversal problem. Build an adjacency list where manager[i] points to i . Start a DFS/BFS from the headID . For each manager, the time to inform their subordinates is time_to_inform_manager + informTime[manager_id] . Keep track of the maximum such time. import collections class Solution: def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int: adj = collections.defaultdict(list) # manager -> [subordinates] for i in range(n): if manager[i] != -1: adj[manager[i]].append(i) # BFS to find max time q = collections.deque([(headID, 0)]) # (employee_id, time_taken_to_inform_this_employee) max_time = 0 while q: employee_id, time_to_inform = q.popleft() max_time = max(max_time, time_to_inform) current_inform_time = informTime[employee_id] for subordinate in adj[employee_id]: q.append((subordinate, time_to_inform + current_inform_time)) return max_time 39. All Paths From Source to Target Notes: DFS (backtracking) from source to target. Maintain a current_path list. When reaching the target, add a copy of current_path to results. Backtrack by popping from current_path . class Solution: def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]: n = len(graph) target = n - 1 results = [] def dfs(node, current_path): current_path.append(node) if node == target: results.append(list(current_path)) # Add a copy current_path.pop() # Backtrack return for neighbor in graph[node]: dfs(neighbor, current_path) current_path.pop() # Backtrack dfs(0, []) return results 40. Clone Graph Notes: Use BFS or DFS. Maintain a dictionary to store mappings from original nodes to cloned nodes. When traversing, if a node is not yet cloned, create its copy and add to map, then process its neighbors. If a neighbor is already cloned, just add it to current node's neighbors; otherwise, recursively clone it. # Definition for a Node. class Node: def __init__(self, val = 0, neighbors = None): self.val = val self.neighbors = neighbors if neighbors is not None else [] import collections class Solution: def cloneGraph(self, node: 'Node') -> 'Node': if not node: return None # Dictionary to store copies of visited nodes # old_node_val -> new_node_object visited = {} q = collections.deque([node]) visited[node.val] = Node(node.val) # Create copy of starting node while q: curr_node = q.popleft() for neighbor in curr_node.neighbors: if neighbor.val not in visited: visited[neighbor.val] = Node(neighbor.val) # Create copy of neighbor q.append(neighbor) # Add original neighbor to queue for processing # Add the copied neighbor to the current copied node's neighbors list visited[curr_node.val].neighbors.append(visited[neighbor.val]) return visited[node.val] 41. Is Graph Bipartite? Notes: Use BFS or DFS. Assign colors (e.g., 0 and 1) to nodes. Start traversal from an uncolored node, assign it color 0. All its neighbors must be color 1. All neighbors of color 1 nodes must be color 0, and so on. If a conflict arises (neighbor already colored with the same color), the graph is not bipartite. import collections class Solution: def isBipartite(self, graph: List[List[int]]) -> bool: n = len(graph) colors = [-1] * n # -1: uncolored, 0: color A, 1: color B for i in range(n): if colors[i] == -1: # If node is uncolored, start BFS/DFS q = collections.deque([i]) colors[i] = 0 # Assign initial color A while q: u = q.popleft() for v in graph[u]: if colors[v] == -1: # Uncolored neighbor colors[v] = 1 - colors[u] # Assign opposite color q.append(v) elif colors[v] == colors[u]: # Conflict: same color return False return True 42. All Nodes Distance K in Binary Tree Notes: Convert the tree into an undirected graph (adjacency list). Then, perform a BFS starting from the target node. Keep track of distance and visited nodes. Collect all nodes at distance $K$. import collections # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]: if not root: return [] # 1. Build an undirected graph (adjacency list) adj = collections.defaultdict(list) def build_graph(node, parent): if parent: adj[node.val].append(parent.val) adj[parent.val].append(node.val) if node.left: build_graph(node.left, node) if node.right: build_graph(node.right, node) build_graph(root, None) # 2. Perform BFS from target node q = collections.deque([(target.val, 0)]) # (node_val, distance) visited = {target.val} result = [] while q: curr_val, dist = q.popleft() if dist == k: result.append(curr_val) continue # No need to explore further from nodes at distance k for neighbor_val in adj[curr_val]: if neighbor_val not in visited: visited.add(neighbor_val) q.append((neighbor_val, dist + 1)) return result 43. Employee Importance Notes: Use a dictionary to map employee ID to Employee object for $O(1)$ lookup. Then, use DFS or BFS starting from the id to sum up importance values of the employee and all their subordinates. # Definition for Employee. class Employee: def __init__(self, id: int, importance: int, subordinates: List[int]): self.id = id self.importance = importance self.subordinates = subordinates import collections class Solution: def getImportance(self, employees: List['Employee'], id: int) -> int: # Map employee ID to Employee object for quick lookup employee_map = {emp.id: emp for emp in employees} total_importance = 0 q = collections.deque([id]) # Start BFS from the given id while q: curr_id = q.popleft() employee = employee_map[curr_id] total_importance += employee.importance for sub_id in employee.subordinates: q.append(sub_id) return total_importance 44. Surrounded Regions Notes: Any 'O' on the border or connected to a border 'O' cannot be flipped. Use DFS/BFS to mark all such 'O's (e.g., change to 'E'). Then, iterate through the grid: flip remaining 'O's to 'X', and change 'E's back to 'O'. import collections class Solution: def solve(self, board: List[List[str]]) -> None: if not board or not board[0]: return rows, cols = len(board), len(board[0]) def dfs(r, c): if not (0 45. Pacific Atlantic Water Flow Notes: Use two separate BFS/DFS traversals. One starting from all cells on the Pacific border to find all cells that can reach Pacific. Another starting from all cells on the Atlantic border to find all cells that can reach Atlantic. The intersection of these two sets of cells is the answer. import collections class Solution: def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: if not heights or not heights[0]: return [] rows, cols = len(heights), len(heights[0]) pacific_reachable = set() atlantic_reachable = set() def bfs(start_cells, reachable_set): q = collections.deque(start_cells) while q: r, c = q.popleft() if (r, c) in reachable_set: continue reachable_set.add((r, c)) for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]: nr, nc = r + dr, c + dc if 0 = heights[r][c]: # Water flows from higher to lower, but we are simulating reverse flow q.append((nr, nc)) # Initialize Pacific border cells pacific_start_cells = [] for r in range(rows): pacific_start_cells.append((r, 0)) # Left border for c in range(cols): pacific_start_cells.append((0, c)) # Top border # Initialize Atlantic border cells atlantic_start_cells = [] for r in range(rows): atlantic_start_cells.append((r, cols - 1)) # Right border for c in range(cols): atlantic_start_cells.append((rows - 1, c)) # Bottom border bfs(pacific_start_cells, pacific_reachable) bfs(atlantic_start_cells, atlantic_reachable) # Find intersection return list(pacific_reachable.intersection(atlantic_reachable)) 46. Rotting Oranges Notes: BFS. Start with all initially rotten oranges in the queue. Each level of BFS represents one minute. Keep track of the number of fresh oranges. If a fresh orange turns rotten, decrement fresh count. If the queue becomes empty and fresh oranges still exist, return -1. import collections class Solution: def orangesRotting(self, grid: List[List[int]]) -> int: rows, cols = len(grid), len(grid[0]) q = collections.deque() fresh_oranges = 0 # Initialize queue with all rotten oranges and count fresh ones for r in range(rows): for c in range(cols): if grid[r][c] == 2: q.append((r, c, 0)) # (row, col, time) elif grid[r][c] == 1: fresh_oranges += 1 max_time = 0 while q: r, c, time = q.popleft() max_time = max(max_time, time) for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]: nr, nc = r + dr, c + dc if 0 47. 01 Matrix Notes: BFS. Initialize all 0s with distance 0 and put them in queue. Initialize all 1s with distance infinity. Perform multi-source BFS; when visiting a neighbor, if its current distance is greater than current_node_distance + 1 , update its distance and add to queue. import collections class Solution: def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]: rows, cols = len(mat), len(mat[0]) dist = [[float('inf')] * cols for _ in range(rows)] q = collections.deque() # Initialize queue with all 0s and set their distance to 0 for r in range(rows): for c in range(cols): if mat[r][c] == 0: q.append((r, c)) dist[r][c] = 0 while q: r, c = q.popleft() for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]: nr, nc = r + dr, c + dc if 0 dist[r][c] + 1: dist[nr][nc] = dist[r][c] + 1 q.append((nr, nc)) return dist 48. Open the Lock Notes: BFS to find the shortest path. Each state is a 4-digit string. Neighbors are generated by rotating each digit up or down. Keep track of visited states and deadends. Start BFS from "0000" to `target`. import collections class Solution: def openLock(self, deadends: List[str], target: str) -> int: dead_set = set(deadends) start = "0000" if start in dead_set: return -1 q = collections.deque([(start, 0)]) # (current_lock_state, steps) visited = {start} def get_neighbors(s): neighbors = [] for i in range(4): digit = int(s[i]) # Rotate up new_digit_up = str((digit + 1) % 10) neighbors.append(s[:i] + new_digit_up + s[i+1:]) # Rotate down new_digit_down = str((digit - 1 + 10) % 10) neighbors.append(s[:i] + new_digit_down + s[i+1:]) return neighbors while q: curr_state, steps = q.popleft() if curr_state == target: return steps for neighbor in get_neighbors(curr_state): if neighbor not in visited and neighbor not in dead_set: visited.add(neighbor) q.append((neighbor, steps + 1)) return -1 # Target not reachable 49. Course Schedule II Notes: Topological sort using Kahn's algorithm (BFS) or DFS. Kahn's (BFS): Build adjacency list and calculate in-degrees for all nodes. Add all nodes with in-degree 0 to a queue. While queue is not empty, pop a node, add to result, and decrement in-degree of its neighbors. If a neighbor's in-degree becomes 0, add it to queue. If number of visited nodes equals total nodes, a valid order exists; otherwise, a cycle exists. DFS: Use 3 states for nodes (unvisited, visiting, visited). Detect cycle if visiting a node marked 'visiting'. import collections class Solution: def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: # Build adjacency list: course -> [list of courses that depend on this course] adj = collections.defaultdict(list) # Calculate in-degrees: course -> number of prerequisites it has in_degree = [0] * numCourses for course, prereq in prerequisites: adj[prereq].append(course) in_degree[course] += 1 # Initialize queue with all courses that have no prerequisites q = collections.deque() for i in range(numCourses): if in_degree[i] == 0: q.append(i) result = [] while q: curr_course = q.popleft() result.append(curr_course) # Decrement in-degree of neighbors for neighbor_course in adj[curr_course]: in_degree[neighbor_course] -= 1 if in_degree[neighbor_course] == 0: q.append(neighbor_course) # If all courses are included in result, a valid order exists if len(result) == numCourses: return result else: return [] # Cycle detected, impossible to finish all courses 50. Find Eventual Safe States Notes: A node is a safe state if all paths starting from it lead to a terminal node (a node with no outgoing edges) or to another safe state. This is a graph problem, can be solved by detecting cycles and nodes leading to cycles. Use 3 states: 0 (unvisited), 1 (visiting/in current path), 2 (safe). DFS. If DFS encounters a node in state 1, it's a cycle. If it encounters a node in state 2, it's safe. If it encounters a node in state 0, recurse. import collections class Solution: def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]: n = len(graph) # 0: unvisited, 1: visiting (in current DFS path), 2: safe, 3: unsafe (leads to cycle) # Using 0, 1, 2 for states as per common patterns. # States: 0 (uncolored), 1 (visiting), 2 (safe) color = [0] * n res = [] def dfs(node): if color[node] != 0: # If already processed or in current path return color[node] == 2 # Return if it's safe (2) or not (1 or 3) color[node] = 1 # Mark as visiting for neighbor in graph[node]: if not dfs(neighbor): # If any path from neighbor leads to unsafe/cycle color[node] = 3 # Mark current node as unsafe return False color[node] = 2 # All paths from node lead to safe states/terminal nodes return True for i in range(n): if dfs(i): res.append(i) return sorted(res)