9 drills · 9 pattern exercises · 18 micro drills
Patterns used in this topic, with difficulty breakdown.
Find the best day to buy and the best day to sell a stock to make the most money.
All 9 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Find the best day to buy and the best day to sell a stock to make the most money.
Track the minimum price seen so far. At each day, the best you can do is sell at today's price minus the cheapest buy — one pass, O(1) space.
Prompt
Given an array of stock prices (one per day), find the maximum profit from one buy and one sell (buy before sell).
Solution
def max_profit(prices):
min_price = float('inf')
max_profit = 0
for p in prices:
min_price = min(min_price, p)
max_profit = max(max_profit, p - min_price) # sell today, bought at min
return max_profit
# Test: max_profit([7,1,5,3,6,4]) == 5 (buy at 1, sell at 6)
# Test: max_profit([7,6,4,3,1]) == 0 (no profit possible)In plain English: Starting at the first position, check if you can hop to the end given each position's maximum jump distance.
Track the farthest index reachable. At each position, update the farthest reach — if you ever land beyond the farthest, you are stuck.
Prompt
Given an array where each element is the max jump length from that position, determine if you can reach the last index starting from index 0.
Solution
def can_jump(nums):
farthest = 0
for i in range(len(nums)):
if i > farthest:
return False # stuck: can't reach this position
farthest = max(farthest, i + nums[i])
return True
# Test: can_jump([2,3,1,1,4]) == True
# Test: can_jump([3,2,1,0,4]) == FalseIn plain English: Find which gas station to start at so you can drive around a circular route without running out of fuel.
If total gas >= total cost, a solution exists. Track the running surplus — whenever it goes negative, the answer must be past that point.
Prompt
There are n gas stations in a circle. Given gas[i] and cost[i], find the starting station index for a complete circuit, or -1 if impossible.
Solution
def can_complete_circuit(gas, cost):
total = 0
tank = 0
start = 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
total += diff
tank += diff
if tank < 0:
start = i + 1 # can't start at or before i
tank = 0
return start if total >= 0 else -1
# Test: can_complete_circuit([1,2,3,4,5],[3,4,5,1,2]) == 3
# Test: can_complete_circuit([2,3,4],[3,4,3]) == -1In plain English: Split a string into the most pieces possible where no letter appears in more than one piece.
Record each character's last occurrence. Extend the current partition's end to cover all characters' last positions — cut when you reach the end.
Prompt
Partition a string into as many parts as possible so that each letter appears in at most one part. Return the sizes of the parts.
Solution
def partition_labels(s):
last = {c: i for i, c in enumerate(s)}
sizes = []
start = end = 0
for i, c in enumerate(s):
end = max(end, last[c]) # extend to cover last occurrence
if i == end:
sizes.append(end - start + 1)
start = i + 1
return sizes
# Test: partition_labels("ababcbacadefegdehijhklij") == [9, 7, 8]In plain English: Remove the fewest intervals so that none of the remaining ones overlap.
Sort by end time and greedily keep intervals that start after the previous one ends — this maximizes non-overlapping intervals (classic activity selection).
Prompt
Given a list of intervals, find the minimum number of intervals to remove so that the remaining intervals do not overlap.
Solution
def erase_overlap_intervals(intervals):
intervals.sort(key=lambda x: x[1]) # sort by end time
count = 0
prev_end = float('-inf')
for start, end in intervals:
if start >= prev_end:
prev_end = end # keep this interval
else:
count += 1 # remove this interval (overlaps)
return count
# Test: erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]]) == 1
# Test: erase_overlap_intervals([[1,2],[1,2],[1,2]]) == 2In plain English: Find the fewest jumps needed to get from the start to the end of the array.
Think of it as BFS where each 'level' is the farthest you can reach in one more jump. Track the current level's end and the farthest reachable. When you pass the current end, increment jumps.
Prompt
Given an array where each element is the max jump length from that position, return the minimum number of jumps to reach the last index. Assume you can always reach the end.
Solution
def jump(nums):
jumps = 0
cur_end = 0
farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == cur_end: # must jump
jumps += 1
cur_end = farthest
return jumps
# Test: jump([2,3,1,1,4]) == 2 (0->1->4)
# Test: jump([2,3,0,1,4]) == 2In plain English: Find the gas station to start at so you can drive around a circular route without running out of fuel.
If total gas >= total cost, a solution exists. Track running tank — if it goes negative, the start must be past this point (reset). The greedy insight: the station after the worst deficit is the answer.
Prompt
There are n gas stations in a circle. gas[i] is the fuel at station i, cost[i] is fuel to travel to station i+1. Return the starting station index to complete the circuit, or -1 if impossible.
Solution
def can_complete_circuit(gas, cost):
if sum(gas) < sum(cost):
return -1
tank = 0
start = 0
for i in range(len(gas)):
tank += gas[i] - cost[i]
if tank < 0:
start = i + 1 # can't start at or before i
tank = 0
return start
# Test: can_complete_circuit([1,2,3,4,5], [3,4,5,1,2]) == 3
# Test: can_complete_circuit([2,3,4], [3,4,3]) == -1In plain English: Split a string into the most pieces possible where no letter appears in more than one piece.
First pass: record the last occurrence of each character. Second pass: expand the current partition's end to include the last occurrence of every character encountered. When you reach the end, cut.
Prompt
Given a string s, partition it into as many parts as possible so that each letter appears in at most one part. Return the sizes of the parts.
Solution
def partition_labels(s):
last = {ch: i for i, ch in enumerate(s)}
result = []
start = end = 0
for i, ch in enumerate(s):
end = max(end, last[ch]) # extend partition
if i == end: # reached the boundary
result.append(end - start + 1)
start = i + 1
return result
# Test: partition_labels("ababcbacadefegdehijhklij")
# == [9, 7, 8]
# Test: partition_labels("eccbbbbdec") == [10]In plain English: Check if a string of parentheses with wildcards (*) can be made valid.
Track a range [lo, hi] of possible open-paren counts. '(' increments both, ')' decrements both, '*' widens the range. If hi < 0, too many ')'. If lo < 0, clamp to 0. Valid if lo == 0 at end.
Prompt
Given a string containing '(', ')' and '*' where '*' can be '(', ')' or empty, determine if the string is valid.
Solution
def check_valid_string(s):
lo = hi = 0 # range of possible open paren counts
for ch in s:
if ch == '(':
lo += 1
hi += 1
elif ch == ')':
lo -= 1
hi -= 1
else: # '*'
lo -= 1 # treat as ')'
hi += 1 # treat as '('
if hi < 0: # too many ')'
return False
lo = max(lo, 0) # can't have negative open count
return lo == 0
# Test: check_valid_string("(*))") == True
# Test: check_valid_string("(*)") == True
# Test: check_valid_string(")(") == False9 exercises: spot the signals, pick the method, avoid the trap.
Find maximum profit from one buy and one sell (buy before sell).
Signals
Track min_price. At each day: max_profit = max(max_profit, price - min_price). O(n).
DP formulation works but is overkill. Greedy with running min is simpler.
Trap
Brute force checking all (buy, sell) pairs is O(n²). The running minimum insight makes it O(n).
Can you reach the last index? Each element is the max jump length from that position.
Signals
Track max_reach. At each position i: if i > max_reach, return False. Else update max_reach. O(n).
dp[i] = can reach i? Works but O(n²). Greedy is O(n) because reachability is monotonic.
Trap
DP is correct but slow. The greedy insight: once a position is reachable, all earlier ones are too.
Find starting station for a complete circuit, or -1 if impossible.
Signals
If total_gas >= total_cost, answer exists. Track running surplus; when < 0, reset start to next station. O(n).
Trap
Brute force trying every starting station is O(n²). The surplus reset insight gives O(n).
Partition string into most parts so each letter appears in at most one part.
Signals
Map each char to its last index. Scan: extend partition end to max(last[c]). Cut when i == end. O(n).
The hash map is part of the greedy solution — used to precompute last occurrences.
Trap
This is an interval merging problem in disguise. Each character defines an interval [first, last].
Minimum intervals to remove so the rest don't overlap.
Signals
Sort by end time. Keep intervals that don't overlap with the last kept. Remove count = total - kept. O(n log n).
LIS-like DP on intervals sorted by end. O(n²) — much slower than greedy.
Trap
Sort by END time, not start time. Sorting by start doesn't give the optimal greedy choice.
Given array where each element is max jump length, find minimum jumps to reach the last index.
Signals
Track current jump boundary and farthest reach. When hitting boundary, jump++, extend boundary. O(n).
dp[i] = min jumps to reach i. O(n²) — much slower.
Trap
Don't BFS with a queue — the greedy two-pointer approach is O(n) with O(1) space.
Given gas stations in a circle with gas[i] and cost[i], find the starting station to complete the circuit, or -1.
Signals
Track total and current tank. If current < 0, reset start to next station. If total >= 0, start is valid. O(n).
Trap
Don't simulate from each station O(n²). The single-pass greedy works because if total >= 0, exactly one valid start exists.
Partition a string so each letter appears in at most one part. Maximize the number of parts.
Signals
Track last occurrence of each char. Extend current partition to max(last[c]). When i == end, cut. O(n).
Same. The hash map of last occurrences is the key data structure.
Trap
Don't try to split greedily without precomputing last occurrences — you'd need to scan ahead repeatedly.
Given a string with '(', ')', and '*' (* can be '(', ')' or empty), determine if it's valid.
Signals
Track lo (min open) and hi (max open). '(' → both++. ')' → both--. '*' → lo--, hi++. Valid if lo <= 0 <= hi throughout. O(n).
dp[i][open_count] = feasibility. O(n²) — overkill when greedy works.
Trap
Don't generate all 3^n possibilities for *. The lo/hi range tracking is the elegant O(n) solution.
18 quick recall drills to reinforce this topic.
Two-state DP: cash (free to buy) and hold (free to sell). Fee paid on sell. No cooldown needed.
def maxProfit(prices, fee):
cash = 0 # not holding
hold = -prices[0] # holding
for p in prices[1:]:
cash = max(cash, hold + p - fee)
hold = max(hold, cash - p)
return cashThree-state machine: hold → sell → rest → buy. After selling, must rest one day before buying.
def maxProfit(prices):
hold = -prices[0] # holding stock
sold = 0 # just sold (cooldown next)
rest = 0 # not holding, free to buy
for p in prices[1:]:
hold, sold, rest = (
max(hold, rest - p), # keep or buy
hold + p, # sell
max(rest, sold), # stay or come off cooldown
)
return max(sold, rest)Single-pass tracking of running minimum and maximum profit. Classic greedy O(n) solution.
mn = float('inf')
mx = 0
for p in prices:
mn = min(mn, p)
mx = max(mx, p - mn)Track farthest reachable and current boundary. Increment jumps when boundary is hit.
jumps = cur_end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == cur_end:
jumps += 1
cur_end = farthestMove-zeroes is remove-element followed by a fill. Classic two-pointer warm-up.
w = 0
for r in range(len(a)):
if a[r] != 0:
a[w] = a[r]
w += 1
while w < len(a):
a[w] = 0
w += 1Write-pointer compaction for sorted arrays. Returns new length.
w = 1
for i in range(1, len(a)):
if a[i] != a[i-1]:
a[w] = a[i]
w += 1
return wTrack running surplus and total balance. Reset start when tank goes negative.
total = tank = start = 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
total += diff
tank += diff
if tank < 0:
start = i + 1
tank = 0
return start if total >= 0 else -1Map each char to its last index. Extend partition end greedily.
last = {c: i for i, c in enumerate(s)}
res = []
start = end = 0
for i, c in enumerate(s):
end = max(end, last[c])
if i == end:
res.append(end - start + 1)
start = i + 1Merging sorted lists is the core of merge sort and merge-k-lists.
i = j = 0
merged = []
while i < len(a) and j < len(b):
if a[i] <= b[j]:
merged.append(a[i]); i += 1
else:
merged.append(b[j]); j += 1
merged.extend(a[i:])
merged.extend(b[j:])Hash-map window tracks last index of each char. Avoids set removal on duplicates.
seen = {}
l = res = 0
for r, c in enumerate(s):
if c in seen and seen[c] >= l:
l = seen[c] + 1
seen[c] = r
res = max(res, r - l + 1)Custom key sorting is Python's primary sort mechanism. Foundation for interval and custom-order problems.
a.sort(key=lambda x: x[1])Multi-key sorting handles tiebreakers. Used in leaderboard and event scheduling.
a.sort(key=lambda x: (x[0], -x[1]))Sorting by end time is the greedy strategy for interval scheduling and activity selection.
intervals.sort(key=lambda x: x[1])Lomuto partition is the core of quicksort and quickselect. Know it cold for kth-element problems.
def partition(a, lo, hi):
pivot = a[hi]
i = lo
for j in range(lo, hi):
if a[j] <= pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
return iPartition is the heart of quicksort. Same as Lomuto partition — drill until automatic.
def partition(a, lo, hi):
pivot = a[hi]
i = lo
for j in range(lo, hi):
if a[j] <= pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
return iLongest Common Subsequence is a classic 2D DP. Foundation for diff algorithms.
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])2D interval DP. Iterate i from bottom-up so dp[i+1] is already computed. Equivalent to LCS(s, reverse(s)).
def longestPalindromeSubseq(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]Window is valid when (window_size - max_freq) <= k. max_freq only needs to increase — shrinking the window can't help.
count = {}
l = max_freq = 0
for r in range(len(s)):
count[s[r]] = count.get(s[r], 0) + 1
max_freq = max(max_freq, count[s[r]])
if (r - l + 1) - max_freq > k:
count[s[l]] -= 1
l += 1