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.
Set Matrix Zeroes
Core idea: When a cell is
0, its entire row and column must become0. The trap is that the moment you start zeroing, you can no longer tell which zeros were original and which you just wrote. So separate the work into two phases: first scan and remember which rows and columns need clearing, then go back and apply. The clever part is where you store those memos — instead of two extra arrays, reuse the matrix's own first row and first column as the marker storage, guarding those two lines themselves with a pair of boolean flags.
Problem, rephrased
You're handed an m × n grid of integers — picture a spreadsheet, or a screen of pixels. Somewhere in it sit some zeros. The rule: any cell that holds a 0 "infects" its entire row and entire column, turning every cell in that crosshair to 0 as well.
Do it in place — mutate the grid you were given, returning nothing — and aim for O(1) extra space: no allocating a second copy of the grid, no per-row/per-column scratch arrays. Just the matrix itself and a couple of scalar variables.
The subtlety: this is not "wherever there's a zero, paint a plus sign as you go." If you zero a row the instant you see a 0, those freshly written zeros look identical to original zeros, and the next cell in that row will spuriously infect its column too — a cascade that wipes the whole grid. You must decide what to clear based only on the original contents.
| Input matrix | Output matrix | Why |
|---|---|---|
[[1,1,1],[1,0,1],[1,1,1]] |
[[1,0,1],[0,0,0],[1,0,1]] |
the single 0 at (1,1) clears row 1 and column 1 |
[[1,2,3],[4,5,6]] |
[[1,2,3],[4,5,6]] |
no zeros, grid is untouched |
[[0,1],[1,1]] |
[[0,0],[0,1]] |
the 0 at (0,0) clears row 0 and column 0 |
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