These problems require combining multiple patterns or applying non-obvious insights.
Understanding the "why" matters more than memorizing the code.
Work through the hints carefully before revealing.
Hard problem strategy: First, solve it in O(n²) or O(n log n). Then ask: "What information am I recomputing? Can I precompute it or maintain it as I scan?"
The optimal solution is often just a cleverer data structure or a two-pointer/deque trick on top of the brute force.
Given an elevation map represented by array height, compute how much water can be trapped after raining.
Water at position i = min(max_left[i], max_right[i]) - height[i].
two pointers from endsleft_max / right_maxO(1) space optimization
Water at index i is limited by the shorter of (max height to its left) and (max height to its right).
With two pointers from each end: whichever side has the smaller max height — process that side.
On the smaller side, you already know the limiting factor (the other side is guaranteed to be at least as tall).
Solution
from typing import List
deftrap(height: List[int]) -> int:
left, right = 0, len(height) - 1
left_max = right_max = 0
water = 0while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left] # new max on left sideelse:
water += left_max - height[left] # trapped water here
left += 1else:
if height[right] >= right_max:
right_max = height[right]
else:
water += right_max - height[right]
right -= 1return water
Key insight: When height[left] < height[right], we know that whatever the right_max is, it's at least height[right] ≥ height[left]. So the water at left is determined solely by left_max. We can safely process left.
Complexity
Time: O(n) — single pass with two pointers. Space: O(1) — no extra arrays.
Alternative Approaches
Precompute arrays: Build left_max[] and right_max[] in two passes, then compute water in a third pass — O(n) time, O(n) space. Easier to understand. Stack: Use a monotonic stack to find "valleys" — O(n) time and space. Less intuitive.
H 02HardArraysBinary Search
Median of Two Sorted Arrays
Given two sorted arrays nums1 and nums2, return the median of the combined sorted array. Solve in O(log(min(m,n))).
binary search on partitionhalf-length split±infinity guards
Think of partitioning both arrays such that all elements on the left ≤ all elements on the right. Binary search on the partition position in the shorter array. The partition is valid when max(left of nums1, left of nums2) ≤ min(right of nums1, right of nums2).
Solution
from typing import List
deffindMedianSortedArrays(nums1: List[int], nums2: List[int]) -> float:
# Ensure nums1 is the shorter array (binary search on smaller space)iflen(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
half = (m + n) // 2
left, right = 0, m
while left <= right:
mid1 = (left + right) // 2# partition in nums1
mid2 = half - mid1 # partition in nums2# Values at partition boundaries (use ±inf for out-of-bounds)
l1 = nums1[mid1 - 1] if mid1 > 0elsefloat('-inf')
r1 = nums1[mid1] if mid1 < m elsefloat('inf')
l2 = nums2[mid2 - 1] if mid2 > 0elsefloat('-inf')
r2 = nums2[mid2] if mid2 < n elsefloat('inf')
if l1 <= r2 and l2 <= r1:
# Correct partition foundif (m + n) % 2 == 1:
returnmin(r1, r2)
return (max(l1, l2) + min(r1, r2)) / 2elif l1 > r2:
right = mid1 - 1# too many from nums1 on leftelse:
left = mid1 + 1# too few from nums1 on left
Key insight: We want to find a cut in each array such that the left halves contain exactly (m+n)//2 elements total, and all left elements ≤ all right elements. Binary search finds this cut. The boundary guards (±inf) handle edge cases when the cut is at array boundaries.
Complexity
Time: O(log(min(m,n))) — binary search on the shorter array. Space: O(1).
Alternative Approach
Merge then find middle: Merge both sorted arrays (O(m+n)), take middle element(s). O(m+n) time and space. Correct but doesn't meet the O(log n) requirement.
H 03HardLinked ListsHeap
Merge k Sorted Lists
Given an array of k linked lists, each sorted in ascending order, merge them all into one sorted linked list.
Use a min-heap containing the current head of each list. Always pop the smallest. When you pop a node, push its next node (if any). This gives you O(N log k) — much better than merging one by one.
Solution
import heapq
from typing import List, Optional
classListNode:
def__init__(self, val=0, next=None):
self.val = val; self.next = next
defmergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
heap = []
# Initialize heap with the first node of each listfor i, node inenumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node)) # i breaks ties
dummy = ListNode(0)
curr = dummy
while heap:
val, i, node = heapq.heappop(heap)
curr.next = node
curr = curr.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
Key idea: The heap always gives us the global minimum in O(log k).
We include the list index i as a tiebreaker to avoid comparing ListNode objects (which aren't comparable in Python).
Complexity
Time: O(N log k) where N = total nodes, k = number of lists. Each node is pushed/popped once in O(log k). Space: O(k) — heap holds at most k elements.
Alternative Approach
Divide and Conquer: Merge pairs of lists, then pairs of merged lists, etc. — O(N log k) time, O(1) extra space. Same complexity but avoids the heap. Elegant recursion.
H 04HardStringsSliding Window
Minimum Window Substring
Given strings s and t, return the minimum window in s that contains all characters of t.
Return "" if no such window exists.
Test Cases
minWindow("ADOBECODEBANC", "ABC") → "BANC"
minWindow("a", "a") → "a"
minWindow("a", "aa") → "" # only one 'a' in s
minWindow("ab", "b") → "b"
sliding windowhave/need countersshrink from left when valid
Expand right until the window contains all of t. Then shrink from left to minimize the window, keeping track of the shortest valid window found. Use "have" (satisfied character types) and "need" (total unique characters in t) counters to detect validity.
Solution
from collections import Counter
defminWindow(s: str, t: str) -> str:
if not t:
return""
need = Counter(t) # required char counts
window = {} # current window char counts
have, total = 0, len(need) # total = unique chars in t
result, result_len = [-1, -1], float('inf')
left = 0for right, ch inenumerate(s):
window[ch] = window.get(ch, 0) + 1if ch in need and window[ch] == need[ch]:
have += 1# one more char type fully satisfiedwhile have == total: # window is valid — try to shrinkif right - left + 1 < result_len:
result = [left, right]
result_len = right - left + 1# Remove leftmost character
window[s[left]] -= 1if s[left] in need and window[s[left]] < need[s[left]]:
have -= 1
left += 1return s[result[0]:result[1] + 1] if result_len != float('inf') else""
Key idea: The have counter tracks how many character types in t are fully satisfied in the current window.
When have == total, the window is valid. We record it and shrink from the left to find a smaller valid window.
Complexity
Time: O(|s| + |t|) — right visits each character once, left visits each at most once. Space: O(|s| + |t|) — window and need hash maps.
H 05HardArraysSliding WindowDeque
Sliding Window Maximum
Given an array nums and window size k, return the maximum of each sliding window of size k.
monotonic dequemaintain max at frontremove stale elements
Use a deque of indices, maintaining a decreasing monotonic property: the front is always the index of the current window's maximum.
When adding a new element: (1) remove from front if out of window, (2) remove from back all indices with smaller values (they can never be max while current element is in the window).
Solution
from collections import deque
from typing import List
defmaxSlidingWindow(nums: List[int], k: int) -> List[int]:
dq = deque() # stores indices; front = index of window max
result = []
for i, num inenumerate(nums):
# 1. Remove front if it's outside the current windowwhile dq and dq[0] < i - k + 1:
dq.popleft()
# 2. Remove from back all indices with smaller valueswhile dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
# 3. Window is fully formed: record the max (front of deque)if i >= k - 1:
result.append(nums[dq[0]])
return result
Key insight: The deque maintains a decreasing sequence of values.
Any element smaller than the current new element can never be the maximum while the new element is in the window (it's to the left AND smaller). So we pop it.
The front of the deque is always the index of the current window's maximum.
Complexity
Time: O(n) — each element is pushed and popped at most once. Space: O(k) — deque holds at most k indices.
Alternative Approach
Heap (priority queue): Push (val, idx) pairs. Pop stale elements (out of window) before reading max. O(n log n) — slower than the deque approach.
Sparse table: O(n log n) preprocessing, O(1) queries — overkill for this problem.
H 06HardGraphsBFS
Word Ladder
Given beginWord, endWord, and a wordList, find the shortest transformation sequence from beginWord to endWord, changing one letter at a time.
Each intermediate word must be in wordList. Return the sequence length (0 if impossible).
Test Cases
ladderLength("hit", "cog", ["hot","dot","dog","lot","log","cog"]) → 5
# hit → hot → dot → dog → cog
ladderLength("hit", "cog", ["hot","dot","dog","lot","log"]) → 0
# "cog" not in wordList
BFS shortest pathwildcard pattern mapvisited set
BFS finds shortest path. The trick: instead of checking all word pairs (O(N²×M)), pre-build a pattern map. For "hot", patterns are "*ot", "h*t", "ho*". Two words are neighbors if they share a pattern. This makes neighbor lookup fast.
Solution
from collections import deque, defaultdict
from typing import List
defladderLength(beginWord: str, endWord: str, wordList: List[str]) -> int:
word_set = set(wordList)
if endWord not in word_set:
return0# Build pattern → list of words mapping
patterns: dict = defaultdict(list)
for word in word_set | {beginWord}:
for i inrange(len(word)):
pattern = word[:i] + '*' + word[i + 1:]
patterns[pattern].append(word)
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
for i inrange(len(word)):
pattern = word[:i] + '*' + word[i + 1:]
for neighbor in patterns[pattern]:
if neighbor == endWord:
return steps + 1if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, steps + 1))
return0
Complexity
Time: O(M² × N) where M = word length, N = wordList size. Pattern building: O(N × M). BFS: O(N × M) nodes × O(M) pattern generation per node. Space: O(M² × N) — pattern map.
Alternative Approach
Bidirectional BFS: Expand from both beginWord and endWord simultaneously. Meets in the middle, cutting the search space roughly in half in practice. Same asymptotic complexity but significantly faster in practice.
H 07HardTreesDFS
Binary Tree Maximum Path Sum
A path in a binary tree is any sequence of nodes from some starting node to any node in the tree along parent-child connections. A node can appear at most once. Find the path with the maximum sum.
Test Cases
tree: [1,2,3] → 6 # path: 2→1→3
tree: [-10,9,20,None,None,15,7] → 42 # path: 15→20→7
tree: [-3] → -3 # must include at least one node
tree: [2,-1] → 2
post-order DFSglobal max trackingmax(child, 0) to ignore negatives
At each node, the maximum path through it uses: node.val + max(left_gain, 0) + max(right_gain, 0). But the path returned UP to the parent can only go one direction (you can't turn twice). Use a global variable to track the best path seen so far.
Solution
from typing import Optional
classTreeNode:
def__init__(self, val=0, left=None, right=None):
self.val = val; self.left = left; self.right = right
defmaxPathSum(root: Optional[TreeNode]) -> int:
max_sum = [float('-inf')] # use list to allow mutation inside closuredefdfs(node: Optional[TreeNode]) -> int:
if not node:
return0# Ignore subtrees with negative contribution (use 0 instead)
left = max(dfs(node.left), 0)
right = max(dfs(node.right), 0)
# Path through this node (can use both children)
max_sum[0] = max(max_sum[0], node.val + left + right)
# Return best one-sided path (can only extend in one direction upward)return node.val + max(left, right)
dfs(root)
return max_sum[0]
Key insight: The path that passes through a node can use both subtrees (going left→node→right). But the path we return to the node's parent can only extend in ONE direction (we can't pass through the current node going both ways to the parent). That's why we return node.val + max(left, right) but update the global max with node.val + left + right.
Complexity
Time: O(n) — visit every node exactly once in post-order. Space: O(h) — recursion stack depth equals tree height. O(log n) for balanced, O(n) for skewed.
H 08HardArraysGreedy
Candy
n children stand in a line. Each has a rating. Give each child at least 1 candy. Children with a higher rating than their immediate neighbor must get more candies. Return the minimum total candies needed.
Test Cases
candy([1,0,2]) → 5 # [2,1,2]
candy([1,2,2]) → 4 # [1,2,1] — equal ratings: same is fine
candy([1,3,2,2,1]) → 7 # [1,3,2,1,2] → wait: [1,2,1,1,2] sum=7
two-pass greedyleft pass + right pass
Two passes: Left→right: if ratings[i] > ratings[i-1], give child i one more than child i-1. Right→left: if ratings[i] > ratings[i+1], child i needs at least (candies[i+1]+1). Take the max of both passes.
Solution
from typing import List
defcandy(ratings: List[int]) -> int:
n = len(ratings)
candies = [1] * n # everyone gets at least 1# Left pass: satisfy left-neighbor constraintfor i inrange(1, n):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1# Right pass: satisfy right-neighbor constraint (take max with left pass)for i inrange(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
candies[i] = max(candies[i], candies[i + 1] + 1)
returnsum(candies)
Key insight: One pass can only satisfy constraints in one direction.
The two-pass approach ensures both directions are satisfied.
We take the max of both passes at each position because a child might need more candies to satisfy the left-neighbor constraint than the right-neighbor constraint.
Complexity
Time: O(n) — two linear passes. Space: O(n) — candies array.
H 09HardDesignHash MapLinked Lists
LFU Cache
Design a data structure implementing Least Frequently Used (LFU) cache eviction.
Implement get(key) and put(key, value) both in O(1).
When evicting, remove the least frequently used item. On tie, remove the least recently used among them.
freq → OrderedDict of keysmin_freq trackingO(1) all ops
Need 3 data structures: (1) key→value map, (2) key→frequency map, (3) frequency→OrderedDict of keys (LRU within same frequency). Track min_freq. On get/put, increment freq and move key to the next frequency bucket. Evict from freq_keys[min_freq].
Solution
from collections import defaultdict, OrderedDict
classLFUCache:
def__init__(self, capacity: int):
self.capacity = capacity
self.min_freq = 0
self.key_val = {} # key → value
self.key_freq = {} # key → frequency
self.freq_keys = defaultdict(OrderedDict) # freq → {key: None}def_update(self, key: int) -> None:
freq = self.key_freq[key]
self.key_freq[key] += 1del self.freq_keys[freq][key] # remove from old bucketif not self.freq_keys[freq] and freq == self.min_freq:
self.min_freq += 1# min_freq bucket is now empty
self.freq_keys[freq + 1][key] = None# add to new bucketdefget(self, key: int) -> int:
if key not in self.key_val:
return -1
self._update(key)
return self.key_val[key]
defput(self, key: int, value: int) -> None:
if self.capacity <= 0:
returnif key in self.key_val:
self.key_val[key] = value
self._update(key)
else:
iflen(self.key_val) >= self.capacity:
# Evict LFU (and LRU among LFU keys)
evict_key, _ = self.freq_keys[self.min_freq].popitem(last=False)
del self.key_val[evict_key]
del self.key_freq[evict_key]
self.key_val[key] = value
self.key_freq[key] = 1
self.freq_keys[1][key] = None
self.min_freq = 1
Key insight:freq_keys[f] is an OrderedDict where order = access order (LRU). When evicting, we pop from the front (oldest/LRU) of the min_freq bucket.
The min_freq tracker only needs to be reset to 1 when inserting a new key (any new key has frequency 1).
Complexity
Time: O(1) for all get and put operations. Space: O(capacity) — three hash structures, each holding at most capacity entries.
H 10HardStacksStrings
Basic Calculator
Implement a basic calculator to evaluate a string expression containing +, -, parentheses, and spaces. No multiplication or division.
stack for parenthesessign trackingmulti-digit numbers
When you see '(', push the current result and current sign onto the stack (to restore later). When you see ')', pop to get the result before this parenthesis and combine. Track the sign (+1 or -1) and accumulate digits into num before applying.
Solution
defcalculate(s: str) -> int:
stack = []
num = 0
sign = 1# current sign: +1 or -1
result = 0for ch in s:
if ch.isdigit():
num = num * 10 + int(ch) # accumulate multi-digit numberelif ch in'+-':
result += sign * num # apply accumulated number
num = 0
sign = 1if ch == '+'else -1elif ch == '(':
# Push current state; start fresh inside parentheses
stack.append((result, sign))
result = 0
sign = 1elif ch == ')':
result += sign * num
num = 0
prev_result, prev_sign = stack.pop()
result = prev_result + prev_sign * result # apply outer sign# spaces: do nothing (implicit)
result += sign * num # don't forget the last numberreturn result
Key idea: When we open a parenthesis, we "save" the current running result and sign, then reset. When we close a parenthesis, we restore and multiply by the saved sign.
The sign variable always holds the sign of the next number to be added.
Multi-digit numbers are accumulated with num = num * 10 + int(ch).
Complexity
Time: O(n) — single pass through the string. Space: O(n) — stack depth equals max parenthesis nesting level.
Alternative Approach
Recursive descent parser: Formally parse the grammar with a recursive approach. More structured for complex calculators (with ×, ÷, unary ops), but overkill for this problem.
The stack-based approach above handles all cases cleanly and is preferred in interviews.