6 drills · 6 pattern exercises · 14 micro drills
Patterns used in this topic, with difficulty breakdown.
Find the best day to buy and the best later day to sell a stock to maximize your profit.
All 6 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Find the best day to buy and the best later day to sell a stock to maximize your profit.
Track the minimum price seen so far and compute profit at each step. This is Kadane's algorithm in disguise — the max gain ending here is today's price minus the running minimum.
Prompt
Given an array prices where prices[i] is the price of a stock on the ith day, return the maximum profit you can achieve from one buy and one sell. You must buy before you sell.
Solution
def max_profit(prices):
min_price = float('inf')
max_profit = 0
for price in prices:
min_price = min(min_price, price) # track cheapest buy
max_profit = max(max_profit, price - min_price) # best sell
return max_profit
# Test: max_profit([7,1,5,3,6,4]) == 5 (buy@1, sell@6)
# Test: max_profit([7,6,4,3,1]) == 0 (no profit possible)In plain English: Find the longest stretch of characters in a string where no character appears twice.
Expand the window right, adding chars to a set. When a duplicate is found, shrink from the left until the duplicate is removed. The set guarantees O(1) membership checks.
Prompt
Given a string s, find the length of the longest substring without repeating characters.
Solution
def length_of_longest_substring(s):
char_set = set()
l = 0
max_len = 0
for r in range(len(s)):
while s[r] in char_set:
char_set.remove(s[l]) # shrink from left
l += 1
char_set.add(s[r])
max_len = max(max_len, r - l + 1)
return max_len
# Test: length_of_longest_substring("abcabcbb") == 3 ("abc")
# Test: length_of_longest_substring("bbbbb") == 1In plain English: You can change up to k letters in a string. Find the longest stretch you can make all the same character.
The window is valid when (window_size - max_freq_char) <= k. The key insight: we only need to track the global max frequency ever seen — if the window becomes invalid, we slide it (don't shrink), so max_freq never needs to decrease.
Prompt
Given a string s and an integer k, you can change at most k characters to any uppercase letter. Return the length of the longest substring containing the same letter after performing at most k replacements.
Solution
def character_replacement(s, k):
count = {}
l = 0
max_freq = 0
result = 0
for r in range(len(s)):
count[s[r]] = count.get(s[r], 0) + 1
max_freq = max(max_freq, count[s[r]])
# window invalid: more than k chars need replacing
if (r - l + 1) - max_freq > k:
count[s[l]] -= 1
l += 1
result = max(result, r - l + 1)
return result
# Test: character_replacement("AABABBA", 1) == 4 ("AABA" or "ABBA")
# Test: character_replacement("ABAB", 2) == 4In plain English: Check if any rearrangement of s1 appears as a contiguous chunk inside s2.
Use a fixed-size sliding window equal to len(s1). Maintain a frequency count difference — when all counts are zero, you've found a permutation. Slide one char at a time, adding right and removing left.
Prompt
Given two strings s1 and s2, return True if s2 contains a permutation of s1 (i.e., one of s1's permutations is a substring of s2).
Solution
def check_inclusion(s1, s2):
if len(s1) > len(s2):
return False
from collections import Counter
need = Counter(s1)
window = Counter(s2[:len(s1)])
if window == need:
return True
for i in range(len(s1), len(s2)):
# add right char
window[s2[i]] += 1
# remove left char
left = s2[i - len(s1)]
window[left] -= 1
if window[left] == 0:
del window[left]
if window == need:
return True
return False
# Test: check_inclusion("ab", "eidbaooo") == True ("ba" is permutation)
# Test: check_inclusion("ab", "eidboaoo") == FalseIn plain English: Find the shortest piece of string s that contains every character from string t.
Expand right to satisfy the requirement, then shrink left to minimize. Track how many distinct characters are fully satisfied — when all are satisfied, try shrinking. Classic two-phase sliding window.
Prompt
Given strings s and t, return the minimum window substring of s that contains all characters in t (including duplicates). Return '' if no such window exists.
Solution
def min_window(s, t):
from collections import Counter
need = Counter(t)
missing = len(need) # distinct chars still needed
window = {}
l = 0
best = (float('inf'), 0, 0) # (length, start, end)
for r, ch in enumerate(s):
window[ch] = window.get(ch, 0) + 1
if ch in need and window[ch] == need[ch]:
missing -= 1
# shrink from left while valid
while missing == 0:
if r - l + 1 < best[0]:
best = (r - l + 1, l, r)
left = s[l]
window[left] -= 1
if left in need and window[left] < need[left]:
missing += 1
l += 1
return s[best[1]:best[2]+1] if best[0] != float('inf') else ''
# Test: min_window("ADOBECODEBANC", "ABC") == "BANC"
# Test: min_window("a", "aa") == "" In plain English: As a window of size k slides across the array, report the biggest number in each window position.
A monotonic decreasing deque keeps the current max at the front. When sliding right, pop smaller elements from the back (they can never be the max). Pop from the front when elements leave the window.
Prompt
Given an array nums and a sliding window of size k moving left to right, return the maximum value in each window position.
Solution
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, values are decreasing
result = []
for i, num in enumerate(nums):
# remove elements outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# maintain decreasing order
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
# Test: max_sliding_window([1,3,-1,-3,5,3,6,7], 3) == [3,3,5,5,6,7]6 exercises: spot the signals, pick the method, avoid the trap.
Given an array of stock prices by day, find the maximum profit from one buy-sell pair.
Signals
Track running min price; at each step profit = price - min_so_far. O(n).
Left at buy, right at sell. Move left when right finds lower price.
Trap
Don't try all O(n²) pairs. The running minimum makes it one-pass.
Given a string, find the length of the longest substring without repeating characters.
Signals
Expand right; when duplicate found, shrink left past the previous occurrence. O(n).
Map char → last index to jump left pointer directly instead of shrinking one by one.
Trap
Don't restart from scratch when a duplicate is found — just slide the left pointer forward.
Given string s and integer k, find the longest substring where you can replace at most k characters to make all characters the same.
Signals
Window is valid when (window_size - max_freq_char) <= k. Expand right, shrink left when invalid. O(n).
Binary search on answer length, check each length feasibility. O(n log n).
Trap
You don't need to update max_freq when shrinking — the window only grows when a better max is found.
Given strings s1 and s2, return true if s2 contains a permutation of s1 as a substring.
Signals
Fixed window of size len(s1). Compare frequency counts. O(n).
Maintain a 'matches' counter for how many of 26 chars have equal counts. O(n).
Trap
Don't generate all permutations — that's O(n!). The frequency count comparison is key.
Given strings s and t, find the minimum window in s that contains all characters of t.
Signals
Expand right to include chars; shrink left while all t chars are covered. Track best window. O(n).
Two frequency maps (need vs have) with a count of satisfied characters. O(n).
Trap
Handle duplicate characters in t correctly — 'have' count must match 'need' count per character.
Given array nums and window size k, return the max value in each window position.
Signals
Maintain a decreasing deque of indices. Front is always the max. Remove expired indices. O(n).
Max-heap with lazy deletion of out-of-window elements. O(n log k).
Trap
Don't use a simple max() per window — that's O(nk). The monotonic deque gives O(n) total.
14 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)Set-based window tracks unique characters. Shrink left when a duplicate enters.
seen = set()
left = 0
best = 0
for right in range(len(s)):
while s[right] in seen:
seen.remove(s[left])
left += 1
seen.add(s[right])
best = max(best, right - left + 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 += 12D 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]Move-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 wCounter-based fixed window slides character frequencies. Powers anagram detection.
from collections import Counter
w = Counter(s[:k])
for i in range(k, len(s)):
w[s[i]] += 1
w[s[i-k]] -= 1
if w[s[i-k]] == 0: del w[s[i-k]]Tracking have/need counts is the matching logic inside minimum-window-substring.
need, have = len(cnt_t), 0
for c in window:
window_cnt[c] += 1
if window_cnt[c] == cnt_t[c]:
have += 1Counter-based window matching powers minimum-window-substring and anagram problems.
from collections import Counter
need = Counter(t)
have, required = 0, len(need)
left = 0
for right in range(len(s)):
c = s[right]
need[c] -= 1
if need[c] == 0: have += 1
while have == required:
# record window [left, right]
need[s[left]] += 1
if need[s[left]] > 0: have -= 1
left += 1Monotonic deque maintains window max in O(n). Used for sliding-window-maximum and similar.
from collections import deque
dq = deque() # indices
for i, x in enumerate(a):
while dq and dq[0] < i - k + 1:
dq.popleft()
while dq and a[dq[-1]] <= x:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(a[dq[0]])Monotonic deque keeps the running maximum in O(1) per step. Key for window-maximum.
from collections import deque
d = deque()
for i, x in enumerate(a):
while d and a[d[-1]] <= x: d.pop()
d.append(i)
if d[0] <= i - k: d.popleft()Deque gives O(1) operations at both ends. Essential for BFS and sliding window.
from collections import deque
q = deque()
q.append(x)
q.popleft()