Pattern reminder: Many Medium problems combine two ideas — e.g. "sort + greedy" or "BFS + state tracking" or "DP + reconstruction". When stuck, ask: "What pattern would make the brute force fast here?"
Given an array nums where nums[i] is the maximum jump length from index i,
return True if you can reach the last index starting from index 0.
Test Cases
canJump([2,3,1,1,4]) → True # jump 1 → index 1 → jump 3 to end
canJump([3,2,1,0,4]) → False # always land on index 3 which has jump 0
canJump([0]) → True # already at end
canJump([2,0,0]) → True # jump 2 straight to end
greedy max_reachsingle pass
Track the furthest index you can reach so far. At each index i, if i > max_reach, you're stuck there — return False. Otherwise update max_reach = max(max_reach, i + nums[i]).
Solution
from typing import List
defcanJump(nums: List[int]) -> bool:
max_reach = 0for i, jump inenumerate(nums):
if i > max_reach:
returnFalse# can't reach this index
max_reach = max(max_reach, i + jump)
returnTrue
Complexity
Time: O(n), Space: O(1).
Alternative Approach
Work backwards: Start from the last index as "goal". Walk left — if you can reach the goal from index i, update goal = i. Return goal == 0. Same complexity.
M 27MediumStringsGreedy
Integer to Roman
Convert an integer (1 ≤ num ≤ 3999) to a Roman numeral string.
Roman numerals: I=1, IV=4, V=5, IX=9, X=10, XL=40, L=50, XC=90, C=100, CD=400, D=500, CM=900, M=1000.
Keep a list of (value, symbol) pairs ordered from largest to smallest. Greedily subtract the largest symbol that fits into num, appending it to the result each time.
Solution
defintToRoman(num: int) -> str:
vals = [
(1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD'),
(100, 'C'), (90, 'XC'), (50, 'L'), (40, 'XL'),
(10, 'X'), (9, 'IX'), (5, 'V'), (4, 'IV'),
(1, 'I'),
]
result = ""for val, symbol in vals:
while num >= val:
result += symbol
num -= val
return result
Complexity
Time: O(1) — num is bounded (≤ 3999), so the number of iterations is bounded. Space: O(1) — fixed size value table and output is bounded.
M 28MediumGraphsTopological Sort
Course Schedule
Given numCourses and a list of prerequisites where [a, b] means you must take b before a,
return True if you can finish all courses (i.e., no cycle exists).
Test Cases
canFinish(2, [[1,0]]) → True # take 0 then 1
canFinish(2, [[1,0],[0,1]]) → False # cycle: 0 requires 1 and 1 requires 0
canFinish(1, []) → True
canFinish(3, [[1,0],[2,1]]) → True
topological sort (Kahn's)in-degree arrayBFS queue
Cycle detection in a directed graph = can we topologically sort it?
Kahn's algorithm: start with nodes that have no prerequisites (in-degree 0). Remove them and reduce neighbors' in-degrees. If we process all nodes, no cycle. If some remain, there's a cycle.
Solution
from collections import defaultdict, deque
from typing import List
defcanFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = defaultdict(list)
in_degree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1# Start with all courses that have no prerequisites
queue = deque(i for i inrange(numCourses) if in_degree[i] == 0)
taken = 0while queue:
course = queue.popleft()
taken += 1for next_course in graph[course]:
in_degree[next_course] -= 1if in_degree[next_course] == 0:
queue.append(next_course)
return taken == numCourses # if not all processed → cycle exists
DFS with 3-color marking: White (unvisited), Gray (in-progress), Black (done). If you visit a Gray node, there's a cycle. Same complexity.
M 29MediumArraysTwo Pointers
Next Permutation
Find the next lexicographically greater permutation of the array of integers. If no such permutation exists (array is sorted descending), rearrange to the smallest permutation (sorted ascending). Do it in-place.
Test Cases
nextPermutation([1,2,3]) → [1,3,2]
nextPermutation([3,2,1]) → [1,2,3] # no larger permutation, wrap to smallest
nextPermutation([1,1,5]) → [1,5,1]
nextPermutation([1,3,2]) → [2,1,3]
rightmost descentswap + reverse suffixin-place
3 steps: (1) Find the rightmost index i where nums[i] < nums[i+1] — this is the "pivot". (2) Find the smallest element to the right of i that's greater than nums[i], swap them. (3) Reverse the suffix after position i to get the smallest arrangement of those elements.
Solution
from typing import List
defnextPermutation(nums: List[int]) -> None:
n = len(nums)
i = n - 2# Step 1: find rightmost ascent (nums[i] < nums[i+1])while i >= 0and nums[i] >= nums[i + 1]:
i -= 1if i >= 0:
# Step 2: find the smallest element > nums[i] in the suffix
j = n - 1while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
# Step 3: reverse the suffix to make it smallest
nums[i + 1:] = reversed(nums[i + 1:])
Complexity
Time: O(n) — at most two passes through the array. Space: O(1) — in-place.
M 30MediumGraphsTopological Sort
Course Schedule II
Same as Course Schedule, but return the order in which courses should be taken.
Return an empty array if it's impossible (cycle exists).
Same as Course Schedule, but instead of just counting, collect the processed courses into an order list. If the order list length != numCourses, return [].
Solution
from collections import defaultdict, deque
from typing import List
deffindOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
graph = defaultdict(list)
in_degree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque(i for i inrange(numCourses) if in_degree[i] == 0)
order = []
while queue:
course = queue.popleft()
order.append(course)
for nxt in graph[course]:
in_degree[nxt] -= 1if in_degree[nxt] == 0:
queue.append(nxt)
return order iflen(order) == numCourses else []
Complexity
Time: O(V + E), Space: O(V + E). Same as Course Schedule I.
M 31MediumArraysBinary Search
Find Peak Element
A peak element is strictly greater than its neighbors. Given an array nums,
find a peak element and return its index. Assume nums[-1] = nums[n] = -∞.
Solve in O(log n).
Test Cases
findPeakElement([1,2,3,1]) → 2 # nums[2]=3 is peak
findPeakElement([1,2,1,3,5,6,4]) → 5 # nums[5]=6 is one valid peak
findPeakElement([1]) → 0
binary searchslope direction
If nums[mid] < nums[mid+1], the peak must be to the right (the slope is going up). Otherwise it must be at mid or to the left. This lets you binary search.
Solution
from typing import List
deffindPeakElement(nums: List[int]) -> int:
left, right = 0, len(nums) - 1while left < right:
mid = (left + right) // 2if nums[mid] > nums[mid + 1]:
right = mid # peak at mid or to the leftelse:
left = mid + 1# going uphill to the right — peak is rightreturn left
Complexity
Time: O(log n), Space: O(1).
M 32MediumArraysGreedy
Best Time to Buy and Sell Stock II
Given prices array, you may complete as many transactions as you like (buy and sell multiple times), but must sell before buying again. Maximize total profit.
Test Cases
maxProfit([7,1,5,3,6,4]) → 7 # buy day2(1),sell day3(5) + buy day4(3),sell day5(6)
maxProfit([1,2,3,4,5]) → 4 # buy day1,sell day5 (or sum daily gains)
maxProfit([7,6,4,3,1]) → 0 # no profit possible
greedysum all upswings
If tomorrow's price is higher than today's, buy today and sell tomorrow (collect every positive daily gain). You don't need to simulate actual buy/sell days — just summing all positive price differences works.
Solution
from typing import List
defmaxProfit(prices: List[int]) -> int:
profit = 0for i inrange(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1] # collect every upward movereturn profit
Complexity
Time: O(n), Space: O(1).
M 33MediumArraysBacktracking
Subsets
Given an integer array nums with unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets.
Start with [[]] (just the empty set). For each number, create new subsets by adding that number to every existing subset. This doubles the result set each time.
Solution
from typing import List
# --- Iterative approach (clean and fast) ---defsubsets(nums: List[int]) -> List[List[int]]:
result = [[]]
for num in nums:
# For each existing subset, add a new one with num appended
result += [subset + [num] for subset in result]
return result
# --- Backtracking approach ---defsubsetsBacktrack(nums: List[int]) -> List[List[int]]:
result = []
defbt(start: int, path: List[int]) -> None:
result.append(path[:])
for i inrange(start, len(nums)):
path.append(nums[i])
bt(i + 1, path)
path.pop()
bt(0, [])
return result
Complexity
Time: O(n × 2ⁿ) — 2ⁿ subsets, each up to n elements. Space: O(n × 2ⁿ) — storing all subsets.
M 34MediumArrays
Rotate Array
Given an integer array nums, rotate it to the right by k steps in-place.
Test Cases
rotate([1,2,3,4,5,6,7], k=3) → [5,6,7,1,2,3,4]
rotate([-1,-100,3,99], k=2) → [3,99,-1,-100]
rotate([1,2], k=3) → [2,1] # k > n, so k = k % n = 1
three reversalsk %= nin-place O(1) space
Trick: reverse the whole array, then reverse the first k elements, then reverse the rest. Three reversals = O(1) space.
Solution
from typing import List
defrotate(nums: List[int], k: int) -> None:
n = len(nums)
k %= n # handle k > ndefreverse(l: int, r: int) -> None:
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1; r -= 1reverse(0, n - 1) # reverse whole arrayreverse(0, k - 1) # reverse first k elementsreverse(k, n - 1) # reverse the rest
Keep a parallel "min stack" alongside the main stack. When you push, also push to the min stack if the new value is ≤ current min. When you pop, if the popped value equals the min stack top, pop the min stack too.
Solution
classMinStack:
def__init__(self):
self.stack = []
self.min_stack = [] # tracks running minimumdefpush(self, val: int) -> None:
self.stack.append(val)
# Push to min_stack if it would be the new minimumifnot self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
defpop(self) -> None:
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
deftop(self) -> int:
return self.stack[-1]
defgetMin(self) -> int:
return self.min_stack[-1]
Complexity
Time: O(1) for all operations. Space: O(n) — min_stack holds at most n elements.
M 36MediumStringsDynamic Programming
Word Break
Given a string s and a dictionary wordDict, return True if s can be segmented into a space-separated sequence of dictionary words.
bottom-up DPdp[i] = can reach index iset lookup O(1)
dp[i] = True means the first i characters of s can be broken into dictionary words.
For each i, check all j < i: if dp[j] is True AND s[j:i] is in the dictionary, then dp[i] = True.
Solution
from typing import List
defwordBreak(s: str, wordDict: List[str]) -> bool:
word_set = set(wordDict) # O(1) lookup
n = len(s)
dp = [False] * (n + 1)
dp[0] = True# empty string is always breakablefor i inrange(1, n + 1):
for j inrange(i):
if dp[j] and s[j:i] in word_set:
dp[i] = Truebreakreturn dp[n]
Complexity
Time: O(n²) — two nested loops; each substring check is O(n) string hashing (amortized). Space: O(n) — dp array.
M 37MediumArraysBacktracking
Word Search
Given an m×n board of characters and a string word, return True if the word exists in the grid.
The word can be constructed from adjacent (horizontal/vertical) cells, each used at most once.
DFS backtrackingmark visited by mutation4-directional search
For each cell that matches word[0], try DFS. At each DFS step: mark the cell as visited (e.g., overwrite with '#'), recurse on all 4 neighbors for word[idx+1], then restore the cell.
Solution
from typing import List
defexist(board: List[List[str]], word: str) -> bool:
rows, cols = len(board), len(board[0])
defdfs(r: int, c: int, idx: int) -> bool:
if idx == len(word):
returnTrueif r < 0or r >= rows or c < 0or c >= cols:
returnFalseif board[r][c] != word[idx]:
returnFalse
temp = board[r][c]
board[r][c] = '#'# mark visited to prevent reuse
found = (dfs(r+1,c,idx+1) ordfs(r-1,c,idx+1) ordfs(r,c+1,idx+1) ordfs(r,c-1,idx+1))
board[r][c] = temp # restore (backtrack)return found
for r inrange(rows):
for c inrange(cols):
ifdfs(r, c, 0):
returnTruereturnFalse
Complexity
Time: O(m × n × 4^L) where L = word length. Each cell can branch into 4 directions for L levels. Space: O(L) — recursion depth equals word length.
M 38MediumArraysDynamic ProgrammingBinary Search
Longest Increasing Subsequence (LIS)
Given an array nums, return the length of the longest strictly increasing subsequence.
The O(n²) DP solution: dp[i] = LIS ending at index i. But there's an O(n log n) approach using "patience sorting" — maintain a tails array where tails[i] is the smallest tail element of all increasing subsequences of length i+1. For each new number, use binary search to find where it fits.
Solution
import bisect
from typing import List
# O(n log n) — patience sorting with binary searchdeflengthOfLIS(nums: List[int]) -> int:
tails = [] # tails[i] = smallest tail of all IS of length i+1for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num) # extends the longest ISelse:
tails[pos] = num # replace: maintain smallest possible tailreturnlen(tails)
# O(n²) DP — simpler to understanddeflengthOfLIS_DP(nums: List[int]) -> int:
dp = [1] * len(nums)
for i inrange(1, len(nums)):
for j inrange(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
returnmax(dp)
Complexity
Patience sorting: Time O(n log n), Space O(n) DP: Time O(n²), Space O(n) — simpler, good for understanding; mention both in interviews.
M 39MediumStringsGreedyHeap
Reorganize String
Given a string s, rearrange the characters so no two adjacent characters are the same.
Return any valid rearrangement, or "" if impossible.
Test Cases
reorganizeString("aab") → "aba"
reorganizeString("aaab") → "" # impossible: 3 a's but only 2 b's
reorganizeString("vvvlo") → "vlvov" (or similar valid arrangement)
max-heapalways pick 2 most frequentimpossible check
Greedy: always pick the two most frequent characters and place them together. This prevents the most-frequent character from becoming adjacent to itself. Impossible if any character has count > (len+1)//2.
Solution
import heapq
from collections import Counter
defreorganizeString(s: str) -> str:
count = Counter(s)
# Max-heap (negate freq for Python's min-heap)
heap = [(-freq, ch) for ch, freq in count.items()]
heapq.heapify(heap)
result = []
whilelen(heap) >= 2:
freq1, ch1 = heapq.heappop(heap)
freq2, ch2 = heapq.heappop(heap)
result.extend([ch1, ch2])
if freq1 + 1 < 0: heapq.heappush(heap, (freq1 + 1, ch1))
if freq2 + 1 < 0: heapq.heappush(heap, (freq2 + 1, ch2))
if heap:
freq, ch = heapq.heappop(heap)
if -freq > 1:
return""# more than 1 remaining: impossible
result.append(ch)
return"".join(result)
Complexity
Time: O(n log k) where k = unique characters (≤ 26). Each of n characters does a heap op. Space: O(k) — heap size is at most k.
M 40MediumArraysStrings
String Compression
Given a list of characters chars, compress it in-place using the following algorithm:
for each group of consecutive identical characters, write the character and then the count (if count > 1).
Return the new length.
read/write pointersrun-length encodingstr(count) for multi-digit counts
Use a read pointer to scan the original and a write pointer to write the compressed version back. Count consecutive identical chars, then write the char and (if count > 1) the digits of the count.
Solution
from typing import List
defcompress(chars: List[str]) -> int:
write = read = 0while read < len(chars):
char = chars[read]
count = 0# Count the run of identical characterswhile read < len(chars) and chars[read] == char:
read += 1
count += 1
chars[write] = char
write += 1if count > 1:
for c instr(count): # handles multi-digit counts like '12'
chars[write] = c
write += 1return write
Complexity
Time: O(n) — read pointer visits each character once. Space: O(1) — in-place modification.
M 41MediumArraysTwo Pointers
Sort Colors (Dutch National Flag)
Given an array with only values 0, 1, 2 (representing red, white, blue), sort in-place so all 0s come first, then 1s, then 2s. Do it in one pass with O(1) space.
Dutch National Flag (3-way partition)low/mid/high pointers
Dijkstra's Dutch National Flag: three pointers — low (0s boundary), mid (current), high (2s boundary).
Process mid: if 0, swap with low and advance both. If 2, swap with high and retreat high. If 1, just advance mid.
Given an array nums, return the minimum number of jumps to reach the last index.
Assume you can always reach the end.
Test Cases
jump([2,3,1,1,4]) → 2 # jump 1→index1, then jump 3→end
jump([2,3,0,1,4]) → 2
jump([1]) → 0 # already at end
greedy BFS layerscurr_end/curr_max
Think in "layers" like BFS. curr_end is the furthest you can reach in the current jump. When you pass curr_end, you must take another jump. Track curr_max as the furthest reachable in the next jump.
Solution
from typing import List
defjump(nums: List[int]) -> int:
jumps = 0
curr_end = 0# furthest reachable with current jumps
curr_max = 0# furthest reachable with one more jumpfor i inrange(len(nums) - 1):
curr_max = max(curr_max, i + nums[i])
if i == curr_end:
jumps += 1
curr_end = curr_max
return jumps
Complexity
Time: O(n), Space: O(1).
M 43MediumStringsStacks
Decode String
Given an encoded string, decode it. The encoding rule: k[encoded_string] means encoded_string repeated k times.
When you see '[', push (current_string, current_number) onto the stack and reset both. When you see ']', pop and build: new_string = popped_string + num × current_string.
Use 27 sets: 9 for rows, 9 for columns, 9 for 3×3 boxes. For each cell, check all three sets. The box index for cell (r, c) is (r//3)*3 + (c//3).
Solution
from typing import List
defisValidSudoku(board: List[List[str]]) -> bool:
rows = [set() for _ inrange(9)]
cols = [set() for _ inrange(9)]
boxes = [set() for _ inrange(9)]
for r inrange(9):
for c inrange(9):
val = board[r][c]
if val == '.':
continue
box_idx = (r // 3) * 3 + (c // 3)
if val in rows[r] or val in cols[c] or val in boxes[box_idx]:
returnFalse
rows[r].add(val); cols[c].add(val); boxes[box_idx].add(val)
returnTrue
Complexity
Time: O(1) — fixed 81 cells; doesn't grow with input. Space: O(1) — 27 sets, each max size 9.
M 46MediumStringsBacktracking
Letter Combinations of a Phone Number
Given a string of digits (2–9), return all possible letter combinations a phone keypad could represent.
monotonic stackstore indicesnext greater element pattern
Use a stack of indices. Walk forward — when the current temperature is warmer than the stack's top temperature, the top of the stack found its answer. Pop it and compute the difference in indices.
Solution
from typing import List
defdailyTemperatures(temperatures: List[int]) -> List[int]:
n = len(temperatures)
result = [0] * n
stack = [] # indices of days awaiting a warmer dayfor i, temp inenumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
idx = stack.pop()
result[idx] = i - idx # days waited
stack.append(i)
return result
Complexity
Time: O(n) — each index pushed and popped at most once. Space: O(n) — stack can hold all indices in worst case (descending temperatures).
M 48MediumRecursionBinary Exponentiation
Pow(x, n)
Implement pow(x, n) — x raised to the power n. Handle negative n and n = 0.
fast exponentiationhalving the exponentnegative n handling
x^n = (x^2)^(n//2) × (x if n is odd). This halves the exponent each step: O(log n) multiplications instead of O(n). Handle n < 0 by using 1/x with |n|.
Solution
defmyPow(x: float, n: int) -> float:
if n < 0:
x, n = 1 / x, -n
result = 1.0while n:
if n % 2 == 1: # odd exponent: multiply in one more x
result *= x
x *= x # square x
n //= 2# halve nreturn result
Complexity
Time: O(log n) — exponent halved each iteration. Space: O(1) — iterative approach, no call stack.
M 49MediumStringsStacks
Simplify Path
Given an absolute Unix path, simplify it. . means current dir, .. means parent dir. Remove double slashes and trailing slashes.
split('/')stack for directory stackedge cases: '.', '..', empty parts
Split by '/'. Ignore empty strings and '.'. For '..', pop the stack (if non-empty). For any real directory name, push it. Join the stack with '/' at the end.
Solution
defsimplifyPath(path: str) -> str:
stack = []
for part in path.split('/'):
if part == '..':
if stack:
stack.pop() # go up one directoryelif part and part != '.':
stack.append(part) # valid directory name# '' (double slash) and '.' are both ignoredreturn'/' + '/'.join(stack)
Complexity
Time: O(n) where n is the path length. Space: O(n) — stack can hold up to n/2 directory names.