Math & Geometry Pattern

CodingMid2 min read · 8 problemsUpdated Nov 11, 2026

Work from the structure of numbers and coordinates: index formulas for matrices, digit arithmetic with carries and overflow checks, repeated squaring for powers, and coordinate lookups for shapes.

When to Use It

Matrix traversal and in-place transforms (spiral order, rotation, zeroing rows and columns), arithmetic on digit arrays or strings, integer reversal within 32-bit limits, fast powers, and counting axis-aligned shapes from points.

Classic example: Rotate Image; Pow(x, n).

How It Works

Matrix problems are index arithmetic, so write down where cell (r, c) goes before writing any loops. A clockwise rotation sends (r, c) to (c, n - 1 - r), which factors into a transpose (swap (r, c) with (c, r) for every c > r) followed by reversing each row, both in place. Spiral order keeps four boundaries, top, bottom, left, and right, and moves one inward after each side, with a check before the return trips so a leftover single row or column isn't read twice. Set Matrix Zeroes records first and clears second, using the first row and column as marker arrays to reach O(1) extra space. In every case, decide which cells must be read before they're overwritten.

Digit problems replay grade-school arithmetic. Plus One and Add Two Numbers walk from the least significant digit with a carry, and Multiply Strings sends the product of digits i and j to positions i + j and i + j + 1 of an array of length m + n. Reverse Integer pops digits with x % 10 and x / 10 and pushes them with result * 10 + digit, and the real question is overflow: compare result against (2^31 - 1) / 10 before multiplying, because after the multiply a 32-bit value has already wrapped. Languages also differ on negative operands. Java's % and / truncate toward zero while Python's floor, so -7 / 2 is -3 in Java and -7 // 2 is -4 in Python.

Exponentiation by squaring computes x^n with O(log n) multiplications: square the base at each step and multiply it into the result whenever the current bit of n is 1. The same loop with % m gives modular powers, and with matrices it gives Fibonacci numbers in O(log n). For geometry, prefer exact integer math: compare squared distances, use cross products for orientation, and identify shapes by their coordinates. Detect Squares fixes the corner diagonally opposite the query, which pins down the other two corners, and multiplies point counts from a hash map. Comparing floating-point results with == is almost always a bug.

Key Insight

Most of these problems reduce to one exact formula: where a cell moves, which position a digit product lands in, or which corners a square needs. Derive it on a small example first, then guard the two places bugs live: values overwritten before they're read, and integers that overflow before you check them.

Worked Example

Pow(x, n)

x = 3, n = 13

n = 13 (binary 1101), lowest bit 1: result = 1 * 3 = 3, then square the base to 9
n = 6 (binary 110), lowest bit 0: result stays 3, then square the base to 81
n = 3 (binary 11), lowest bit 1: result = 3 * 81 = 243, then square the base to 6561
n = 1 (binary 1), lowest bit 1: result = 243 * 6561 = 1594323, and n drops to 0

Result: 1594323, which is 3^13. One step per bit of 13 makes four steps, where multiplying by 3 repeatedly takes twelve multiplications.

Templates

// Matrix: work out where (r, c) goes, then move cells in place.
// Rotate 90 degrees clockwise = transpose, then reverse each row.
for (int r = 0; r < n; r++) {
    for (int c = r + 1; c < n; c++) { // one triangle only
        int t = grid[r][c];
        grid[r][c] = grid[c][r];
        grid[c][r] = t;
    }
}
for (int[] row : grid) {
    for (int i = 0, j = n - 1; i < j; i++, j--) {
        int t = row[i];
        row[i] = row[j];
        row[j] = t;
    }
}

// Fast power: O(log n) multiplications.
long e = n; // widen before negating
if (e < 0) {
    x = 1 / x;
    e = -e;
}
double result = 1.0;
while (e > 0) {
    if ((e & 1) == 1) result *= x;
    x *= x;
    e >>= 1;
}

// Digit push with an overflow check before the multiply.
if (acc > (Integer.MAX_VALUE - digit) / 10) return 0;
acc = acc * 10 + digit;

# Matrix: work out where (r, c) goes, then move cells in place.
# Rotate 90 degrees clockwise = transpose, then reverse each row.
for r in range(n):
    for c in range(r + 1, n):  # one triangle only
        grid[r][c], grid[c][r] = grid[c][r], grid[r][c]
for row in grid:
    row.reverse()

# Fast power: O(log n) multiplications.
if n < 0:
    x, n = 1 / x, -n
result = 1.0
while n:
    if n & 1:
        result *= x
    x *= x
    n >>= 1

# Digit push with an overflow check before the multiply.
# Python ints never overflow, so enforce the 32-bit limit explicitly.
LIMIT = 2**31 - 1
if acc > (LIMIT - digit) // 10:
    return 0
acc = acc * 10 + digit

Common Pitfalls

Overwriting matrix cells you still need: transposing the full square, so each pair swaps twice and nothing changes, or clearing rows during the same scan that finds the zeros.
Checking for overflow after result * 10 + digit has run. In a 32-bit int the value has already wrapped and can look valid.
Negating n = -2^31 in a 32-bit int, which overflows back to -2^31. Widen to 64 bits before negating.
Assuming % and / behave the same on negative numbers in every language. Python floors, while Java and C truncate toward zero.
Comparing floating-point values with ==, or taking square roots for distances, when squared integer distances answer the question exactly.

When It Breaks

Each formula assumes the shape the problem states. The in-place rotation needs a square; for an m x n matrix, write the rotated result into a new n x m matrix.
Floating point can't represent most decimals exactly, so answers that must be exact, like money or large integer powers, need integer or decimal arithmetic.
Squaring cuts the number of multiplications to O(log n), but without a modulus the numbers themselves keep growing, and each big-integer multiplication gets slower as the digits pile up.

Variations

Matrix transforms: Rotate Image (transpose, then reverse each row), Spiral Matrix (four shrinking boundaries), and Set Matrix Zeroes (first row and column as markers).
Digit arithmetic: Plus One, Multiply Strings, Add Binary, and Add Two Numbers on linked lists.
Overflow-safe integer work: Reverse Integer, String to Integer (atoi), and Divide Two Integers.
Repeated squaring: Pow(x, n), modular exponentiation, and matrix powers for linear recurrences.
Coordinate geometry: Detect Squares, Max Points on a Line (slopes as reduced integer fractions), and rectangle overlap.

Big O

Time: O(m * n) matrix, O(log n) power
Space: O(1)

Matrix walks and in-place transforms touch each cell a constant number of times with a few index variables. Exponentiation by squaring halves the exponent at each step, so it needs O(log n) multiplications. Digit arithmetic is linear in the number of digits, except schoolbook multiplication, which is O(m * n) time with an O(m + n) result array.

Next PatternSliding Window