NeetCode 150 · Math & Geometry

Math & Geometry Problems

Matrix transformations, cycle detection for happy numbers, fast exponentiation, and long multiplication. These test mathematical reasoning more than pure algorithmic patterns.

Problems: 8
Easy: 2
Medium: 6
Hard: 0
Learning approach: Read the problem. Try the test cases yourself first. Click Hint if stuck — it guides without spoiling. Use Show Solution only after a genuine attempt. Then hit Let's Code to run your solution live.
01 Medium ArrayMathMatrix
Rotate n×n matrix by 90 degrees clockwise, in-place.
Test Cases
rotate([[1,2,3],[4,5,6],[7,8,9]]) → [[7,4,1],[8,5,2],[9,6,3]]
transpose then reverse rowsin-place O(1)O(n²)
Rotation = transpose + reverse each row. Try it on a 3×3 example.
Python Solution
def rotate(matrix): n = len(matrix) # Step 1: Transpose (swap across main diagonal) 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()
Key idea: 90° clockwise = transpose + reverse each row. Transpose: swap matrix[i][j] with matrix[j][i]. Then reverse each row. This achieves the rotation in-place with O(1) extra space.
Time: O(n²).
Space: O(1).
02 Medium ArrayMatrixSimulation
Given m×n matrix, return all elements in spiral order.
Test Cases
spiralOrder([[1,2,3],[4,5,6],[7,8,9]]) → [1,2,3,6,9,8,7,4,5] spiral Order([[1,2,3,4],[5,6,7,8],[9,10,11,12]]) → [1,2,3,4,8,12,11,10,9,5,6,7]
four boundariesshrink boundaries after each directionO(m·n)
Use four boundaries: top, bottom, left, right. Process each direction, then shrink the corresponding boundary.
Python Solution
def spiralOrder(matrix): result = [] top, bottom, left, right = 0, len(matrix)-1, 0, len(matrix[0])-1 while top <= bottom and left <= right: for c in range(left, right+1): result.append(matrix[top][c]) top += 1 for r in range(top, bottom+1): result.append(matrix[r][right]) right -= 1 if top <= bottom: for c in range(right, left-1, -1): result.append(matrix[bottom][c]) bottom -= 1 if left <= right: for r in range(bottom, top-1, -1): result.append(matrix[r][left]) left += 1 return result
Key idea: Four boundaries shrink as we spiral inward. Process right (top row), down (right col), left (bottom row), up (left col). Guard middle checks to prevent double-counting.
Time: O(m·n).
Space: O(1) extra.
03 Medium ArrayHash TableMatrix
If an element is 0, set its entire row and column to 0. Do it in-place.
Test Cases
setZeroes([[1,1,1],[1,0,1],[1,1,1]]) → [[1,0,1],[0,0,0],[1,0,1]]
record zero positions firstO(m·n)two-pass
First pass: find all zeros and record their positions. Second pass: zero out the corresponding rows and columns.
Python Solution
def setZeroes(matrix): rows, cols = len(matrix), len(matrix[0]) zero_rows, zero_cols = set(), set() # First pass: find zeros for r in range(rows): for c in range(cols): if matrix[r][c] == 0: zero_rows.add(r) zero_cols.add(c) # Second pass: zero out for r in range(rows): for c in range(cols): if r in zero_rows or c in zero_cols: matrix[r][c] = 0
Key idea: Collect zero positions first (can't do in-place immediately or you'd zero rows/cols that weren't originally zero). Then zero out all marked rows and columns.
Time: O(m·n).
Space: O(m+n).
04 Easy Hash TableMathTwo Pointers
Replace a number with the sum of squares of its digits. Repeat until it equals 1 (happy) or loops endlessly (not happy).
Test Cases
isHappy(19) → True # 19→82→68→100→1 isHappy(2) → False
Floyd's cycle detectiondigit square sumO(log n)
If the number is unhappy, the sequence eventually cycles. Use Floyd's slow/fast pointer to detect the cycle.
Python Solution
def isHappy(n): def sum_squares(x): total = 0 while x: x, d = divmod(x, 10) total += d * d return total slow = fast = n while True: slow = sum_squares(slow) fast = sum_squares(sum_squares(fast)) if slow == fast: return slow == 1
Key idea: The sequence either reaches 1 or cycles. Floyd's slow/fast pointer detects the cycle endpoint. If the meeting point is 1, it's happy; otherwise it's in a non-1 cycle.
Time: O(log n).
Space: O(1).
05 Easy ArrayMath
Given large integer represented as digits array, increment by one and return the result.
Test Cases
plusOne([1,2,3]) → [1,2,4] plusOne([4,3,2,1]) → [4,3,2,2] plusOne([9]) → [1,0]
iterate from rightcarry propagationO(n)
Walk from right to left. Increment if digit < 9 and return. If digit is 9, set to 0 and carry. If all were 9, prepend 1.
Python Solution
def plusOne(digits): for i in range(len(digits) - 1, -1, -1): if digits[i] < 9: digits[i] += 1 return digits digits[i] = 0 # carry return [1] + digits # all 9s: prepend 1
Key idea: Walk from the right. If digit < 9, increment and done. If digit is 9, set to 0 and continue (carry). If the loop completes, all digits were 9, so prepend a 1.
Time: O(n).
Space: O(1) usually.
06 Medium MathRecursion
Implement pow(x, n) — x raised to the power n. n can be negative.
Test Cases
myPow(2.0, 10) → 1024.0 myPow(2.1, 3) → 9.261 myPow(2.0, -2) → 0.25
fast exponentiationhalve n each stepO(log n)
If n is even: x^n = (x²)^(n/2). If odd: x^n = x * (x²)^((n-1)/2). Handle negative n by using 1/x.
Python Solution
def myPow(x, n): if n < 0: x, n = 1 / x, -n result = 1 while n: if n % 2 == 1: result *= x # odd power: include x in result x *= x # square the base n //= 2 # halve the exponent return result
Key idea: Fast exponentiation by squaring. Each iteration halves n: if odd, multiply result by x; square x and halve n. This reduces O(n) multiplications to O(log n).
Time: O(log n).
Space: O(1).
07 Medium MathStringSimulation
Given two non-negative integers num1 and num2 as strings, return their product as a string. Cannot use big integers directly.
Test Cases
multiply('2','3') → '6' multiply('123','456') → '56088'
position arraydigit multiplicationO(m·n)
A digit at position i and another at position j contribute to positions i+j and i+j+1 in the result.
Python Solution
def multiply(num1, num2): if num1 == '0' or num2 == '0': return '0' m, n = len(num1), len(num2) pos = [0] * (m + n) for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): mul = (ord(num1[i]) - 48) * (ord(num2[j]) - 48) p1, p2 = i + j, i + j + 1 total = mul + pos[p2] pos[p2] = total % 10 pos[p1] += total // 10 return ''.join(str(d) for d in pos).lstrip('0')
Key idea: Long multiplication. Each pair of digits at positions i and j contributes to result positions i+j (carry) and i+j+1. Process all pairs and accumulate into a position array.
Time: O(m·n).
Space: O(m+n).
08 Medium ArrayHash TableDesign
Given stream of points, support: add(point) and count(point) — the number of axis-aligned squares with the given point as a corner.
Test Cases
ds = DetectSquares() ds.add([3,10]); ds.add([11,2]); ds.add([3,2]) ds.count([11,10]) → 1 ds.count([14,8]) → 0
point count mapx_to_ys dictenumerate square corners
For count(x1,y1), find another corner (x1,y2) with the same x. The side length = |y2-y1|. Check if (x2,y1) and (x2,y2) exist where x2 = x1 ± side.
Python Solution
from collections import defaultdict class DetectSquares: def __init__(self): self.point_count = defaultdict(int) self.x_to_ys = defaultdict(set) def add(self, point): x, y = point self.point_count[(x, y)] += 1 self.x_to_ys[x].add(y) def count(self, point): x1, y1 = point result = 0 for y2 in self.x_to_ys[x1]: if y2 == y1: continue side = abs(y2 - y1) for x2 in [x1 + side, x1 - side]: result += (self.point_count[(x2, y1)] * self.point_count[(x2, y2)] * self.point_count[(x1, y2)]) return result
Key idea: For each potential diagonal (x1,y1)→(x1,y2), the side is |y2-y1|. The square is completed by (x2,y1) and (x2,y2) where x2 = x1 ± side. Multiply counts for all three corners.
Time: O(n) add, O(n) count worst case.
Space: O(n).
← Prev Category Next Category →