Medium Problems
Use a hash map for O(1) key lookup combined with a doubly linked list for O(1) insertion and removal. The hash map stores key-to-node references, while the linked list maintains access order. On every get or put, move the node to the head; on capacity overflow, evict the tail node.
Sort intervals by start time. Iterate through them, and if the current interval overlaps with the last merged interval (current start <= last end), extend the last merged interval's end. Otherwise, start a new merged interval.
Model courses as a directed graph where edges represent prerequisites. Detect if a cycle exists using DFS with three states (unvisited, in-progress, visited) or Kahn's BFS algorithm with in-degree tracking. If a cycle exists, not all courses can be finished.
Iterate through every cell. When you find a '1' that hasn't been visited, increment your island count and run BFS or DFS to mark all connected '1' cells as visited. Each BFS/DFS call fully explores one island.
Use a sliding window with two pointers and a hash map that stores the last index of each character. When a duplicate is found, jump the left pointer to one past the duplicate's last position. Track the maximum window size throughout.
Sort the array. For each element, fix it as the first number and use two pointers (left and right) on the remaining subarray to find pairs that sum to the negative of the fixed element. Skip duplicate values at each level to avoid duplicate triplets.
Place two pointers at the start and end. Calculate the area between them (width * min height). Always move the pointer that has the shorter line inward, because keeping it would never produce a larger area since width is shrinking.
Use a hash map where the key is a canonical form of each word (sorted characters or a character-count tuple). All anagrams share the same canonical key, so group them in the same bucket. Return the values of the hash map.
tuple(Counter(s).values()) or a fixed-size count array.For each cell that matches the first character, run DFS/backtracking exploring all four directions. Mark cells as visited during exploration and unmark them when backtracking. If the entire word is matched, return True.
Build a DP array where dp[i] is the fewest coins needed to make amount i. Initialize all values to infinity except dp[0] = 0. For each amount from 1 to target, try every coin and take min(dp[i], dp[i - coin] + 1).
Use the expand-around-center technique. For each index, try expanding outward treating that index as the center of both an odd-length and even-length palindrome. Track the longest palindrome found. This avoids the O(n^2) space of the full DP table.
Use modified binary search. At each step, determine which half is sorted by comparing nums[mid] with nums[left]. If the target falls within the sorted half, search there; otherwise, search the other half.
mid is always sorted. Identifying the sorted half lets you decide which direction to search with a simple range check.Perform an in-order traversal of the BST (left, node, right). The in-order traversal of a BST visits nodes in sorted order. Maintain a counter and return the node when the counter reaches k. Use an iterative stack-based approach for early termination.
Use BFS with a queue. Process one level at a time by recording the queue size at the start of each level, then dequeuing exactly that many nodes. Add each node's children to the queue and collect the level's values into a sublist.
len(queue) at the start of each level. This tells you exactly how many nodes belong to the current level before their children are added.Count frequencies with a hash map. Then use either a min-heap of size k (push each element, pop when size exceeds k) or bucket sort where index = frequency. Bucket sort gives O(n) time: create n+1 buckets, place elements in their frequency bucket, then collect from the highest bucket down.
Create a boolean DP array where dp[i] is True if the substring s[0:i] can be segmented into dictionary words. For each position i, check all possible last-word boundaries j: if dp[j] is True and s[j:i] is in the dictionary, set dp[i] = True.
The O(n^2) DP approach sets dp[i] = length of LIS ending at index i. For O(n log n), maintain a "tails" array: for each number, use binary search (bisect_left) to find where it fits. If it extends the sequence, append; otherwise, replace the smallest tail that's >= it.
bisect_left for the binary search.Hard Problems
Use a sliding window with two hash maps: one for the target character counts and one for the current window. Expand the right pointer until the window contains all required characters. Then shrink the left pointer to minimize the window while maintaining validity. Track the smallest valid window.
Use two pointers (left and right) with running max heights from each side. The water at any position is min(left_max, right_max) - height[i]. Move the pointer with the smaller max inward. Alternatively, precompute left_max and right_max arrays, or use a monotonic stack.
Binary search on the shorter array to find the correct partition. The partition divides both arrays so that all elements on the left are smaller than all elements on the right. Check boundary conditions: maxLeftA <= minRightB and maxLeftB <= minRightA.
j = (m+n+1)//2 - i. Handle edge cases with -infinity and +infinity sentinels.Push the head of each list into a min-heap. Repeatedly pop the smallest node, add it to the result, and push its next node into the heap. Alternatively, use divide-and-conquer to merge lists pairwise, halving the number of lists each round.
Model the problem as an unweighted graph where each word is a node and edges connect words that differ by one character. Use BFS from the start word to find the shortest path to the end word. Preprocess using wildcard patterns (e.g., "h*t") for efficient neighbor lookup.
Compare adjacent words to extract ordering rules: find the first differing character between each consecutive pair to build directed edges. Run topological sort (BFS/Kahn's or DFS) on the character graph. Detect invalid inputs (e.g., "abc" before "ab").
Build a 2D DP table where dp[i][j] is the minimum edit distance between word1[0:i] and word2[0:j]. If characters match, dp[i][j] = dp[i-1][j-1]. Otherwise, take the minimum of insert (dp[i][j-1]), delete (dp[i-1][j]), and replace (dp[i-1][j-1]), plus 1.
Serialize using preorder traversal, recording null nodes as a sentinel (e.g., "N"). Deserialize by reading tokens sequentially: each token is either a value (create a node) or the sentinel (return None). Use a queue or iterator to consume tokens during recursive reconstruction.
Ready to crack the interview?
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →