Math & Geometry Essentials

Why this topic is different

Math & Geometry questions are low-frequency compared to Trees or Dynamic Programming, but interviewers reach for them specifically to probe rigor: can you handle overflow, division by zero, and off-by-one indexing without a pattern to lean on? There's no "sliding window" or "two pointers" template here — you're expected to reason from first principles about numbers and coordinates. The good news: the surface area is small. This is explicitly not a discrete math or computational geometry course — you don't need proofs, and real geometric machinery (exact convex hull implementations, computational geometry libraries) is out of scope for all but a few specialized roles.

Number theory essentials

GCD and LCM

The greatest common divisor comes up constantly as a subroutine (reducing fractions, checking divisibility relationships, normalizing slopes — see Max Points on a Line below). Don't compute it by trial division; use the Euclidean algorithm:

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a

def lcm(a: int, b: int) -> int:
    return a // gcd(a, b) * b  # divide first to reduce overflow risk

This runs in O(log(min(a, b))) — each step at least halves the smaller number (a consequence of Lamé's theorem, which ties the worst case to consecutive Fibonacci numbers). Most languages ship this in a standard library (math.gcd in Python, std::gcd in C++17+), but you should be able to derive it on a whiteboard without hesitation. For LCM, dividing by the GCD before multiplying (not a * b // gcd(a, b)) avoids an unnecessary intermediate overflow — a small detail senior interviewers notice.

Primality testing

Two distinct scenarios call for two distinct techniques:

Testing a single number n for primality → trial division up to √n. If n has a factor larger than √n, it must pair with one smaller than √n, so checking beyond that is wasted work. This is O(√n) per query.
Answering many primality queries, or finding all primes below n → precompute once with the Sieve of Eratosthenes: mark composites by walking multiples of each prime starting from p² (smaller multiples were already struck out by smaller primes).

def sieve(n: int) -> list[bool]:
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, int(n ** 0.5) + 1):
        if is_prime[p]:
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False
    return is_prime

The sieve runs in O(n log log n) — effectively linear for interview purposes. "Answer Q queries about primality" or "count primes below n" is your signal to sieve once instead of trial-dividing per query — the same amortization instinct as caching repeated work in Arrays & Hashing.

Modular arithmetic

% isn't just for "is this even" checks — it's how you keep numbers bounded when a problem says "return the answer modulo 10^9 + 7," a hint that the true answer overflows fixed-width integers. Python's arbitrary-precision integers make this a non-issue there, but apply the modulo as specified anyway — it's part of the problem contract, and the habit will bite you the moment you work in Java, C++, or Go.

Two rules to keep straight:

(a + b) % m == ((a % m) + (b % m)) % m, and the same holds for multiplication. Apply the modulo after every operation, not just at the end, or you reintroduce the overflow you were trying to avoid.
Negative modulo differs across languages. Python's % always returns a non-negative result matching the sign of the divisor (-1 % 5 == 4), while C++, Java, and JavaScript return a result matching the sign of the dividend (-1 % 5 == -1). If you're reasoning about this in an interview using C++/Java-style semantics, normalize with ((a % m) + m) % m.

Modular exponentiation (computing x^n mod m without ever materializing the full x^n) is worth recognizing even though it's rarely the crux of an interview question: square-and-halve the exponent, taking the modulo at every multiplication, for O(log n) instead of O(n).

def mod_pow(x: int, n: int, m: int) -> int:
    result = 1
    x %= m
    while n > 0:
        if n & 1:
            result = (result * x) % m
        x = (x * x) % m
        n >>= 1
    return result

This is the same halving-the-exponent idea behind Pow(x, n), and it shares its bit-shifting mechanics with the Bit Manipulation topic.

Matrix and grid manipulation

Grid problems in this topic are about index bookkeeping, not algorithmic cleverness — the traversal techniques (BFS/DFS over a grid) belong to Graphs and Trees; here the focus is rearranging a matrix in place.

Rotating a matrix 90° in place

The naive approach allocates a new matrix — O(n²) space. The interview-expected approach uses two O(1)-extra-space passes: transpose, then reverse each row (for clockwise rotation; reverse first, then transpose, for counter-clockwise):

def rotate(matrix: list[list[int]]) -> None:
    n = len(matrix)
    # Transpose: swap across the 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]
    # Reverse each row
    for row in matrix:
        row.reverse()

This is O(n²) time (every cell is touched a constant number of times) and O(1) extra space — the in-place constraint is usually stated explicitly, so don't reach for a fresh matrix out of habit.

Spiral traversal

Walk the matrix boundary-by-boundary (top row left→right, right column top→bottom, bottom row right→left, left column bottom→top), then shrink the boundary inward and repeat. Track four pointers (top, bottom, left, right) and re-check top <= bottom / left <= right before each of the four legs — this is where most bugs live, on single-row or single-column remainders. O(m·n) time, O(1) extra space beyond the output.

Transpose alone

Sometimes you just need matrix[i][j] ↔ matrix[j][i] without the reversal — as a building block for rotation, or for converting between row-major and column-major access patterns. For non-square matrices, transposing changes the dimensions, so it can't be done fully in place; you generally need a new n × m output.

Geometry essentials (the practical slice)

You are not expected to derive geometry from scratch — you're expected to correctly apply a small set of formulas and reason about edge cases.

Need	Formula / technique
Distance between two points	Euclidean: `√((x2-x1)² + (y2-y1)²)`; skip the sqrt if you only need to compare distances
Overlap of two axis-aligned rectangles	Overlap exists iff both x-ranges and y-ranges overlap: `max(0, min(x2,x4) - max(x1,x3)) > 0 and` the same for y
Area covered by two rectangles	`area1 + area2 - overlapArea` (inclusion-exclusion; clamp overlap dimensions at 0 for the non-overlapping case)
Are three points collinear?	Cross product of two edge vectors is zero: `(y2-y1)(x3-x1) == (y3-y1)(x2-x1)` — avoids computing (and comparing) floating-point slopes
Slope between two points, without floats	Reduce `(dy, dx)` by their GCD and compare the resulting pairs, rather than dividing to get a float

Convex hull — know that it exists and roughly what it computes (the smallest convex polygon enclosing a set of points, typically via Graham scan or Andrew's monotone chain, both O(n log n) dominated by the sort). A full derivation is out of scope for the large majority of interview loops — if it comes up, it's usually at a company/team with a graphics, mapping, or robotics bent — but if you want that derivation, along with its natural companion problem (closest pair of points, the other classic O(n log n) divide-and-conquer geometry algorithm), see the Closest Pair & Convex Hull subtopic below.

Numeric edge cases that actually get you

Integer overflow. In fixed-width-integer languages, a * b or intermediate sums in a formula (area, distance-squared, mid = (lo + hi) / 2) can silently overflow. The general habit: identify the largest intermediate value your formula can produce given the stated constraints, and widen the type or restructure the arithmetic (e.g., lo + (hi - lo) / 2 instead of (lo + hi) / 2) if it can exceed the type's range. Python is exempt from this class of bug entirely (integers are arbitrary precision), but don't let that make you sloppy about stating the risk out loud — the interviewer is evaluating whether you know it exists, not just whether your Python solution happens to work.
Floating-point precision. Never compare floats with ==. If a problem reduces to comparing two fractions (a/b vs c/d), cross-multiply instead of dividing: a*d vs c*b (watching for the sign of b and d first) — this keeps you in exact integer arithmetic and sidesteps precision loss entirely.
Division by zero. Any formula with a denominator (slope, normalized vectors) needs an explicit vertical/undefined case carved out before you divide.
Off-by-one in matrix index math. n - 1 - i vs n - i is the single most common source of bugs in rotation/spiral problems — verify against a tiny (2×2 or 3×3) example by hand before trusting the general formula.

Complexity cheat sheet for this topic

Technique	Time	Space
Euclidean GCD	O(log(min(a, b)))	O(1)
Trial division primality check	O(√n)	O(1)
Sieve of Eratosthenes (up to n)	O(n log log n)	O(n)
Modular exponentiation	O(log n)	O(1)
In-place matrix rotation	O(n²)	O(1)
Spiral traversal	O(m·n)	O(1) extra
Convex hull (for awareness)	O(n log n)	O(n)

How to state it in an interview

As with any topic, name the mechanism, not just the bound:

"I'm using the Euclidean algorithm here, so this reduction is O(log(min(a, b))), and I'm applying the modulo after every multiplication to avoid overflow before it happens, not after."

That single sentence signals you know why the technique is safe, which is exactly what separates a competent Math & Geometry answer from a lucky one.

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Find Greatest Common Divisor of ArrayEasy!1/510m
Rectangle OverlapEasy!2/515m
Count PrimesMedium!3/525m
Rotate ImageMedium!!3/525m
Spiral MatrixMedium!!3/530m
Pow(x, n)Medium!3/525m
Random Pick with WeightMedium!!3/530m
Random Pick IndexMedium!3/525m

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.

Max Points on a LineHard~5/550m
Water and Jug ProblemMedium~3/520m
Super PowMedium~3/525m
Common DivisorsCSES~3/525m