LeetCode 75 · Hard

Hard Problems

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.

Problems: 10
Difficulty: Hard
Topics: Advanced DP · Sliding Window · Graphs · Design
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.
H 01 Hard Arrays Two Pointers
Trapping Rain Water
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].
Test Cases
trap([0,1,0,2,1,0,1,3,2,1,2,1]) → 6 trap([4,2,0,3,2,5]) → 9 trap([1,0,1]) → 1 trap([3,0,0,2,0,4]) → 10
two pointers from endsleft_max / right_max O(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 def trap(height: List[int]) -> int: left, right = 0, len(height) - 1 left_max = right_max = 0 water = 0 while left < right: if height[left] < height[right]: if height[left] >= left_max: left_max = height[left] # new max on left side else: water += left_max - height[left] # trapped water here left += 1 else: if height[right] >= right_max: right_max = height[right] else: water += right_max - height[right] right -= 1 return 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 02 Hard Arrays Binary 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))).
Test Cases
findMedianSortedArrays([1,3], [2]) → 2.0 findMedianSortedArrays([1,2], [3,4]) → 2.5 # merged [1,2,3,4], median=(2+3)/2 findMedianSortedArrays([0,0], [0,0]) → 0.0 findMedianSortedArrays([], [1]) → 1.0
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 def findMedianSortedArrays(nums1: List[int], nums2: List[int]) -> float: # Ensure nums1 is the shorter array (binary search on smaller space) if len(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 > 0 else float('-inf') r1 = nums1[mid1] if mid1 < m else float('inf') l2 = nums2[mid2 - 1] if mid2 > 0 else float('-inf') r2 = nums2[mid2] if mid2 < n else float('inf') if l1 <= r2 and l2 <= r1: # Correct partition found if (m + n) % 2 == 1: return min(r1, r2) return (max(l1, l2) + min(r1, r2)) / 2 elif l1 > r2: right = mid1 - 1 # too many from nums1 on left else: 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 03 Hard Linked Lists Heap
Merge k Sorted Lists
Given an array of k linked lists, each sorted in ascending order, merge them all into one sorted linked list.
Test Cases
lists = [1→4→5, 1→3→4, 2→6] mergeKLists(lists) → 1→1→2→3→4→4→5→6 lists = [] → [] lists = [[]] → []
min-heap with (val, idx, node)heapq dummy head
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 class ListNode: def __init__(self, val=0, next=None): self.val = val; self.next = next def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]: heap = [] # Initialize heap with the first node of each list for i, node in enumerate(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 04 Hard Strings Sliding 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 counters shrink 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 def minWindow(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 = 0 for right, ch in enumerate(s): window[ch] = window.get(ch, 0) + 1 if ch in need and window[ch] == need[ch]: have += 1 # one more char type fully satisfied while have == total: # window is valid — try to shrink if right - left + 1 < result_len: result = [left, right] result_len = right - left + 1 # Remove leftmost character window[s[left]] -= 1 if s[left] in need and window[s[left]] < need[s[left]]: have -= 1 left += 1 return 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 05 Hard Arrays Sliding Window Deque
Sliding Window Maximum
Given an array nums and window size k, return the maximum of each sliding window of size k.
Test Cases
maxSlidingWindow([1,3,-1,-3,5,3,6,7], k=3) → [3,3,5,5,6,7] maxSlidingWindow([1], k=1) → [1] maxSlidingWindow([1,-1], k=1) → [1,-1]
monotonic dequemaintain max at front remove 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 def maxSlidingWindow(nums: List[int], k: int) -> List[int]: dq = deque() # stores indices; front = index of window max result = [] for i, num in enumerate(nums): # 1. Remove front if it's outside the current window while dq and dq[0] < i - k + 1: dq.popleft() # 2. Remove from back all indices with smaller values while 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 06 Hard Graphs BFS
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 map visited 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 def ladderLength(beginWord: str, endWord: str, wordList: List[str]) -> int: word_set = set(wordList) if endWord not in word_set: return 0 # Build pattern → list of words mapping patterns: dict = defaultdict(list) for word in word_set | {beginWord}: for i in range(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 in range(len(word)): pattern = word[:i] + '*' + word[i + 1:] for neighbor in patterns[pattern]: if neighbor == endWord: return steps + 1 if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, steps + 1)) return 0
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 07 Hard Trees DFS
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 tracking max(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 class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val; self.left = left; self.right = right def maxPathSum(root: Optional[TreeNode]) -> int: max_sum = [float('-inf')] # use list to allow mutation inside closure def dfs(node: Optional[TreeNode]) -> int: if not node: return 0 # 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 08 Hard Arrays Greedy
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 def candy(ratings: List[int]) -> int: n = len(ratings) candies = [1] * n # everyone gets at least 1 # Left pass: satisfy left-neighbor constraint for i in range(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 in range(n - 2, -1, -1): if ratings[i] > ratings[i + 1]: candies[i] = max(candies[i], candies[i + 1] + 1) return sum(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 09 Hard Design Hash Map Linked 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.
Test Cases
cache = LFUCache(2) cache.put(1, 1); cache.put(2, 2) cache.get(1) → 1 (freq[1]=2, freq[2]=1) cache.put(3, 3) # evicts key 2 (LFU, freq=1) cache.get(2) → -1 (evicted) cache.get(3) → 3 cache.put(4, 4) # evicts key 3 (freq=1, LRU among min_freq) cache.get(1) → 1 cache.get(3) → -1 cache.get(4) → 4
freq → OrderedDict of keys min_freq tracking O(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 class LFUCache: 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] += 1 del self.freq_keys[freq][key] # remove from old bucket if 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 bucket def get(self, key: int) -> int: if key not in self.key_val: return -1 self._update(key) return self.key_val[key] def put(self, key: int, value: int) -> None: if self.capacity <= 0: return if key in self.key_val: self.key_val[key] = value self._update(key) else: if len(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 10 Hard Stacks Strings
Basic Calculator
Implement a basic calculator to evaluate a string expression containing +, -, parentheses, and spaces. No multiplication or division.
Test Cases
calculate("1 + 1") → 2 calculate(" 2-1 + 2 ") → 3 calculate("(1+(4+5+2)-3)+(6+8)") → 23 calculate("- (3 + (4 - 2))") → -5
stack for parenthesessign tracking multi-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
def calculate(s: str) -> int: stack = [] num = 0 sign = 1 # current sign: +1 or -1 result = 0 for ch in s: if ch.isdigit(): num = num * 10 + int(ch) # accumulate multi-digit number elif ch in '+-': result += sign * num # apply accumulated number num = 0 sign = 1 if ch == '+' else -1 elif ch == '(': # Push current state; start fresh inside parentheses stack.append((result, sign)) result = 0 sign = 1 elif 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 number return 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.
← Medium Part 2 ↑ LeetCode 75 Home