21 — Math & Geometry

A grab-bag section, but three recurring themes are worth isolating:

1. In-place matrix transforms — decompose a hard operation into simple reversible steps.
2. Boundary-managed traversal — shrink four walls inward.
3. Overflow-safe arithmetic — which is what several of these problems are really testing.

Matrix coordinate identities

Memorize these. They recur far beyond this section.

// transpose: swap rows and columns
matrix[i][j]  <->  matrix[j][i]

// reverse each row (horizontal flip)
matrix[i][j]  ->   matrix[i][n - 1 - j]

// reverse each column (vertical flip)
matrix[i][j]  ->   matrix[n - 1 - i][j]

// 90° clockwise rotation
matrix[i][j]  ->   matrix[j][n - 1 - i]

// diagonals (from N-Queens, see 13)
r - c  is constant along a "\" diagonal
r + c  is constant along a "/" diagonal

// flatten a 2-D coordinate to 1-D (union-find, binary search)
index = r * cols + c;    r = index / cols;    c = index % cols;

Why n - 1 - j reverses: index 0 maps to n-1, index 1 to n-2, and so on. The n - 1 is the last valid index; subtracting the current position mirrors it.

Rotate Image — decomposition beats index juggling

Rotate an n × n matrix 90° clockwise, in place.

The direct approach computes each element's destination and performs a four-way cyclic swap. It works, but the index arithmetic is easy to get wrong under pressure.

The decomposition: rotating 90° clockwise = transpose, then reverse each row. Two trivially correct steps.

original      transpose      reverse rows
1 2 3         1 4 7          7 4 1
4 5 6    →    2 5 8     →    8 5 2
7 8 9         3 6 9          9 6 3

int n = matrix.length;

// 1. transpose — note j starts at i
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        int tmp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = tmp;
    }
}

// 2. reverse each row
for (int[] row : matrix) {
    for (int l = 0, r = n - 1; l < r; l++, r--) {
        int tmp = row[l];
        row[l] = row[r];
        row[r] = tmp;
    }
}

j = i, not j = 0. Starting at 0 would visit every pair twice — swapping (0,1)↔(1,0) and then later (1,0)↔(0,1) — returning the matrix to its original state.

This bug produces plausible-looking output and passes symmetric test cases, which makes it especially nasty. Starting j at i covers only the upper triangle, so each pair is swapped exactly once.

Counter-clockwise: transpose, then reverse each column (or reverse rows first, then transpose).

Spiral Matrix — four shrinking boundaries

Read the matrix in spiral order: right across the top, down the right side, left across the bottom, up the left side, then inward.

Track top, bottom, left, right and move each inward after its pass.

List<Integer> res = new ArrayList<>();
int top = 0, bottom = m - 1, left = 0, right = n - 1;

while (top <= bottom && left <= right) {
    for (int c = left; c <= right; c++) res.add(matrix[top][c]);     // → across the top
    top++;

    for (int r = top; r <= bottom; r++) res.add(matrix[r][right]);   // ↓ down the right
    right--;

    if (top <= bottom) {                                             // GUARD
        for (int c = right; c >= left; c--) res.add(matrix[bottom][c]);   // ← across the bottom
        bottom--;
    }
    if (left <= right) {                                             // GUARD
        for (int r = bottom; r >= top; r--) res.add(matrix[r][left]);     // ↑ up the left
        left++;
    }
}

Why the two inner guards are mandatory

Consider a single-row matrix [[1, 2, 3]]:

1. The top pass reads 1, 2, 3 — everything.
2. top++ makes top = 1, now greater than bottom = 0.
3. The right pass correctly does nothing (r starts above bottom).
4. Without the guard, the bottom pass would run matrix[bottom][c] = matrix[0][c] — re-reading the same row backwards, producing 1,2,3,3,2,1.

The guard if (top <= bottom) catches exactly this.

Single-row and single-column inputs are the test cases to name proactively — they're where this breaks.

Set Matrix Zeroes — using the matrix as its own marker storage

If any cell is 0, set its whole row and column to 0. In place.

Why the naive approach fails: if you zero a row as you find it, those new zeros look like original zeros to the rest of the scan, and everything cascades to zero.

The O(m + n) fix: record which rows and columns need zeroing in two sets, then apply them in a second pass. Correct and easy to explain — write this first.

The O(1) fix: store those flags inside the matrix itself, using row 0 and column 0 as the marker arrays.

The complication: cell [0][0] would need to serve as the flag for both row 0 and column 0. One extra scalar resolves it.

int m = matrix.length, n = matrix[0].length;
boolean firstColHasZero = false;

// PASS 1: mark
for (int r = 0; r < m; r++) {
    if (matrix[r][0] == 0) firstColHasZero = true;      // column 0 tracked separately
    for (int c = 1; c < n; c++) {                        // c starts at 1
        if (matrix[r][c] == 0) {
            matrix[r][0] = 0;                            // mark this ROW
            matrix[0][c] = 0;                            // mark this COLUMN
        }
    }
}

// PASS 2: apply, working BACKWARDS
for (int r = m - 1; r >= 0; r--) {
    for (int c = n - 1; c >= 1; c--) {
        if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
    }
    if (firstColHasZero) matrix[r][0] = 0;               // handle column 0 last for this row
}

Why pass 2 iterates backwards: row 0 and column 0 are holding the markers. If you applied zeroes top-to-bottom, you'd overwrite row 0 early — destroying the column flags that later rows still need to read.

Going backwards means row 0 and column 0 are the last things touched, after every other cell has consumed them.

Offer the O(m + n) version first, then present this as the optimization. Jumping straight here without explaining the marker idea usually reads as memorized rather than understood.

Happy Number — cycle detection in disguise

Repeatedly replace a number with the sum of the squares of its digits. Does it reach 1, or loop forever?

The reframe: the "next number" function defines a graph where each node has exactly one outgoing edge. Following it either reaches 1 or enters a cycle. That's the same machinery as Linked List Cycle (11).

private int next(int n) {
    int sum = 0;
    while (n > 0) {
        int d = n % 10;
        sum += d * d;
        n /= 10;
    }
    return sum;
}

public boolean isHappy(int n) {
    int slow = n, fast = next(n);
    while (fast != 1 && slow != fast) {
        slow = next(slow);
        fast = next(next(fast));
    }
    return fast == 1;
}

A HashSet of seen values is equally correct and easier to explain — loop until you either hit 1 or revisit a value. The two-pointer version is O(1) space.

Recognizing this as cycle detection rather than a number-theory puzzle is the point. Say it explicitly — that's the insight being tested, not the digit arithmetic.

Plus One — carry propagation

Increment a number represented as a digit array.

for (int i = digits.length - 1; i >= 0; i--) {
    if (digits[i] < 9) {
        digits[i]++;
        return digits;                  // no carry — done immediately
    }
    digits[i] = 0;                      // a 9 becomes 0 and the carry continues left
}

int[] res = new int[digits.length + 1]; // all nines: 999 -> 1000
res[0] = 1;
return res;

The early return handles the common case — most numbers don't end in 9, so you touch one digit and leave.

The all-nines case needs a longer array. 999 + 1 = 1000 has one more digit than the input, so you can't do it in place. That's the edge case to name, and the reason the extra allocation appears at all.

The new array starts zero-filled, so setting res[0] = 1 is all that's needed.

Pow(x, n) — fast exponentiation

Computing x^n by multiplying n times is O(n). Halving the exponent makes it O(log n).

The idea: x^10 = (x^5)^2. So instead of 10 multiplications, square your way up.

public double myPow(double x, int n) {
    long exp = n;                       // WIDEN FIRST — see below
    if (exp < 0) { x = 1 / x; exp = -exp; }

    double res = 1.0;
    while (exp > 0) {
        if ((exp & 1) == 1) res *= x;   // this bit is set — fold in the current power
        x *= x;                         // square for the next bit
        exp >>= 1;
    }
    return res;
}

How the binary version works: write the exponent in binary. x^13 where 13 = 1101₂ means x^8 · x^4 · x^1. The loop walks the bits, squaring x each round (so it holds x^1, x^2, x^4, x^8, …) and multiplying it into the result whenever the corresponding bit is set.

Trace x^13:

long exp = n before negating is essential

-Integer.MIN_VALUE overflows back to Integer.MIN_VALUE — there's no positive counterpart in int (03). Widening to long first gives the negation somewhere to go.

Interviewers use n = Integer.MIN_VALUE as the test case for exactly this.

The recursive form is equally acceptable:

if (exp == 0) return 1.0;
double half = myPow(x, exp / 2);
return (exp % 2 == 0) ? half * half : half * half * x;

Computing half once is the whole optimization. Writing myPow(x, exp/2) * myPow(x, exp/2) makes two recursive calls instead of one — collapsing back to O(n).

Multiply Strings — grade-school multiplication

Multiply two numbers given as strings, without converting to integers.

The key index identity: digits at positions i and j contribute to result positions i + j and i + j + 1.

      1 2 3        (indices 0,1,2)
    ×   4 5        (indices 0,1)

Multiplying num1[i] by num2[j] gives at most a 2-digit product, whose tens digit lands at i + j and units digit at i + j + 1.

if (num1.equals("0") || num2.equals("0")) return "0";

int m = num1.length(), n = num2.length();
int[] res = new int[m + n];                      // the product has at most m + n digits

for (int i = m - 1; i >= 0; i--) {
    for (int j = n - 1; j >= 0; j--) {
        int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
        int p1 = i + j, p2 = i + j + 1;
        int sum = mul + res[p2];                 // add into whatever is already there

        res[p2] = sum % 10;                      // units digit stays
        res[p1] += sum / 10;                     // += , NOT = — carries accumulate
    }
}

StringBuilder sb = new StringBuilder();
for (int d : res) {
    if (sb.length() == 0 && d == 0) continue;    // skip leading zeros
    sb.append(d);
}
return sb.length() == 0 ? "0" : sb.toString();

Three details:

1. m + n sizing — the product of an m-digit and an n-digit number has at most m + n digits.
2. res[p1] += not = — multiple digit pairs contribute carries to the same position. Overwriting would lose them.
3. Strip leading zeros at the end — the "0" early return prevents the stripping loop from producing an empty string.

Detect Squares — counting with a point map

Add points; query how many axis-aligned squares can be formed with a given point as one corner.

The approach: for a query point (px, py), iterate over stored points that could be the diagonal partner. A valid diagonal partner (x, y) satisfies |px - x| == |py - y| (equal side lengths) and is not on the same row or column.

Given the query point and its diagonal, the other two corners are determined: (px, y) and (x, py). Multiply how many of each exist.

private final Map<Long, Integer> count = new HashMap<>();   // encoded point -> multiplicity
private final List<int[]> points = new ArrayList<>();

private long key(int x, int y) { return ((long) x << 32) | (y & 0xFFFFFFFFL); }

public void add(int[] point) {
    points.add(point);
    count.merge(key(point[0], point[1]), 1, Integer::sum);
}

public int count(int[] point) {
    int px = point[0], py = point[1];
    int total = 0;

    for (int[] p : points) {
        int x = p[0], y = p[1];
        if (Math.abs(px - x) != Math.abs(py - y) || px == x || py == y) continue;   // not a diagonal

        total += count.getOrDefault(key(px, y), 0)      // the other two corners
               * count.getOrDefault(key(x, py), 0);
    }
    return total;
}

Two mechanics:

1. px == x || py == y must be excluded. Without it, a point on the same row or column would pass the abs test when both differences are 0 — counting degenerate "squares" of zero area.

2. Encoding a 2-D point into one long avoids a nested map or string keys. Shift x into the high 32 bits and OR in y.

The & 0xFFFFFFFFL mask matters: without it, a negative y would sign-extend into the high bits and corrupt the encoded x.

add is O(1); count is O(n) in the number of stored points.

Overflow and precision — the recurring theme

long product = (long) a * b;              // cast BEFORE multiplying
int mid = lo + (hi - lo) / 2;             // never (lo + hi) / 2
long exp = Math.abs((long) n);            // never Math.abs(Integer.MIN_VALUE)
(a + b - 1) / b                           // integer ceiling for non-negative a, b
Math.floorDiv(a, b)                       // floors toward -infinity; / truncates toward 0

Avoid floating point for exact comparisons

• Comparing distances? Compare squared distances — squaring is monotonic on non-negative values, so the ordering is identical (14).
• Need a ceiling? Use (a + b - 1) / b, not Math.ceil on a double.

Why: double has 53 bits of precision. Above 2^53 it cannot represent consecutive integers exactly, so comparisons and rounding produce off-by-one bugs that only surface on large inputs.

Recognition checklist

Complexity summary