Sliding window, binary search, graph BFS/DFS, two pointers, DP, and matrix problems.
These are the core patterns that appear in the majority of real interviews.
Tip: For Medium problems, the brute force usually exists — but interviewers want the optimal approach.
Always ask yourself: "What if n were 10 million? Would my approach still work?"
That question usually points you toward the right data structure or algorithm.
Design a data structure that follows the Least Recently Used (LRU) cache eviction policy.
Implement get(key) returning the value (-1 if not found) and
put(key, value) inserting or updating. Both must be O(1).
When capacity is exceeded, evict the least recently used item.
OrderedDictmove_to_endpopitem(last=False)O(1) all ops
You need O(1) lookup (hash map) and O(1) eviction of the LRU item (ordered sequence).
Python's OrderedDict is a doubly-linked list + hash map combined.
It has a move_to_end(key) method — what would "most recently used" mean in terms of the order?
Solution
from collections import OrderedDict
classLRUCache:
def__init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict() # maintains insertion/access orderdefget(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key) # mark as most recently usedreturn self.cache[key]
defput(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key) # update moves to MRU position
self.cache[key] = value
iflen(self.cache) > self.capacity:
self.cache.popitem(last=False) # pop LRU (front of ordered dict)
Key idea:OrderedDict is a doubly-linked list under the hood.
We keep the "least recently used" item at the front (left) and the "most recently used" at the back (right).
move_to_end(key) is O(1). popitem(last=False) evicts from the front — O(1).
Both get and put are O(1).
Complexity
Time: O(1) for both get and put — hash map lookup + linked list pointer updates. Space: O(capacity) — stores at most capacity items.
Alternative Approach
Manual doubly linked list + dict: Build your own DLL with prev/next pointers.
Same complexity, more code — but demonstrates deeper understanding. Preferred in Java/C++ interviews
where LinkedHashMap might not be "obvious". In Python, OrderedDict is the clean answer.
M 02MediumArraysSorting
Merge Intervals
Given an array of intervals [[start, end], ...], merge all overlapping intervals
and return a list of non-overlapping intervals that cover all intervals in the input.
sort by startextend vs appendinterval overlap check
Sort intervals by start time. Then walk through: for each interval, does it overlap with the last merged interval?
Two intervals overlap when the new one's start ≤ the last one's end. When they overlap, you merge by extending the end.
Solution
from typing import List
defmerge(intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: x[0]) # sort by start time
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # overlaps with last merged
merged[-1][1] = max(merged[-1][1], end) # extend endelse:
merged.append([start, end]) # no overlap — add new intervalreturn merged
Complexity
Time: O(n log n) — dominated by sorting. The merge pass is O(n). Space: O(n) — output list can be up to n intervals.
Alternative Approach
If the input is already sorted, the sort step is skippable and you get O(n).
This is worth mentioning in interviews when the input arrives in sorted order.
M 03MediumStringsSliding Window
Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.
sliding windowhash map for last indexleft pointer jump
Use a sliding window [left, right]. Expand right one character at a time.
When you hit a duplicate, where should left jump to? Not just +1 from where it is — you should jump it to just past the previous occurrence of the duplicate character.
Solution
deflengthOfLongestSubstring(s: str) -> int:
char_idx = {} # maps char → most recent index seen
left = 0
max_len = 0for right, ch inenumerate(s):
# If char seen and its last index is inside our current windowif ch in char_idx and char_idx[ch] >= left:
left = char_idx[ch] + 1# jump left past the old occurrence
char_idx[ch] = right
max_len = max(max_len, right - left + 1)
return max_len
Key idea: The hash map stores the most recent index of each character.
When we see a duplicate inside our window, we move the left pointer past it.
The check char_idx[ch] >= left prevents us from jumping left backward when the duplicate is outside the window.
Complexity
Time: O(n) — right pointer visits each character once; left only moves right. Space: O(min(m, n)) where m is the charset size (26 for lowercase, 128 for ASCII). Effectively O(1) for fixed charsets.
M 04MediumGraphsDFSBFS
Number of Islands
Given a 2D grid of '1's (land) and '0's (water), count the number of islands.
An island is surrounded by water and formed by connecting adjacent land cells horizontally or vertically.
DFS flood fillmark visited by mutation4-directional search
Scan the grid. Every time you find a '1' that hasn't been visited, you found a new island — increment the count.
Then "sink" the entire island using DFS: recursively mark all connected '1's as '0' (visited).
That way they won't be counted again.
Solution
from typing import List
defnumIslands(grid: List[List[str]]) -> int:
if not grid:
return0
rows, cols = len(grid), len(grid[0])
count = 0defdfs(r: int, c: int) -> None:
# Out of bounds or water — stopif r < 0or r >= rows or c < 0or c >= cols or grid[r][c] == '0':
return
grid[r][c] = '0'# sink this land cell (mark visited)dfs(r + 1, c); dfs(r - 1, c)
dfs(r, c + 1); dfs(r, c - 1)
for r inrange(rows):
for c inrange(cols):
if grid[r][c] == '1':
dfs(r, c) # sink the whole island
count += 1# this was a new islandreturn count
Key idea: "Flood fill" — when we find land, we immediately sink the entire island
by marking all connected cells as water ('0'). This avoids a separate visited set.
Note: this mutates the input grid. If the input must be preserved, use a separate visited set.
Complexity
Time: O(m × n) — each cell is visited at most twice (once in the scan, once in DFS). Space: O(m × n) — recursion stack depth in the worst case (one giant island).
Alternative Approach
BFS: Use a queue instead of recursion — avoids Python's recursion limit for huge grids. Same complexity, but iterative. Union-Find: Connect adjacent '1' cells using disjoint sets. Count distinct components. Elegant for dynamic grids.
M 05MediumArraysStringsHash Map
Group Anagrams
Given an array of strings strs, group the anagrams together.
Return the groups in any order.
defaultdict(list)sorted string as keygrouping pattern
Anagrams have the same characters with the same counts.
What's a way to get a consistent "fingerprint" for a string that all its anagrams share?
(Sorted characters work — all anagrams sort to the same string.)
Solution
from collections import defaultdict
from typing import List
defgroupAnagrams(strs: List[str]) -> List[List[str]]:
groups: dict = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # anagram fingerprint: sorted chars
groups[key].append(s)
returnlist(groups.values())
Key idea: Sorting the characters of a string produces a canonical form — all anagrams produce the same sorted string.
We use this as the hash map key. We use tuple(sorted(s)) because lists are not hashable.
Complexity
Time: O(n × k log k) where n = number of strings, k = max string length (sorting each string). Space: O(n × k) — storing all strings in the groups.
Alternative Approach
Character count key: Instead of sorting, build a tuple of 26 character counts.
Key computation becomes O(k) instead of O(k log k) — faster for long strings.
key = tuple(Counter(s)[c] for c in 'abcdefghijklmnopqrstuvwxyz')
M 06MediumStringsExpand Around Center
Longest Palindromic Substring
Given a string s, return the longest substring that is a palindrome.
Test Cases
longestPalindrome("babad") → "bab" or "aba" (both valid)
longestPalindrome("cbbd") → "bb"
longestPalindrome("a") → "a"
longestPalindrome("racecar") → "racecar"
expand around centerodd/even palindromestwo-pointer expansion
Every palindrome has a center. Odd-length palindromes have a single center character; even-length palindromes have two center characters.
Try expanding outward from every possible center. How many possible centers are there in a string of length n?
Solution
deflongestPalindrome(s: str) -> str:
result = ""defexpand(l: int, r: int) -> str:
# Expand outward while characters matchwhile l >= 0and r < len(s) and s[l] == s[r]:
l -= 1; r += 1return s[l + 1:r] # l+1 and r because we went one step too farfor i inrange(len(s)):
odd = expand(i, i) # odd-length: single center
even = expand(i, i + 1) # even-length: two center charsiflen(odd) > len(result): result = odd
iflen(even) > len(result): result = even
return result
Complexity
Time: O(n²) — n centers × O(n) expansion per center. Space: O(1) — no extra data structures (string slicing for return only).
Alternative Approach
Manacher's Algorithm: O(n) time using the symmetry of palindromes.
Quite complex to implement — worth knowing exists but rarely required in interviews.
The expand-around-center O(n²) approach is always accepted.
M 07MediumArraysHeap
Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements.
Order of results doesn't matter.
First count frequencies (Counter). Then you need the k largest frequencies.
heapq.nlargest does this in O(n log k) — better than sorting all n elements.
Solution
import heapq
from collections import Counter
from typing import List
deftopKFrequent(nums: List[int], k: int) -> List[int]:
count = Counter(nums)
# nlargest picks the k keys with the largest count.get valuesreturn heapq.nlargest(k, count.keys(), key=count.get)
# --- Bucket sort approach: O(n) time ---deftopKFrequentBucket(nums: List[int], k: int) -> List[int]:
count = Counter(nums)
# Bucket index = frequency. Max frequency ≤ n.
buckets = [[] for _ inrange(len(nums) + 1)]
for num, freq in count.items():
buckets[freq].append(num)
# Collect from highest-frequency buckets
result = []
for freq inrange(len(buckets) - 1, -1, -1):
result.extend(buckets[freq])
iflen(result) >= k:
return result[:k]
Complexity
Heap approach: Time O(n log k), Space O(n) Bucket sort: Time O(n), Space O(n) — optimal, but uses more memory on sparse frequencies.
M 08MediumArraysTwo Pointers
3Sum
Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]]
such that i != j != k and nums[i] + nums[j] + nums[k] == 0.
The solution set must not contain duplicate triplets.
sort firstfix one + two pointersduplicate skipping
Sort the array first. Fix the first element (nums[i]), then use two pointers on the rest to find pairs that sum to -nums[i].
The sorted order makes it easy to skip duplicate values and avoid duplicate triplets.
Solution
from typing import List
defthreeSum(nums: List[int]) -> List[List[int]]:
nums.sort()
result = []
for i inrange(len(nums) - 2):
if i > 0and nums[i] == nums[i - 1]:
continue# skip duplicate first elementsif nums[i] > 0:
break# sorted: all remaining sums will be positive
left, right = i + 1, len(nums) - 1while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]: left += 1while left < right and nums[right] == nums[right - 1]: right -= 1
left += 1; right -= 1elif s < 0:
left += 1else:
right -= 1return result
Complexity
Time: O(n²) — outer loop O(n) × inner two-pointer scan O(n). Space: O(n) — sorting is in-place; output list is O(n) in the worst case.
Alternative Approach
Hash set approach: For each pair (i,j), look up -(nums[i]+nums[j]) in a set — O(n²) time, O(n) space.
Harder to de-duplicate results. The sort + two-pointer approach handles duplicates more cleanly.
M 09MediumArraysPrefix Sum
Subarray Sum Equals K
Given an array nums and an integer k, return the total number of
subarrays whose elements sum to k. The array may contain negative numbers.
Test Cases
subarraySum([1,1,1], k=2) → 2 # [1,1] at [0,1] and [1,2]
subarraySum([1,2,3], k=3) → 2 # [3] and [1,2]
subarraySum([1,-1,1], k=1) → 3 # [1], [1,-1,1], [1] at index 2
subarraySum([-1,-1,1], k=-1) → 2
prefix sumhash map for countcomplement trick
A subarray sum from i to j equals prefix_sum[j] - prefix_sum[i-1].
So "does a subarray ending at j sum to k?" is equivalent to "does prefix_sum[j] - k appear earlier in the prefix sums?"
Use a hash map to count how many times each prefix sum has been seen.
Solution
from collections import defaultdict
from typing import List
defsubarraySum(nums: List[int], k: int) -> int:
prefix_count: dict = defaultdict(int)
prefix_count[0] = 1# empty prefix (sum=0) has been seen once
prefix_sum = 0
total = 0for num in nums:
prefix_sum += num
# How many earlier prefix sums satisfy: prefix_sum - earlier = k?
total += prefix_count[prefix_sum - k]
prefix_count[prefix_sum] += 1return total
Key idea: If prefix_sum[j] - prefix_sum[i] == k, then the subarray nums[i+1..j] sums to k.
Rearranging: prefix_sum[i] == prefix_sum[j] - k.
So for each j, count how many previous prefix sums equal prefix_sum[j] - k.
Initializing with prefix_count[0] = 1 handles subarrays starting from index 0.
Complexity
Time: O(n) — one pass through the array. Space: O(n) — hash map can hold up to n distinct prefix sums.
Alternative Approach
Brute force: O(n²) with nested loops computing all subarray sums.
Note: sliding window does NOT work here because of negative numbers — the window can't expand/shrink monotonically.
Prefix sum + hash map is the correct O(n) approach for negative numbers.
M 10MediumArraysBinary Search
Search in Rotated Sorted Array
Given an integer array nums sorted in ascending order then rotated at some pivot,
and a target value, return the index of target or -1 if not present. Solve in O(log n).
Even after rotation, one of the two halves is always sorted.
If nums[left] ≤ nums[mid], the left half is sorted. Otherwise the right half is sorted.
Check if the target falls within the sorted half. If yes, search there. Otherwise search the other half.
Solution
from typing import List
defsearch(nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1while left <= right:
mid = (left + right) // 2if nums[mid] == target:
return mid
# Left half is sortedif nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1# target in sorted left halfelse:
left = mid + 1# target in right half# Right half is sortedelse:
if nums[mid] < target <= nums[right]:
left = mid + 1# target in sorted right halfelse:
right = mid - 1# target in left halfreturn -1
Complexity
Time: O(log n) — standard binary search, halving the search space each step. Space: O(1) — no extra storage.
M 11MediumArraysDynamic Programming
Maximum Subarray (Kadane's Algorithm)
Given an integer array nums, find the subarray with the largest sum and return its sum.
The subarray must contain at least one element.
Test Cases
maxSubArray([-2,1,-3,4,-1,2,1,-5,4]) → 6 # [4,-1,2,1]
maxSubArray([1]) → 1
maxSubArray([5,4,-1,7,8]) → 23 # entire array
maxSubArray([-1,-2,-3]) → -1 # must pick at least one
Kadane's algorithmrunning sumreset when negative
For each element, ask: "Is it better to extend the previous subarray, or start fresh from here?"
If the running sum becomes negative, drop it and start fresh — a negative prefix only hurts future sums.
Solution
from typing import List
defmaxSubArray(nums: List[int]) -> int:
max_sum = nums[0]
curr_sum = nums[0]
for num in nums[1:]:
# Either extend the current subarray, or start fresh from num
curr_sum = max(num, curr_sum + num)
max_sum = max(max_sum, curr_sum)
return max_sum
Complexity
Time: O(n) — single pass, O(1) work per element. Space: O(1) — just two variables.
Alternative Approach
DP array:dp[i] = max(nums[i], dp[i-1] + nums[i]) — same logic but O(n) space. No benefit. Divide and Conquer: O(n log n) time — elegant but slower than Kadane's. Know it exists.
M 12MediumArraysMatrix
Rotate Image
Given an n×n matrix, rotate it 90 degrees clockwise in-place.
A 90° clockwise rotation = transpose + then reverse each row.
Transpose means flipping across the diagonal: matrix[i][j] ↔ matrix[j][i].
Try it on a 3×3 example mentally first.
Solution
from typing import List
defrotate(matrix: List[List[int]]) -> None:
n = len(matrix)
# Step 1: Transpose — swap matrix[i][j] with matrix[j][i]for i inrange(n):
for j inrange(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Step 2: Reverse each rowfor row in matrix:
row.reverse()
Complexity
Time: O(n²) — visit every cell once for transpose, once for reverse. Space: O(1) — all operations in-place.
Alternative Approach
Counter-clockwise (90° CCW): Transpose then reverse each column (or reverse rows then transpose). 4-cell cycle rotation: Rotate 4 corners at a time in a cycle — more complex but also O(1) space.
M 13MediumArraysMatrix
Spiral Matrix
Given an m×n matrix, return all elements in spiral order (clockwise from top-left).
Track four boundaries: top, bottom, left, right. Each full loop of the spiral shrinks all four boundaries by 1.
Walk: left→right (top row), top→bottom (right col), right→left (bottom row), bottom→top (left col).
Don't forget to shrink each boundary after processing it.
Solution
from typing import List
defspiralOrder(matrix: List[List[int]]) -> List[int]:
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1while top <= bottom and left <= right:
# → top row: left to rightfor c inrange(left, right + 1):
result.append(matrix[top][c])
top += 1# ↓ right col: top to bottomfor r inrange(top, bottom + 1):
result.append(matrix[r][right])
right -= 1if top <= bottom: # guard: might have exhausted rows# ← bottom row: right to leftfor c inrange(right, left - 1, -1):
result.append(matrix[bottom][c])
bottom -= 1if left <= right: # guard: might have exhausted cols# ↑ left col: bottom to topfor r inrange(bottom, top - 1, -1):
result.append(matrix[r][left])
left += 1return result
Complexity
Time: O(m × n) — every cell is visited exactly once. Space: O(1) — excluding the output array.
M 14MediumLinked ListsMath
Add Two Numbers
Two non-empty linked lists represent two non-negative integers stored in reverse order.
Each node contains a single digit. Add the two numbers and return the sum as a linked list.
carry propagationdummy headdivmod()linked list construction
Simulate grade-school addition digit by digit. Track the carry.
The loop should continue as long as either list has digits OR there's a carry remaining.
Use divmod(val, 10) to get the carry and the digit to store.
Solution
from typing import Optional
classListNode:
def__init__(self, val=0, next=None):
self.val = val; self.next = next
defaddTwoNumbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0)
curr = dummy
carry = 0while l1 or l2 or carry:
val = carry
if l1: val += l1.val; l1 = l1.next
if l2: val += l2.val; l2 = l2.next
carry, digit = divmod(val, 10) # carry = val//10, digit = val%10
curr.next = ListNode(digit)
curr = curr.next
return dummy.next
Complexity
Time: O(max(m, n)) where m and n are the lengths of the two lists. Space: O(max(m, n)) — the result list can be at most max(m,n)+1 nodes long.
M 15MediumArraysHeap
Kth Largest Element in an Array
Given an integer array nums and an integer k, return the kth largest element.
Note: kth largest is not kth distinct.
Maintain a min-heap of size k. If the heap has k elements and you see something larger than the minimum, replace it.
The top of the heap (the minimum of the k largest elements) is your answer.
Solution
import heapq
from typing import List
deffindKthLargest(nums: List[int], k: int) -> int:
# Min-heap of size k — the heap top is always the kth largest seen so far
heap = nums[:k]
heapq.heapify(heap)
for num in nums[k:]:
if num > heap[0]:
heapq.heapreplace(heap, num) # pop min, push num in O(log k)return heap[0] # smallest of the k largest = kth largest overall
Complexity
Time: O(n log k) — each element processed in O(log k) heap ops. Space: O(k) — only the heap of size k.
Alternative Approach
Sort:sorted(nums)[-k] — O(n log n), clean one-liner. Accepted in interviews. Quickselect: Average O(n), worst case O(n²). Partition around a pivot like Quicksort but only recurse into one half.
Best theoretical average, but the heap approach is more predictable and simpler to code correctly.
M 16MediumRecursionBacktracking
Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
At each step, you can add '(' if you have open parens remaining. You can add ')' only if the number of open parens placed so far exceeds the number of close parens placed.
Base case: when the string has length 2n, add it to results.
Time: O(4ⁿ / √n) — this is the nth Catalan number. Each valid sequence is O(n) to construct. Space: O(n) — recursion depth is at most 2n (the length of the string being built).
M 17MediumArraysBFS
Rotting Oranges
In a grid, 0 = empty, 1 = fresh orange, 2 = rotten orange.
Every minute, any fresh orange adjacent (4-directional) to a rotten one becomes rotten.
Return the minimum minutes until no fresh oranges remain, or -1 if impossible.
Start BFS from ALL rotten oranges simultaneously (multi-source BFS).
Each BFS level = one minute. Track how many fresh oranges remain. If any are left when BFS ends, return -1.
Solution
from collections import deque
from typing import List
deforangesRotting(grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0# Seed queue with all initially rotten oranges; count fresh onesfor r inrange(rows):
for c inrange(cols):
if grid[r][c] == 2: queue.append((r, c, 0))
elif grid[r][c] == 1: fresh += 1if fresh == 0:
return0
minutes = 0while queue:
r, c, minutes = queue.popleft()
for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
nr, nc = r + dr, c + dc
if0 <= nr < rows and0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc, minutes + 1))
return minutes if fresh == 0else -1
Complexity
Time: O(m × n) — each cell is enqueued/processed at most once. Space: O(m × n) — queue can hold all cells in the worst case.
M 18MediumArraysBinary Search
Find First and Last Position of Element in Sorted Array
Given a sorted integer array nums and a target, return the starting and ending positions of target.
Return [-1, -1] if target is not found. Solve in O(log n).
Run binary search twice: once to find the leftmost position of target, once to find the rightmost.
Python's bisect module does exactly this. bisect_left gives the first position, bisect_right gives one past the last.
Solution
import bisect
from typing import List
defsearchRange(nums: List[int], target: int) -> List[int]:
left = bisect.bisect_left(nums, target)
# Check if target actually exists at this positionif left == len(nums) or nums[left] != target:
return [-1, -1]
right = bisect.bisect_right(nums, target) - 1return [left, right]
Complexity
Time: O(log n) — two binary searches, each O(log n). Space: O(1).
M 19MediumArraysDynamic Programming
House Robber
Given an array of non-negative integers nums representing the amount of money in each house,
return the maximum amount you can rob without robbing two adjacent houses.
Test Cases
rob([1,2,3,1]) → 4 # rob house 1 (1) + house 3 (3) = 4
rob([2,7,9,3,1]) → 12 # rob house 1 (2) + house 3 (9) + house 5 (1) = 12
rob([0]) → 0
rob([1,2]) → 2
DP rolling variablesno adjacent constraintmax(skip, take)
At each house, you decide: rob it (get its value + what you had 2 houses ago) or skip it (keep what you had 1 house ago).
dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
Do you really need an array, or just two variables?
Solution
from typing import List
defrob(nums: List[int]) -> int:
# prev2 = dp[i-2], prev1 = dp[i-1]
prev2, prev1 = 0, 0for num in nums:
curr = max(prev1, prev2 + num) # skip or rob current house
prev2 = prev1
prev1 = curr
return prev1
Complexity
Time: O(n) — one pass. Space: O(1) — only two variables needed, not an array.
M 20MediumArraysTwo Pointers
Container With Most Water
Given an array height where height[i] is the height of a vertical line at position i,
find two lines that form a container holding the most water. Return the maximum area.
Test Cases
maxArea([1,8,6,2,5,4,8,3,7]) → 49 # lines at index 1 (h=8) and 8 (h=7)
maxArea([1,1]) → 1
maxArea([4,3,2,1,4]) → 16
two pointers from endsmove shorter sidegreedy observation
Start with left at 0 and right at the end — this maximizes width.
Area = min(height[left], height[right]) × (right - left).
Which pointer should you move? Moving the taller one can only decrease area (width decreases, height can only stay or decrease). So always move the shorter one.
Solution
from typing import List
defmaxArea(height: List[int]) -> int:
left, right = 0, len(height) - 1
max_water = 0while left < right:
water = min(height[left], height[right]) * (right - left)
max_water = max(max_water, water)
# Move the shorter line inward — moving the taller can't improve the areaif height[left] < height[right]:
left += 1else:
right -= 1return max_water
Complexity
Time: O(n) — each pointer moves at most n steps total. Space: O(1).
M 21MediumArraysGreedyHeap
Meeting Rooms II
Given a list of meeting time intervals [start, end], find the minimum number of conference rooms required.
sort by startmin-heap of end timesheapreplace for reuse
Sort meetings by start time. Use a min-heap where each entry is the end time of an active meeting.
For each new meeting: if the earliest-ending meeting finishes before this one starts, we can reuse that room (pop and push new end time). Otherwise, we need a new room (push to heap).
Solution
import heapq
from typing import List
defminMeetingRooms(intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[0])
heap = [] # min-heap of meeting end timesfor start, end in intervals:
if heap and heap[0] <= start:
heapq.heapreplace(heap, end) # reuse the room that freed upelse:
heapq.heappush(heap, end) # need a new roomreturnlen(heap) # number of rooms in use
Complexity
Time: O(n log n) — sorting + heap operations. Space: O(n) — heap holds at most n end times.
Alternative Approach
Event sweep: Create events (+1 for start, -1 for end), sort by time, track running max.
O(n log n) time. Cleaner to understand for some people.
M 22MediumDynamic Programming
Coin Change
Given an array of coin denominations coins and an integer amount,
return the fewest number of coins needed to make up that amount.
Return -1 if it cannot be done.
Test Cases
coinChange([1,5,11], 15) → 3 # 5+5+5 (NOT 1+1+...) — greedy fails here
coinChange([1,2,5], 11) → 3 # 5+5+1
coinChange([2], 3) → -1 (can't make 3 with only 2s)
coinChange([1], 0) → 0
bottom-up DPdp[amount] tableunbounded knapsack
dp[i] = minimum coins to make amount i. Start: dp[0]=0, dp[1..amount]=inf.
For each coin, for each amount from coin to amount: dp[x] = min(dp[x], dp[x-coin] + 1).
Why does greedy fail here? Try coins=[1,5,11], amount=15 — greedy picks 11+1+1+1+1=5 coins, but 5+5+5=3 is optimal.
Solution
from typing import List
defcoinChange(coins: List[int], amount: int) -> int:
# dp[i] = min coins to make exactly amount i
dp = [float('inf')] * (amount + 1)
dp[0] = 0# 0 coins needed to make amount 0for coin in coins:
for x inrange(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
Key insight: This is the unbounded knapsack problem — each coin can be used any number of times.
The inner loop goes from coin to amount (not the reverse), allowing coins to be reused.
Complexity
Time: O(amount × len(coins)) — two nested loops. Space: O(amount) — the dp array.
M 23MediumArrays
Product of Array Except Self
Given an integer array nums, return an array output where
output[i] equals the product of all elements of nums except nums[i].
Solve without using division and in O(n).
output[i] = (product of all elements to the left of i) × (product of all elements to the right of i).
Can you compute the left products and right products separately, then combine them?
Solution
from typing import List
defproductExceptSelf(nums: List[int]) -> List[int]:
n = len(nums)
result = [1] * n
# Pass 1 (left→right): result[i] = product of all nums[0..i-1]
prefix = 1for i inrange(n):
result[i] = prefix
prefix *= nums[i]
# Pass 2 (right→left): multiply in product of all nums[i+1..n-1]
suffix = 1for i inrange(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
Complexity
Time: O(n) — two linear passes. Space: O(1) — excluding the output array (we reuse it for prefix products).
M 24MediumArraysHash Set
Longest Consecutive Sequence
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
Solve in O(n) time.
Put all numbers in a set (O(1) lookup). For each number, only start counting a sequence if it's the START of a sequence — i.e., num-1 is NOT in the set. This ensures each sequence is counted exactly once, giving O(n) total.
Solution
from typing import List
deflongestConsecutive(nums: List[int]) -> int:
num_set = set(nums)
best = 0for num in num_set:
# Only start counting from the beginning of a sequenceif num - 1not in num_set:
curr = num
streak = 1while curr + 1in num_set:
curr += 1
streak += 1
best = max(best, streak)
return best
Key insight: The "only start from the beginning" check is what makes this O(n).
Without it, we'd re-count subsequences. With it, each number is traversed at most twice
(once in the outer loop, once in the inner while).
Complexity
Time: O(n) — each number is visited at most twice total across all iterations. Space: O(n) — the set stores all n numbers.
M 25MediumArraysBinary Search
Koko Eating Bananas
Koko has piles of bananas piles[i] and h hours. She eats at rate k bananas/hour (finishing a pile or just eating k from it each hour).
Find the minimum k such that she can eat all bananas within h hours.
Test Cases
minEatingSpeed([3,6,7,11], h=8) → 4
minEatingSpeed([30,11,23,4,20], h=5) → 30 # must finish each pile in 1 hour
minEatingSpeed([1,1,1,999999999], h=10) → 999999999
binary search on answermath.ceilfeasibility check function
The answer k is somewhere between 1 and max(piles). For a given k, you can check feasibility in O(n): sum up ceil(pile/k) for all piles and see if total ≤ h. Binary search on k.
Solution
import math
from typing import List
defminEatingSpeed(piles: List[int], h: int) -> int:
left, right = 1, max(piles)
while left < right:
mid = (left + right) // 2
hours = sum(math.ceil(p / mid) for p in piles)
if hours <= h:
right = mid # mid works — try smallerelse:
left = mid + 1# mid too slow — try fasterreturn left
Key pattern — "binary search on the answer": Whenever you need to minimize/maximize a value subject to a feasibility condition that is monotone (if k works, all k' > k also work), binary search on the answer space.
Here the feasibility check is O(n), giving total O(n log m) where m = max(piles).
Complexity
Time: O(n log m) where m = max(piles). Binary search runs log(m) iterations; each feasibility check is O(n). Space: O(1).