25
Problems
17
Medium
8
Hard
10
Patterns

Medium Problems

1
LRU Cache
#146 Medium
Design Hash Map Linked List
Amazon Meta Google Microsoft

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.

Key insight: The doubly linked list lets you remove any node in O(1) without scanning, because each node holds prev/next pointers and the hash map gives you direct access to the node.
Time: O(1) get/putSpace: O(capacity)
2
Merge Intervals
#56 Medium
Array Greedy / Sorting
Google Meta Bloomberg

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.

Key insight: After sorting by start time, overlapping intervals are always adjacent. You only need to compare each interval with the last merged one, not with all previous intervals.
Time: O(n log n)Space: O(n)
3
Course Schedule
#207 Medium
Graph Topological Sort
Amazon Microsoft Apple

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.

Key insight: This is cycle detection in a directed graph. If you can produce a valid topological ordering of all nodes, there is no cycle and all courses can be completed.
Time: O(V + E)Space: O(V + E)
4
Number of Islands
#200 Medium
Graph BFS / DFS
Amazon Google Meta

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.

Key insight: This is connected-component counting on a 2D grid. You can modify the grid in-place (set visited cells to '0') to avoid extra space for a visited set.
Time: O(m * n)Space: O(m * n)
5
Longest Substring Without Repeating Characters
#3 Medium
String Sliding Window Hash Map
Amazon Meta Bloomberg Google

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.

Key insight: Store each character's last-seen index in the hash map. When you encounter a duplicate, you can skip the left pointer directly instead of shrinking one step at a time.
Time: O(n)Space: O(min(n, m))
6
3Sum
#15 Medium
Array Two Pointers
Meta Amazon Microsoft Apple

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.

Key insight: Sorting enables the two-pointer approach and makes duplicate-skipping straightforward. The key trap is forgetting to skip duplicates for the outer loop element as well as the inner pointers.
Time: O(n^2)Space: O(1) extra
7
Container With Most Water
#11 Medium
Array Two Pointers
Amazon Goldman Sachs Google

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.

Key insight: Moving the shorter pointer is safe because the current area is already the maximum possible with that shorter line at that width. Moving the taller pointer can only decrease or maintain the height while reducing width.
Time: O(n)Space: O(1)
8
Group Anagrams
#49 Medium
String Hash Map
Amazon Meta Uber

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.

Key insight: Using a tuple of 26 character counts as the hash key avoids the O(k log k) sorting cost per word, giving O(k) per word instead. In Python: tuple(Counter(s).values()) or a fixed-size count array.
Time: O(n * k)Space: O(n * k)
9
Word Search
#79 Medium
Backtracking String
Amazon Microsoft Bloomberg

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.

Key insight: Temporarily modify the board cell (e.g., set to '#') to mark it as visited during the current path, then restore it when backtracking. This avoids needing a separate visited set.
Time: O(m * n * 4^L)Space: O(L)
10
Coin Change
#322 Medium
Dynamic Programming
Amazon Apple Google

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

Key insight: This is the unbounded knapsack variant. The greedy approach (always picking the largest coin) fails for certain denominations, so DP is necessary to guarantee the optimal solution.
Time: O(amount * coins)Space: O(amount)
11
Longest Palindromic Substring
#5 Medium
String Dynamic Programming
Amazon Microsoft Meta

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.

Key insight: There are 2n - 1 possible centers (n single characters + n - 1 gaps between characters). Expanding from each center takes O(n) in the worst case, giving O(n^2) time with O(1) extra space.
Time: O(n^2)Space: O(1)
12
Search in Rotated Sorted Array
#33 Medium
Array Binary Search
Meta Amazon Microsoft LinkedIn

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.

Key insight: In a rotated sorted array, at least one half around mid is always sorted. Identifying the sorted half lets you decide which direction to search with a simple range check.
Time: O(log n)Space: O(1)
13
Kth Smallest Element in a BST
#230 Medium
Tree
Amazon Meta Uber

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.

Key insight: BST in-order traversal produces sorted output. You don't need to collect all elements — just stop as soon as you've visited k nodes, giving you O(H + k) time instead of O(n).
Time: O(H + k)Space: O(H)
14
Binary Tree Level Order Traversal
#102 Medium
Tree BFS
Amazon Meta Microsoft

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.

Key insight: The trick is snapshotting 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.
Time: O(n)Space: O(n)
15
Top K Frequent Elements
#347 Medium
Array Hash Map Heap
Amazon Meta Google

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.

Key insight: Bucket sort avoids the O(n log k) heap cost. Since frequencies range from 1 to n, you can use the frequency as an array index for O(n) overall complexity.
Time: O(n)Space: O(n)
16
Word Break
#139 Medium
Dynamic Programming String
Amazon Meta Bloomberg

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.

Key insight: Convert the word list to a set for O(1) lookups. Optionally limit the inner loop to the max word length in the dictionary to prune unnecessary checks.
Time: O(n^2 * k)Space: O(n)
17
Longest Increasing Subsequence
#300 Medium
Dynamic Programming Binary Search
Amazon Google Microsoft

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.

Key insight: The tails array doesn't store the actual LIS — it stores the smallest possible tail element for each subsequence length. Its length equals the LIS length. Use Python's bisect_left for the binary search.
Time: O(n log n)Space: O(n)

Hard Problems

18
Minimum Window Substring
#76 Hard
String Sliding Window Hash Map
Meta Amazon Google Airbnb

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.

Key insight: Maintain a "formed" counter that tracks how many unique characters in the window have met their required frequency. This avoids recomputing validity from scratch on every step.
Time: O(|s| + |t|)Space: O(|s| + |t|)
19
Trapping Rain Water
#42 Hard
Array Two Pointers Stack
Amazon Goldman Sachs Google Meta

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.

Key insight: The two-pointer approach works because the water level at any bar is determined by the shorter of the two maximum heights. You always process the side with the smaller max because it's the bottleneck.
Time: O(n)Space: O(1)
20
Median of Two Sorted Arrays
#4 Hard
Array Binary Search
Amazon Google Apple Goldman Sachs

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.

Key insight: Always binary search the shorter array to ensure O(log(min(m,n))). The partition index of the second array is derived from the first: j = (m+n+1)//2 - i. Handle edge cases with -infinity and +infinity sentinels.
Time: O(log(min(m,n)))Space: O(1)
21
Merge K Sorted Lists
#23 Hard
Linked List Heap
Amazon Meta Microsoft

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.

Key insight: The min-heap always contains at most k elements (one per list), so each push/pop is O(log k). With n total nodes, the overall time is O(n log k) — much better than the naive O(n * k) approach.
Time: O(n log k)Space: O(k)
22
Word Ladder
#127 Hard
Graph BFS String
Amazon Meta Google

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.

Key insight: Instead of comparing all word pairs (O(n^2 * L)), create a pattern map: for each word, generate all patterns with one wildcard character. Words sharing a pattern are neighbors. Bidirectional BFS can further halve the search space.
Time: O(n * L^2)Space: O(n * L)
23
Alien Dictionary
#269 Hard
Graph Topological Sort String
Meta Google Airbnb Bloomberg

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

Key insight: Only the first differing character between adjacent words gives you an ordering edge. Don't compare non-adjacent words — the transitive ordering is captured by the graph. Watch for the edge case where a longer word appears before its prefix.
Time: O(C)Space: O(U + E)
24
Edit Distance
#72 Hard
Dynamic Programming String
Amazon Google Microsoft

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.

Key insight: Each cell depends only on three neighbors: top, left, and diagonal. You can optimize space from O(m*n) to O(min(m,n)) using two rolling arrays, since you only need the previous row.
Time: O(m * n)Space: O(m * n)
25
Serialize and Deserialize Binary Tree
#297 Hard
Tree Design
Amazon Meta Google LinkedIn

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.

Key insight: You must record null children explicitly. Without null markers, the tree structure is ambiguous — different trees can produce the same preorder sequence. BFS (level-order) serialization also works but preorder is simpler to implement recursively.
Time: O(n)Space: O(n)
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

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 →