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, v is 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.