Math & Geometry

Math & Geometry problems don't share one data structure the way graphs or intervals do — what actually unites them is a mindset: decompose a problem that looks 2D, huge, or overflow-prone into a smaller, well-understood operation you already trust. A matrix rotation becomes two simpler in-place transformations. A rectangle-overlap check becomes two 1D interval checks. A number too big for any built-in type becomes digit-by-digit arithmetic on an array. And almost every "obvious" numeric trick here has a genuine overflow trap lurking in it that a naive C++ implementation walks straight into.

In-place matrix transformations: decompose, don't derive

Rotate Image looks like it needs careful index arithmetic to map each cell to its rotated position — but it's actually two operations you already understand, composed: transpose the matrix (flip across the main diagonal), then reverse every row. Set Matrix Zeroes has the same flavor: rather than deriving a clever in-place zeroing scheme from scratch, it reuses the matrix's own first row and first column as marker storage, exactly the way you'd use any other O(1)-space scratch area. Spiral Matrix is the one case here that's genuinely a direct simulation — four shrinking boundaries (top, bottom, left, right), walked in order — but even there, the subtlety is a boundary-guard problem, not an algorithmic one.

Overflow safety: promote before the risky operation, never after

Pow(x, n), Reverse Integer, and Palindrome Number all share one discipline: the moment an operation might overflow a 32-bit int, promote to a wider type before doing that operation, not after it's already happened. Pow(x, n) negates its exponent — but n == INT_MIN has no positive int representation, so the exponent must be promoted to long long first. Reverse Integer accumulates its reversed digits in long long, checking against INT_MIN/INT_MAX only at the very end. Palindrome Number sidesteps the whole problem by only ever reversing half the digits — since the reversed half can never approach the range where overflow would even be possible.

Positional notation, generalized: base-26 and long multiplication

Excel Sheet Column Number is base-10 string-to-integer conversion wearing a disguise — base 26 instead of base 10, with a +1 offset per digit since there's no symbol for "zero" in spreadsheet column letters. Multiply Strings generalizes the same positional-arithmetic instinct in the other direction: instead of converting huge digit strings into a built-in integer type (which would overflow immediately), it performs grade-school long multiplication directly on a result array, exploiting the fact that multiplying digit i by digit j always contributes to fixed positions i+j and i+j+1 in the output — no manual digit alignment required.

Number theory at scale: sieve instead of per-number checks

Count Primes is the clearest lesson in this topic on why per-element correctness isn't enough — an algorithm's shape has to match the scale of its input. Checking each number below n for primality individually costs roughly O(n·√n), which is billions of operations once n reaches into the millions. The Sieve of Eratosthenes flips the question: instead of asking "is this number prime?" one at a time, mark every multiple of each prime as composite, starting from p*p (every smaller multiple already got marked by a smaller prime factor) — bringing the total cost down to O(n log log n), which is what actually makes the large-n case tractable.

Geometry as decomposed 1D checks

Rectangle Overlap turns a 2D shape question into two independent 1D interval-overlap checks — do the x-ranges overlap and do the y-ranges overlap — with strict inequality being exactly what excludes edge-touching and corner-touching from counting. Max Points on a Line takes the same "reduce to something exact" instinct further: instead of computing floating-point slopes (which accumulate rounding error and can wrongly split truly-collinear points into separate buckets), it represents each direction as a reduced, sign-canonicalized integer pair — dividing by the GCD of the deltas, then normalizing sign so a direction and its exact opposite always hash to the same bucket.

Common mistakes

• Negating INT_MIN as a plain int — its magnitude has no positive int representation; promote to a wider type first, in Pow(x, n) and anywhere else a sign flip is involved.
• Reversing digits directly in int — Reverse Integer's whole point is that the reversed value can exceed the 32-bit range mid-computation; accumulate in long long and check bounds only at the end.
• Forgetting Spiral Matrix's second-half boundary guards — without top <= bottom / left <= right checks, single-row or single-column remainders get some cells visited twice.
• Comparing floating-point slopes for exact collinearity — Max Points on a Line needs an exact integer representation (reduced, sign-canonicalized (dx, dy) pairs), not floating-point division, or truly collinear points can wrongly end up in different buckets.
• Reaching for a per-number or per-element check when the problem's scale demands a batch technique — Count Primes' naive per-number trial division and Rotate Image's "derive the rotated index directly" both look reasonable until you notice a simpler, composed operation (a sieve; transpose-then-reverse) is both easier to get right and asymptotically faster.