6 drills · 6 pattern exercises · 8 micro drills
Patterns used in this topic, with difficulty breakdown.
Keep replacing a number with the sum of the squares of its digits. It's happy if you eventually reach 1.
All 6 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Rotate a square grid of numbers 90 degrees clockwise without using extra space.
Transpose (swap rows and columns) then reverse each row. This two-step trick works because a 90-degree clockwise rotation = transpose + horizontal flip.
Prompt
Given an n x n 2D matrix, rotate the image by 90 degrees clockwise in-place.
Solution
def rotate(matrix):
n = len(matrix)
# Step 1: Transpose (swap matrix[i][j] with matrix[j][i])
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Step 2: Reverse each row
for row in matrix:
row.reverse()
return matrix
# Test: rotate([[1,2,3],[4,5,6],[7,8,9]])
# == [[7,4,1],[8,5,2],[9,6,3]]In plain English: Walk around a matrix in a spiral from the outside in, collecting elements.
Maintain four boundaries (top, bottom, left, right). Traverse right, down, left, up, shrinking the boundary after each pass. Stop when boundaries cross.
Prompt
Given an m x n matrix, return all elements in spiral order.
Solution
def spiral_order(matrix):
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
for j in range(left, right + 1): # right
result.append(matrix[top][j])
top += 1
for i in range(top, bottom + 1): # down
result.append(matrix[i][right])
right -= 1
if top <= bottom:
for j in range(right, left - 1, -1): # left
result.append(matrix[bottom][j])
bottom -= 1
if left <= right:
for i in range(bottom, top - 1, -1): # up
result.append(matrix[i][left])
left += 1
return result
# Test: spiral_order([[1,2,3],[4,5,6],[7,8,9]])
# == [1,2,3,6,9,8,7,4,5]In plain English: If any cell in a grid is zero, zero out its entire row and column.
Use the first row and first column as markers. First pass: mark which rows/cols need zeroing. Second pass: zero based on markers. Handle the first row/col separately with a flag.
Prompt
Given an m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Solution
def set_zeroes(matrix):
m, n = len(matrix), len(matrix[0])
first_row_zero = any(matrix[0][j] == 0 for j in range(n))
first_col_zero = any(matrix[i][0] == 0 for i in range(m))
# mark zeros in first row/col
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0 # mark row
matrix[0][j] = 0 # mark col
# zero cells based on markers
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# handle first row and col
if first_row_zero:
for j in range(n):
matrix[0][j] = 0
if first_col_zero:
for i in range(m):
matrix[i][0] = 0
return matrix
# Test: set_zeroes([[1,1,1],[1,0,1],[1,1,1]])
# == [[1,0,1],[0,0,0],[1,0,1]]In plain English: Keep replacing a number with the sum of the squares of its digits. It's happy if you eventually reach 1.
The sequence either converges to 1 or enters a cycle. Use Floyd's cycle detection (slow/fast pointers) or a hash set to detect the cycle. If you hit 1, it's happy.
Prompt
Write an algorithm to determine if a number n is happy. A happy number is defined by repeatedly summing the squares of its digits until you reach 1 or loop endlessly.
Solution
def is_happy(n):
def digit_sq_sum(x):
total = 0
while x:
x, d = divmod(x, 10)
total += d * d
return total
# Floyd's cycle detection: fast moves 2 steps, slow 1
slow = n
fast = digit_sq_sum(n)
while fast != 1 and slow != fast:
slow = digit_sq_sum(slow)
fast = digit_sq_sum(digit_sq_sum(fast)) # two steps so it laps slow if a cycle exists
return fast == 1
# Test: is_happy(19) == True (19->82->68->100->1)
# Test: is_happy(2) == FalseIn plain English: Compute x to the power n efficiently, handling negative exponents too.
Binary exponentiation: if n is even, x^n = (x^(n/2))^2. If n is odd, x^n = x * x^(n-1). This halves the exponent each step, giving O(log n) multiplications instead of O(n).
Prompt
Implement pow(x, n), which calculates x raised to the power n.
Solution
def my_pow(x, n):
if n < 0:
x = 1 / x
n = -n
result = 1
while n:
if n & 1: # odd exponent
result *= x
x *= x # square the base
n >>= 1 # halve the exponent
return result
# Test: my_pow(2.0, 10) == 1024.0
# Test: my_pow(2.0, -2) == 0.25In plain English: Multiply two large numbers given as strings without using built-in big integer conversion.
Simulate grade-school multiplication. The product of digit at position i and j lands at position i+j and i+j+1 in the result array. Process carries from right to left.
Prompt
Given two non-negative integers represented as strings, return their product as a string. You must not convert the inputs to integers directly.
Solution
def multiply(num1, num2):
if num1 == '0' or num2 == '0':
return '0'
n1, n2 = len(num1), len(num2)
result = [0] * (n1 + n2)
for i in range(n1 - 1, -1, -1):
for j in range(n2 - 1, -1, -1):
mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
# p1, p2 map digit positions i,j to their place in the product array
p1, p2 = i + j, i + j + 1
total = mul + result[p2] # add existing value (carry from a previous digit pair)
result[p2] = total % 10
result[p1] += total // 10 # propagate carry leftward
# skip leading zeros
start = 0
while start < len(result) - 1 and result[start] == 0:
start += 1
return ''.join(str(d) for d in result[start:])
# Test: multiply("123", "456") == "56088"
# Test: multiply("2", "3") == "6"
# Test: multiply("0", "12345") == "0" 6 exercises: spot the signals, pick the method, avoid the trap.
Rotate an n×n matrix 90 degrees clockwise in-place.
Signals
Transpose (swap m[i][j] with m[j][i]), then reverse each row. O(n²).
Rotate four cells at a time in concentric rings. Same O(n²) but trickier.
Trap
Transpose + reverse rows = 90° CW. Transpose + reverse columns = 90° CCW. Don't mix them up.
Given an m×n matrix, return all elements in spiral order.
Signals
Track 4 boundaries. Traverse right, down, left, up; shrink after each. O(m*n).
Mark visited cells, turn right when hitting a wall or visited cell. Same O(m*n).
Trap
Check boundary conditions after EACH direction — the inner boundaries may have already crossed.
Given an m×n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Signals
Use first row/col as flags. Separate flag for row0/col0 themselves. Two passes. O(mn) time, O(1) space.
Track zero rows and columns in sets. O(m+n) space — simpler but not O(1).
Trap
Process the first row and column LAST, otherwise you corrupt the markers.
Determine if a number is 'happy': repeatedly sum the squares of its digits; if it reaches 1 it's happy.
Signals
Track seen numbers. If you see a repeat, it's a cycle → not happy. O(log n) per step.
Floyd's slow/fast on the digit-sum function. Detects cycle without extra space.
Trap
Don't assume it always converges quickly. The cycle detection is essential to avoid infinite loops.
Implement pow(x, n) — compute x raised to the power n.
Signals
x^n = (x^(n/2))². If n is odd, multiply by x. O(log n).
Iterative: square x and halve n, accumulating when n is odd. Same O(log n).
Trap
Handle n < 0 by computing 1/x^(-n). Watch for integer overflow when negating n.
Given two numbers represented as strings, return their product as a string.
Signals
Result has len(n1)+len(n2) digits. Multiply each pair, add to position i+j+1. Handle carries. O(m*n).
Trap
Indexing: digit at position i times digit at position j contributes to result position i+j and i+j+1.
8 quick recall drills to reinforce this topic.
Transpose + reverse-rows rotates 90 degrees clockwise in-place. Classic matrix manipulation.
n = len(m)
for i in range(n):
for j in range(i+1, n):
m[i][j], m[j][i] = m[j][i], m[i][j]
for row in m:
row.reverse()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 wSpiral traversal uses shrinking boundaries: top, bottom, left, right.
res = []
t, b, l, r = 0, len(m)-1, 0, len(m[0])-1
while t <= b and l <= r:
for c in range(l, r+1): res.append(m[t][c])
t += 1
for c in range(t, b+1): res.append(m[c][r])
r -= 1Using first row/col as markers gives O(1) extra space for zero-setting.
row0 = any(m[0][j] == 0 for j in range(n))
col0 = any(m[i][0] == 0 for i in range(r))
for i in range(1, r):
for j in range(1, n):
if m[i][j] == 0:
m[i][0] = m[0][j] = 0Digit-square-sum with cycle detection (fast/slow or set) determines happiness.
def digit_sq_sum(n):
s = 0
while n:
n, d = divmod(n, 10)
s += d * d
return sPhase 1: detect cycle with slow/fast. Phase 2: reset slow to head, advance both by 1 — they meet at cycle start.
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow # cycle startSortedness check is a precondition guard for binary search and merge operations.
all(a[i] <= a[i+1] for i in range(len(a)-1))