Matrix Moves & Digit Math

Two families, one module

This module collects problems that need no grand algorithm — just precise mechanical control. The first family is matrix choreography: moving cells around a grid in place without losing data. The second is digit math: simulating arithmetic one digit at a time, the way you did it in grade school, plus one genuinely clever speedup for powers.

Rotating a matrix: two clean moves instead of one confusing one

Rotate an n×n matrix 90° clockwise, in place. Trying to reason directly about where each cell lands — "(row, col) goes to (col, n-1-row)" — leads to four-way cyclic swaps that are easy to fumble under pressure. The clean decomposition: a clockwise rotation is a transpose followed by a horizontal mirror.

Transpose means flipping across the main diagonal: cell (i, j) swaps with cell (j, i), turning rows into columns. Then reverse each row. Watch it on real numbers:

1 2 3      transpose      1 4 7      reverse       7 4 1
4 5 6      -------->      2 5 8      each row      8 5 2
7 8 9                     3 6 9      ------->      9 6 3

Check the corners: 1 was top-left, and after both moves it sits top-right — exactly where a clockwise turn sends it. Both sub-moves are trivial in-place loops (transpose swaps only the upper triangle, j > i, or every pair double-swaps back). Counterclockwise? Transpose, then reverse each column — or equivalently reverse the rows first, then transpose. Say the decomposition out loud in an interview; it turns a fiddly index problem into two one-liners.

Spiral order: four shrinking boundary pointers

Spiral Matrix asks for the elements in clockwise spiral order. Keep four pointers — top, bottom, left, right — marking the still-unvisited rectangle. Each lap peels one ring:

1. Walk left→right along row top, then top += 1.
2. Walk top→bottom down column right, then right -= 1.
3. Walk right→left along row bottom, then bottom -= 1.
4. Walk bottom→top up column left, then left += 1.

The trap lives in steps 3 and 4: after steps 1 and 2 shrink the boundaries, the rectangle may already be empty. On a single-row matrix, step 1 consumes the row, and without a re-check, step 3 walks the same row again in reverse. So guard the two reverse passes: run step 3 only if top <= bottom still holds, and step 4 only if left <= right. Loop while both inequalities hold.

Set Matrix Zeroes: the matrix as its own scratchpad

If any cell is 0, zero out its entire row and column — in place. The obvious approach records doomed rows and columns in two boolean arrays: O(m + n) extra space. The O(1) trick: use the first row and first column as the marker arrays. Scanning the matrix, when grid[i][j] is 0, set grid[i][0] = 0 and grid[0][j] = 0 — the borders become the record.

One collision to manage: cell (0, 0) belongs to both the first row and first column, so the two markers would overwrite each other's meaning. Keep one separate boolean for "the first row (or column) itself needs zeroing". Then zero the interior based on the markers, and zero the borders last — border-first would destroy the markers before they are read.

Happy Number: arithmetic that hides a cycle

A happy number repeatedly replaces itself with the sum of the squares of its digits; happy means the process reaches 1. For 19: 1² + 9² = 82 → 68 → 100 → 1. Happy. For 2: 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 — back to 4, an endless loop.

The key observation: any number up to a few hundred digits collapses below ~810 after one step (for numbers under 1000, the max digit-square sum is 3 × 81 = 243), so the sequence lives in a small finite set — it must either hit 1 or repeat. Detect the repeat with a hash set of seen values, or — the elegant version — Floyd's fast and slow pointers on the sequence itself, treating "next value" like a linked-list pointer. If fast meets slow at anything other than 1, the number is unhappy. O(1) space, and a nice callback to cycle detection.

Carry propagation: Plus One and Multiply Strings

Plus One increments a number stored as a digit array. Walk from the least-significant end: a digit below 9 just increments — done, return. A 9 becomes 0 and the carry continues left. If you fall off the front, every digit was 9: the answer grows a digit, so return [1] + zeros.

Multiply Strings multiplies two numbers given as strings, too big for built-in integers. Grade-school method, with one indexing fact doing all the work: the product of digit i (of a length-m number) and digit j (of a length-n number) lands in result positions i + j and i + j + 1 (the carry and the unit), and the whole result fits in m + n digits. Allocate an array of m + n zeros, accumulate every digit pair into position i + j + 1, push carries into i + j, then strip leading zeros. No clever math — just disciplined indexing.

Pow(x, n): squaring instead of looping

Computing x^n by multiplying n times is O(n) — hopeless for n around 2^31. Exponentiation by squaring uses the binary form of n: 13 is 1101 in binary, so x^13 = x^8 · x^4 · x^1. Square x repeatedly (x, x², x⁴, x⁸, …) and multiply into the answer wherever n has a 1-bit:

def my_pow(x, n):
    if n < 0:
        x, n = 1 / x, -n
    result = 1.0
    while n:
        if n & 1:
            result *= x
        x *= x
        n >>= 1
    return result

O(log n) multiplications — 31 steps instead of two billion. One edge case earns points: n = -2^31. Negating it overflows a 32-bit signed int (whose max is 2^31 - 1); in Python it is harmless, but in Java/C++ you widen to a 64-bit type first, and mentioning that shows you know why.

Detect Squares: count by the diagonal

Detect Squares stores points and answers "how many axis-aligned squares include this query point as a corner?" The counting trick: a square is determined by its diagonal. For query point q, scan the stored points for any point p that is diagonal to q — meaning abs(p.x - q.x) == abs(p.y - q.y) and nonzero. Those two points fix the other two corners exactly: (q.x, p.y) and (p.x, q.y). Multiply the stored counts of those two corners (points can repeat) and add to the total. A hash map from point to count makes each query O(number of distinct stored points).

What this module trains

None of these problems asks for an algorithmic leap. They ask for: a decomposition that beats brute index-juggling (rotation), boundary discipline (spiral), reusing structure you already have (marker rows), recognizing a hidden pattern from another module (cycle detection inside arithmetic), and clean carry/index bookkeeping (digits). Interviewers use them to watch you code carefully under mild pressure — slow down, narrate the invariants, and check the degenerate inputs: single row, single column, all nines, n = 0.