Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Book a call

Coding · Arrays and hashing

The array as its own table

Lesson · 10 min read · Arrays and hashing · The array as its own table

When you're told to use O(1) extra space, the array you were given can be the table. A value's index becomes its key.

When there is no room for a map

All of the earlier modules in this chapter leaned on a map or a set, and that costs O(n) memory. Now and again you'll be told you can't have it: O(n) time, O(1) extra space, and you're allowed to change the array. That last part's the clue. If we can't build a table next to the array, we'll have to use the array itself as one.

That only works if the values can be turned into indices. So the first step is always the same one: work out which values can affect the answer, and check there are no more of them than there are slots.

Bounding the answer first

Take the smallest positive integer that's missing from an array of length n. If all of 1, 2, …, n are there, they fill the n slots between them and the answer is n + 1. If one of them isn't there, the answer's at most n. Either way it's somewhere from 1 to n + 1, so zeros, negatives and anything bigger than n can't change it, and we can ignore them.

That leaves us with values from 1 to n and an array with n slots, which is all we need for a table where value v lives at index v − 1.

Sending each value home

We walk the array, and while the slot we're looking at holds a value v from 1 to n that isn't already at home, we swap it into slot v − 1. Then we look at whatever came back from the swap. A loop inside a loop looks quadratic, but a swap puts one value in its right place for good, so there can't be more than n swaps over the whole run.

Place, then read

firstMissing(nums)

  1. For i from 0 to n − 1: while nums[i] = v with 1 ≤ v ≤ n and nums[v − 1] ≠ v, swap nums[i] and nums[v − 1].
  2. For i from 0 to n − 1: if nums[i] ≠ i + 1, return i + 1.
  3. Return n + 1.

Look closely at the swap condition. It checks that the target slot doesn't already hold v, which is a stronger test than asking if v is out of place. If you used the weaker one, two copies of a value would keep swapping with each other for ever.

The smallest missing positive in [3, 4, -1, 1].

  1. Step 1 / 7
    nums
    3041-1213
    n4

    n = 4, so the answer is somewhere in 1..5. Only values 1..4 matter: put each value v in slot v − 1.

  2. Step 2 / 7
    nums
    -10i413213
    i0placed3

    Slot 0 holds 3, which belongs in slot 2. Swap it home.

  3. Step 3 / 7
    nums
    -10i413213
    i0

    Slot 0 holds -1, outside 1..4. It cannot be the answer's evidence either way; leave it.

  4. Step 4 / 7
    nums
    -1011i3243
    i1placed4

    Slot 1 holds 4, which belongs in slot 3. Swap it home.

  5. Step 5 / 7
    nums
    10-11i3243
    i1placed1

    Slot 1 holds 1, which belongs in slot 0. Swap it home.

  6. Step 6 / 7
    nums
    10-11i3243
    i1

    Slot 1 holds -1, outside 1..4. It cannot be the answer's evidence either way; leave it.

  7. Step 7 / 7
    nums
    10-113243
    answer2

    Read left to right: slot 1 should hold 2 and does not. Answer 2.

Marking with a sign

There's a second way to use the array as a table, and you'll see it in a lot of solutions. First we overwrite anything that's out of range (zero, negative, or bigger than n) with n + 1, so all of the values are positive. Then for each value v with |v| from 1 to n, we make nums[|v| − 1] negative. The sign of a slot is now the bit that says "present", and the size of the number is still there for us to read. The first slot that's still positive gives the answer, and if there isn't one, it's n + 1.

I'd show the swapping version in an interview because it's easier to trace on paper. The sign version is worth knowing as well, since it works when the values need to stay where they are, as long as you're allowed to put the signs back afterwards.

TimeO(n)
SpaceO(1) extra

Both versions change the input. If you're told not to touch it, O(1) extra space isn't possible this way, and you should say so.

Problems in this module