1
result
Most "math" problems reward spotting a closed-form shortcut — binary exponentiation, digit peeling, or cycle detection — instead of simulating the obvious loop. Master a small toolkit and the pattern recognition becomes mechanical.
A "math" problem is usually begging you to work one tiny case by hand until you spot the invariant or the closed-form pattern — and then either replace the loop with a log-time math shortcut, or simulate it carefully while reusing the input itself as your scratch space so you pay O(1) extra memory.
The brute-force version of these problems is always obvious: multiply x by itself n times, touch every digit, simulate every step. The fast version comes from noticing some structure the brute force ignores — a symmetry, an algebraic identity, or the fact that a bounded process must eventually repeat.
So the first move is never to code. It's to do the smallest non-trivial instance by handand watch what actually happens: rotate a 3×3 grid on scratch paper, expand x^4 = (x^2)^2, reverse the digits of 12. The transformation you discover by hand is the algorithm.
Rotate Image.You will never derive “rotate 90°” by staring at index formulas. Do it by hand on a 3×3 and the two moves jump out — transpose (flip across the diagonal), then reverse each row:
Goal: rotate 90° clockwise (top row should become right column)
original transpose reverse each row
(read rows) (swap a[i][j] (left<->right)
with a[j][i]) = the answer
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
Why transpose-then-reverse? Transpose flips across the main
diagonal (rows<->cols). That alone faces the wrong way, so
reversing each row mirrors it into the clockwise position.
Both steps mutate IN PLACE → O(1) extra space.Pow(x, n). Write the exponent in binary and the O(n) loop collapses to O(log n) — square the base each step, multiply it into the answer only where a bit is 1:
Compute x^13. 13 in binary = 1101 exp bit base (=x^(2^k)) result (multiply in on a 1-bit) ---- --- --------------- ------------------------------- 13 1 x result = 1 * x = x^1 6 0 x^2 (skip — bit is 0) x^1 3 1 x^4 result = x^1 * x^4 = x^5 1 1 x^8 result = x^5 * x^8 = x^13 0 -- done 13 = 8 + 4 + 1 = the 1-bits. x^13 = x^8 · x^4 · x^1. Each row SQUARES the base and HALVES the exponent: 4 steps instead of 13 multiplies → O(log n).
n times but the answer is built from powers of twoof something, there's almost always a halving / squaring shortcut hiding underneath.When a problem is about numbers, grids, or points rather than a collection you search, climb these four rungs in order:
pow(x, 3), reverse "12", spiral a 2×3. Watch what each value does — don't reach for code yet.result × base^expnever changes.” If you can't name it, keep working rung 1.O(1) extra space.%10 / //10 peels digits; a deterministic process on a bounded integer must cycle (happy number).solve(numeric problem):
1. work the SMALLEST case by hand # rotate a 2x2, pow(x,3),
on paper, no code # reverse "12": what moved?
2. name the transformation/invariant
"90deg cw = transpose + reverse row"
"result * base^exp stays constant"
3. can I avoid extra arrays? # mutate in place, or stash
reuse the input as scratch: # markers in row0/col0
first row/col as flags
4. is there a log-time shortcut? # squaring halves the work;
halve the work with math # %10 // 10 peels digits;
# bounded process -> cycleThe recurring trick for hitting O(1) extra space is encoding bookkeeping inside the input you already have. The grid is sitting right there — borrow its margins as a notebook.
Set Matrix Zeroes in O(1) space: use row 0 and col 0 as the "should this line be zeroed?" notebook — no extra arrays. 1 1 1 mark: a[i][0] and a[0][j] = 0 when a[i][j]==0 1 0 1 ──► (one extra flag tracks col 0 itself) 1 1 1 after marking (top row + left col carry the flags): 1 0 1 row 1 flagged (a[1][0]=0) 0 0 1 col 1 flagged (a[0][1]=0) 1 0 1 apply flags inward, then handle row 0 / col 0 LAST. The input IS the storage. The trick: only read a marker AFTER you've finished writing markers, never during.
0 from one you just wrote. Mark everything first, then apply, and handle row 0 / col 0 last.Every one of these algorithms has a single sentence you can say that, if true at the start of each iteration and preserved by the body, proves the loop correct. Say it before coding:
result × base^expequals the final answer at every step.” Odd exp? Multiply one factor into result to restore it.rev holds the already-peeled digits in reversed order; abs holds the digits not yet peeled.”iis final; a carry of 1 is still pending.”When no shortcut exists you simply simulate — but careful simulation is its own skill. Spiral Matrix and Rotate Image are won or lost on boundary bookkeeping, not cleverness.
top, bottom, left, right. After walking an edge, move that bound inward, and re-check top ≤ bottom and left ≤ right beforethe next pass so a thin leftover row/column isn't traversed twice.-123 % 10 is -3 in JavaScript, and Math.floor(-7 / 2) is -4, not -3. Work on Math.abs(n) and restore the sign at the end.The defining move in math problems is recognizing that a naive loop — multiply x by itself n times, process each digit, sum forever until a cycle — has a much faster closed form. The four most common shortcuts are:
O(n) multiplications to O(log n).n % 10 / floor-divide by 10 to process or reconstruct a number without converting to a string.x^n = (x^2)^(n/2) when n is even, and x^n = x · x^(n-1) when n is odd. Applying this recursively (or iteratively) halves the problem size at every step, just like binary search.After k squarings you have covered 2^k of the original exponent. So you only need log₂(n) squarings total.
Similarly, grade-school string multiplication runs O(m × n) for m- and n-digit inputs — painful, but unavoidable without FFT. Cycle detection on a numeric process costs O(n) time and O(1) extra space with Floyd (vs O(n) space for a hash set).
Geometry problems on LeetCode rarely require a full computational geometry library. The two recurring tricks are:
(x, y) as a string key or a nested map to count points or group by position in O(1) per lookup.Overflow is the geometry pitfall: distance-squared comparisons using integer coordinates can easily exceed 32-bit range — use Number (64-bit float) or promote to BigInt when products of coordinates appear.
3^13in O(log n) multiplies, not n. Read the exponent in binary (1101) from the low bit up. Square the base, halve the power.Reach for the math & geometry toolkit when the problem is about numeric structure — the digits of a number, the value of an expression, the positions of points — rather than a collection you search or sort. The tell is that simulating the obvious process would be correct but too slow.
| "compute x^n efficiently" / implement pow(x, n) | binary (fast) exponentiation — O(log n) iterative squaring |
| "process digits / reverse a number" without string conversion | mod-and-floor digit loop: peel with % 10, drop with Math.floor(n / 10) |
| "detect a repeating process / cycle" on bounded integers | hash set (O(n) space) or Floyd two-pointer (O(1) space) cycle detection |
| "increment / add to a number stored as a digit array" | right-to-left carry propagation; prepend 1 if all nines |
| "multiply two large numbers given as strings" | grade-school per-digit multiplication into a result array, then trim leading zeros |
| "count shapes / squares from a set of points" | hash map of point counts; fix a diagonal, check the two implied corners exist |
| "is this a happy number?" / any deterministic integer sequence | cycle detection on the sequence — same Floyd / hash-set pattern |
numberis a 64-bit float (safe integers up to 2⁵³), so intermediate products don't silently wrap the way Java int does — but the problem statement may still ask you to return 0 on 32-bit overflow, requiring an explicit range check.Math.floor(-7 / 2) is -4, not -3. When peeling digits from a negative number, work with the absolute value and restore the sign at the end.When → Any pow(x, n) variant. Handle negative n upfront by inverting the base; then iterate, squaring the base and halving the exponent each step.
function myPow(x: number, n: number): number {
// Handle negative exponent: x^-n = (1/x)^n
if (n < 0) { x = 1 / x; n = -n; }
let result = 1;
let base = x;
let exp = n; // iterative so stack is O(1)
while (exp > 0) {
if (exp % 2 === 1) result *= base; // odd exponent: absorb one factor
base *= base; // square the base each step
exp = Math.floor(exp / 2); // halve the exponent (floored)
}
return result; // O(log n) multiplications
}result × base^exp equals the final answer at every iteration. When exp is odd, multiply result by base to restore the invariant before halving.When → Reverse a number, sum its digits, check digit properties. Work with Math.abs(n) to avoid negative-division surprises; re-apply the sign after.
function reverseDigits(n: number): number {
// Works for negatives: keep sign, reverse magnitude
const sign = n < 0 ? -1 : 1;
let abs = Math.abs(n);
let rev = 0;
while (abs > 0) {
const digit = abs % 10; // peel the last digit
rev = rev * 10 + digit; // shift result left, append digit
abs = Math.floor(abs / 10); // drop the last digit (floored)
}
// 32-bit overflow guard (LeetCode Reverse Integer spec)
const MAX32 = 2 ** 31 - 1;
if (rev > MAX32) return 0;
return sign * rev;
}2^31 - 1(or the problem's stated bound)before returning, not inside the loop.When → The algorithm repeatedly applies a function to an integer (sum of squared digits, Collatz step, etc.) and you need to know whether it reaches a fixed point or loops. Use hash-set for simplicity; Floyd for O(1) space.
// Hash-set variant (simple, O(n) space)
function hasRepeatedState(start: number, next: (n: number) => number): boolean {
const seen = new Set<number>();
let cur = start;
while (!seen.has(cur)) {
seen.add(cur);
cur = next(cur);
if (isTerminal(cur)) return false; // reached a known fixed point
}
return true; // revisited a state → cycle
}
// Floyd variant (O(1) space)
function floydCycle(start: number, next: (n: number) => number): boolean {
let slow = next(start);
let fast = next(next(start));
while (slow !== fast) {
if (isTerminal(slow) || isTerminal(fast)) return false;
slow = next(slow);
fast = next(next(fast));
}
return true; // pointers met → cycle exists
}
declare function isTerminal(n: number): boolean;cur === 1 (happy) or cur === 4 (unhappy) without a general set.When → A number is stored as a digit array (most-significant first). Increment it or add a small value by walking right-to-left and propagating the carry. The only tricky case is all nines.
function plusOne(digits: number[]): number[] {
// Walk right-to-left, propagate carry
for (let i = digits.length - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++;
return digits; // no carry needed, done early
}
digits[i] = 0; // this digit flips 9 → 0, carry continues
}
// All digits were 9 (e.g. [9,9,9] → [1,0,0,0])
digits.unshift(1);
return digits;
}digits.unshift(1) is O(n) but unavoidable — the array genuinely grows by one slot.TypeScript number holds integers exactly up to 2^53 - 1, so products of two 32-bit values are safe. But some problems (Reverse Integer) explicitly ask you to return 0 if the result doesn't fit in a signed 32-bit integer. Check against 2^31 - 1 / -(2^31) after computing, not during.
For pow(x, n) with negative n: invert x and negate n before the main loop — do not try to handle it inside. For digit loops: always call Math.abs(n) first and track the sign separately.-123 % 10 is -3 in JavaScript, not 3.
Math.floor(-7 / 2) returns -4 (towards negative infinity), while C++/Java integer division truncates to -3 (towards zero). In the fast-exponentiation loop, expis always non-negative after the initial negation, so this doesn't bite there — but it matters whenever you floor-divide a value that could be negative mid-algorithm.
The most common Plus One bug: returning early after incrementing the last non-nine digit but forgetting to handle the leading carry. Ensure the loop runs through index 0, sets that digit to 0, and then outside the loop you prepend 1. Doing the unshift inside the loop leads to off-by-one prepends.