Math & Matrix Tricks

Math and matrix problems rarely need a clever data structure. Each one usually hinges on a single insight: rotate by transposing and reversing, subtract one before converting to a base with no zero digit, check for overflow before multiplying. This note groups those insights by kind so you can recognize them quickly.

Matrix traversal and in-place transforms#

Matrix problems are mostly about index bookkeeping. Get the boundaries right and the code is short. Four moves cover most of them.

Transpose#

Transposing turns row r into column r, so res[c][r] = matrix[r][c]. A non-square R × C matrix needs a new C × R result. A square matrix can be transposed in place by swapping matrix[i][j] with matrix[j][i] for j > i only; swapping every pair would undo each swap.

Rotate 90 degrees#

Rotating clockwise is a transpose followed by reversing each row. The transpose turns rows into columns, and the reversal fixes the left-right orientation. For counter-clockwise, transpose and then reverse each column (or reverse the row order). The in-place transpose works only because the matrix is N × N.

Spiral order#

Keep four boundaries: top, bottom, left and right. Walk the top row and move top down, walk the right column and move right in, then walk the bottom row and the left column. The last two walks need guards: when only one row or one column is left, the bottom-row walk would re-read the top row, and the left-column walk would re-read the right column.

Markers inside the matrix#

Recording rows and columns in two sets costs $O(m + n)$ . To get $O(1)$ extra space, store the markers in the matrix itself: in its first row and first column, or in a spare bit of each cell. Read every old value before you overwrite anything you still need.

Template#

The in-place clockwise rotation and the spiral walk are both pure index bookkeeping. Here's the rotation first:

rotate N x N clockwise:
    for i from 0 to n - 1:
        for j from i + 1 to n - 1:     # upper triangle only
            swap matrix[i][j] and matrix[j][i]
    reverse each row

And here's the spiral walk, with the two guards from above:

top, bottom, left, right = matrix edges
while top <= bottom and left <= right:
    walk the top row left to right, then top += 1
    walk the right column top to bottom, then right -= 1
    if top <= bottom:              # a row is still left
        walk the bottom row right to left, then bottom -= 1
    if left <= right:              # a column is still left
        walk the left column bottom to top, then left += 1

Digit arithmetic and overflow#

The second group of problems works on numbers instead of grids. These problems process a number one digit at a time, the way you would on paper.

Peel digits with n % 10 (the last digit) and n // 10 (the rest).
Carry from the end. Walk from the last digit. As soon as there is no carry left, stop.
Repeated digit maps either reach a fixed point (a number that maps to itself) or fall into a cycle, so cycle detection applies.
Fixed-width limits. With a 32-bit limit, check for overflow before result * 10 + digit, because afterward it is too late.
Grade-school multiplication. Digit i of one number times digit j of the other lands at positions i + j and i + j + 1 of the result array.

Number bases#

Base conversion uses the same peel-a-digit loop, with one twist to watch for. A normal base-26 conversion uses the digits 0..25. Some systems start at 1 and have no zero digit (A = 1, …, Z = 26, AA = 27). This is called bijective base 26. Subtract 1 from n before each % 26 and // 26, so A..Z map to 0..25. The loop looks like this:

out = empty list
while n > 0:
    n -= 1                       # shift 1..26 down to 0..25
    append the letter for n % 26 to out
    n //= 26
return out reversed

GCD and string periodicity#

The last insight connects strings to number theory. Two strings are built from a common repeating unit exactly when a + b == b + a. If that holds, the longest common unit has length gcd(len(a), len(b)). The same concatenation comparison also works as a sort key: put a before b when a + b > b + a. Python's math.gcd runs Euclid's algorithm in $O(\log \min(a, b))$ .

Pitfalls#

These are the mistakes that most often cost a correct answer.

Transposing the whole square. Swapping for every (i, j) swaps each pair twice and leaves the matrix unchanged. Loop over j > i only.
Spiral double reads. Without the two guards, a single remaining row or column is read twice.
Bijective base off-by-one. Taking n % 26 without subtracting 1 first maps Z to digit 0 and breaks every multiple of 26.
Overflow checked too late. In a fixed-width setting, compare against the limit before multiplying by 10.
Markers clobbering themselves. When the first row and column hold markers, remember whether they had their own zeros before you write into them.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Rotate Image and Spiral Matrix.

Matrix#

Digits and overflow#

Bases, GCD and number theory#

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Transpose Matrix

The matrix may not be square, so build a new C × R result with res[c][r] = matrix[r][c].

Hint: Rotate Image

Transpose in place over the upper triangle, then reverse each row. That is a clockwise turn.

Hint: Spiral Matrix

Use the four-boundary walk. The two guards matter when one row or one column is left.

Hint: Set Matrix Zeroes

Use the first row and first column as markers. First note whether they contain a zero themselves. Then mark matrix[i][0] and matrix[0][j] for every other zero cell, and zero every inner cell whose row or column marker is zero. Zero the first row and column last, if your first note says so.

Hint: Game of Life

Every cell must update from the old board. Store the next state in a spare bit of each cell (for example bit 1), then shift every cell right by one at the end.

Hint: Plus One

Walk from the last digit with a carry of 1. As soon as a digit becomes less than 10, stop and return. If the carry survives the whole array (all 9s), insert a 1 at the front. Converting to an int and back works in Python, but it misses the point of the problem.

Hint: Happy Number

Replace n with the sum of the squares of its digits, again and again. The sequence either reaches 1 or falls into a cycle. Detect the cycle with a seen set, or with Floyd's fast and slow pointers in $O(1)$ space (see Fast/Slow & Gap Pointers).

Hint: Reverse Integer

Peel digits from the end and build the result. The answer must fit in 32 bits, so check for overflow before result * 10 + digit. String to Integer (atoi) uses the same check.

Hint: Palindrome Number

Reverse only the second half of the digits and compare it with the first half. You need no string conversion, and the half can't overflow.

Hint: Multiply Strings

Use an int array of length len(a) + len(b). Digits i and j contribute to result[i + j] and result[i + j + 1], exactly like grade-school multiplication.

Hint: Roman to Integer

Add each symbol's value. Subtract it instead when a smaller symbol comes before a larger one (IV, XC).

Hint: Excel Sheet Column Title

Excel columns are bijective base 26: there is no zero digit. Do n -= 1 before each % 26 and // 26.

Hint: Greatest Common Divisor of Strings

First check str1 + str2 == str2 + str1. If the concatenations differ, the answer is empty. If they are equal, the answer is the prefix of length gcd(len(str1), len(str2)).

Hint: Largest Number

Sort the numbers as strings with the comparator a + b versus b + a. Watch the all-zeros input, which should give "0".

Hint: Insert Greatest Common Divisors in Linked List

Walk the list and, between each pair of neighbors, splice in a new node holding math.gcd of the two values.

Hint: Count Primes

Use the Sieve of Eratosthenes. Start marking each prime p at p * p, since smaller multiples are already marked.

Hint: Pow(x, n)

Use binary exponentiation: square the base and halve the exponent, in $O(\log n)$ . For negative n, use 1 / x and -n.

Hint: Next Permutation

Find the rightmost ascent. Swap its left value with the next larger value to its right, then reverse the suffix.

Hint: Robot Bounded in Circle

Simulate the instructions once. The robot is bounded if it is back at the origin, or if it is not facing north.

Key takeaways#

Rotate clockwise = transpose + reverse each row; transpose a square in place over the upper triangle only.
Spiral order is four shrinking boundaries, with guards for a last single row or column.
Process numbers digit by digit, and stop early once the carry is gone.
Bijective bases (Excel columns) need n -= 1 before each division step.
a + b == b + a tests for a common repeating unit; the same comparison orders Largest Number.

Core idea#

Math and matrix problems rarely need a clever data structure. Each one hinges on a single insight, such as transpose plus reverse, or subtract one before a base conversion.

Key points#

Rotate clockwise: transpose, then reverse each row. Counter-clockwise: transpose, then reverse the row order.
Transpose a square in place over j > i only. A non-square matrix needs a new C × R result.
Spiral order: four shrinking boundaries, with guards for a last single row or column.
Set Matrix Zeroes in $O(1)$ space: use the first row and column as markers. Record their own zeros first.
Game of Life: store the next state in a spare bit, then shift every cell right.
Check 32-bit overflow before result * 10 + digit.
Excel columns are bijective base 26. Do n -= 1 before each % 26 and // 26.
a + b == b + a tests for a common repeating unit. The GCD string is the prefix of length gcd(len(a), len(b)).

One-line insights#

Problem	Insight
Plus One	Carry from the end; stop once a digit is below 10; all 9s add a leading 1
Happy Number	Cycle check with a `seen` set or fast and slow pointers
Palindrome Number	Reverse only the second half of the digits
Multiply Strings	Digits `i`, `j` land at `i + j` and `i + j + 1`
Count Primes	Sieve; start marking at `p * p`
Pow(x, n)	Binary exponentiation, $O(\log n)$ ; negative `n` uses `1 / x`
Next Permutation	Rightmost ascent, swap with next larger, reverse suffix
Largest Number	Sort by `a + b` versus `b + a`
Robot Bounded	Bounded if back at origin or not facing north

Template#

rotate N x N clockwise:
    for i from 0 to n - 1:
        for j from i + 1 to n - 1:     # upper triangle only
            swap matrix[i][j] and matrix[j][i]
    reverse each row

bijective base 26:
    while n > 0:
        n -= 1                         # 1..26 becomes 0..25
        append the letter for n % 26
        n //= 26
    return the letters reversed

Pitfalls#

Transposing the whole square. Each pair swaps twice and nothing changes.
Spiral without the guards. A last row or column is read twice.
n % 26 without subtracting 1. Every multiple of 26 breaks.
Overflow checked after the multiply.
Set Zeroes markers that overwrite the first row's own zero information.

Say it in an interview#

"Rotate clockwise is transpose, then reverse each row."
"Excel columns have no zero digit, so subtract one before each step."