Math, Matrix & Heaps

The core idea

A mixed cluster of problems that share a flavour rather than a single algorithm. Three sub-patterns live here:

Digit / number tricks: arithmetic on arrays of digits, base conversions, parsing.
Matrix walks: iterating a 2-D grid in a specific order (spiral, layered, transposed).
Heap problems: top-K and stream problems where you need the smallest or largest at each step.

A heap is a priority queue: insert and extract-extreme in O(log n). Use a min-heap of size K to track the top-K largest items in O(n log K) without sorting the whole stream.

When to reach for it

Trigger phrases for the three sub-patterns:

"without converting to integer", "digit-by-digit"
"rotate the matrix", "spiral order", "transpose"
"top k", "kth largest", "smallest k closest", "merge k sorted streams"

How to approach

For digit problems: be deliberate with the loop direction. Carry propagates from right to left; iterate accordingly.

For matrix walks: track the four boundaries (top, bottom, left, right). Update them as you peel a layer.

For heap problems: decide direction first. Top-K largest → min-heap of size K. Top-K smallest → max-heap (in Python, push negatives). Median of a stream → two heaps, one of each polarity.

Enterprise scenarios

Spotify "Discover Weekly": top-K recommended tracks per user; heap-based selection over a candidate pool of millions.
Twitter / X feed ranking: top-K most engaging tweets per timeline, refreshed on demand.
Cloudflare top-IP-by-traffic monitoring: streaming top-K via a fixed-size heap.
Google Maps "k closest restaurants": heap of points by distance to the query.
Datadog and Grafana alerting: median, p95, p99 latency over streams uses heap-based approximations or t-digests.
Image rotation in Photoshop, Figma, Lightroom: rotate-image at the pixel level uses the same transpose + reverse trick.
Number formatting in fintech (Stripe, PayPal, banks): digit-by-digit conversion to handle precision (no float arithmetic on money).
OCR / form parsers: scanning digit arrays from images uses plus-one-style carry logic.

In the AI-integrated workspace

Two pitfalls for AI-generated code in this cluster:

For matrix walks, agents will frequently mix up (row, col) vs (x, y) and the rotation will be transposed or mirrored. Always test with a non-square 3×4 matrix; the bug shows up immediately.

For heap problems, the agent's default mistake is using the wrong heap polarity. Python's heapq is a min-heap; to track the K largest, you push and pop from a min-heap (the smallest gets evicted when a new larger one arrives). Agents often write a max-heap solution (push negatives) when a min-heap was simpler. Verify by stating the invariant in code: "after each insert, the heap contains the K largest seen so far".

For digit arithmetic (money, OCR, version numbers), insist that the agent does not convert to int and back. Floating-point error in money calculations is one of the costliest classes of production bug. Stripe, Adyen, and every payment processor uses integer arithmetic with explicit base-100 (or base-1000) for cents.

Problems in this cluster

Easy: plus-one, roman-to-integer, longest-common-prefix, implement-strstr. Medium: spiral-matrix, rotate-image, k-closest-points-to-origin, kth-largest-element.

Start with plus-one. It is the warm-up for thinking about digits as arrays, which transfers to most of the rest.