Array as Hash and In-Place
What is this?
These are tricky problems where the single insight is that the array can store its own bookkeeping — no extra hash map needed. Because a value can point at an index, you flip a sign, scribble a marker in a border row, or sweep once forward and once backward, and the scratch space simply vanishes. Spotting that the data can serve as its own memory is the whole trick.
💡 Fun fact: Using the sign bit of each number as a "have I seen this?" flag means you can find every duplicate in an array of size n with zero extra memory — the data structure is the data itself.
🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: When values are bounded by the array's own index range, the array can be its hash table. Flip a sign, stash a marker in the first row, or split the answer into two directional passes — and the extra space disappears.
The pattern
The trick is noticing that an element's value can point at another element's position. If values live in [1, n], then value v maps to index v-1, so you can record "I've seen v" by negating the number sitting there. The sign becomes a one-bit hash flag stored inside the data itself.
The same instinct shows up sideways: when you need scratch space for markers, reuse a border of the structure (a first row, a first column) instead of allocating a new buffer. And when you want "everything except me," you don't need division or a hash — you sweep left-to-right accumulating a prefix, then right-to-left folding in a suffix.
The unifying move is let position and order carry information so you never reach for an auxiliary map.
The problems
- Find All Duplicates in an Array — for each value
v, negate the slot at index|v|-1; if it was already negative,vis a duplicate. The sign is the seen-flag. - Set Matrix Zeroes — use the first row and first column as marker rows for which columns and rows must zero out, with one extra flag for the first column itself.
- Product of Array Except Self — one prefix pass storing the product of everything to the left, one suffix pass multiplying in everything to the right. No division.
- Increasing Triplet Subsequence — keep only the two smallest values seen so far; the moment a third larger one appears, a triplet exists. Two scalars replace any structure.
Key takeaways
- Values can index the array — when bounded, the slot a value points to is your hash cell.
- A sign is a free bit — negation marks "seen" without extra memory.
- Borrow a border — first row/column make fine marker space.
- Two passes beat one map — prefix then suffix computes "all but me" in O(1) space.
Core idea: the product of everything except
nums[i]is just (product of everything to its left) × (product of everything to its right). Compute those two running products in two sweeps — one left-to-right, one right-to-left — and you never need division, never trip over zeros, and never spend more thanO(n)time.
Problem, rephrased
You're given an array nums of n integers (with n > 1). Return a new array out where out[i] equals the product of every element of nums except nums[i].
Two hard rules from the problem (LeetCode 238):
- No division. The "lazy" answer — multiply everything once, then divide by
nums[i]— is banned. (And as we'll see, it's also wrong the moment a zero shows up.) O(n)time. No nested loop that recomputes a product for each index.
The follow-up tightens it further: solve it in constant extra space, where the output array doesn't count against you.
Picture a shop counter with prices laid out left to right. For each price, you want "the product of all the other prices" — what you'd get if you covered that one slot with your hand and multiplied the rest.
nums |
out (product except self) |
why out[0] |
|---|---|---|
[1, 2, 3, 4] |
[24, 12, 8, 6] |
2 × 3 × 4 = 24 |
[2, 3, 4, 5] |
[60, 40, 30, 24] |
3 × 4 × 5 = 60 |
[5, 1] |
[1, 5] |
everything-except-5 is just 1 |
[3, 0, 2] |
[0, 6, 0] |
the lone zero zeroes out every slot but its own |
Look at the last row: a single 0 in the input makes most outputs 0, but the slot sitting on the zero is 3 × 2 = 6 — because that slot excludes the zero. That asymmetry is exactly why naïve division blows up, and exactly what the two-sweep method handles for free.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson