Free Arrays lessonsArrays · Stage 6 · Arrays and hashing · Step 4

Ask the set in order

Find the smallest positive number that isn't in the list. About 7 minutes.

Ask 1, then 2, then 3

Think of raffle tickets numbered 1, 2, 3 and so on. Some have been sold, and you want the lowest number still left. You'd check 1, then 2, then 3, and stop at the first one nobody has.

Asking "is it in the array?" by walking the array each time is slow. So build a set once. Then each question is a single quick lookup.

Build the set once: then every question is instant.

nums = [3, 4, -1, 1] · asking 1, 2, 3, … in order

ask

seen: {3, 4, -1, 1}

First, drop everything into a set: {3, 4, -1, 1}. Now each question is one lookup. The row shows the numbers we might ask about.

Move 1 of 4

The answer is never far away

How long can the questions go on? An array of n numbers can cover at most n of the tickets 1 to n + 1, so at least one of those is missing. You'll always stop by n + 1.

Negative numbers, zeros and repeats don't use up any of those tickets, so they can only make the answer come sooner.

At most n + 1 questions: n numbers can't fill n + 1 slots.

In code

seen = set(nums)
answer = 1
while answer in seen:
    answer += 1
return answer

Quick check

What's the smallest positive number missing from 2, 3, 1, 5?

Show the answer

4. 1, 2 and 3 are there; 4 is the first one missing.

Your problem

Smallest missing positive

You get a list of whole numbers, possibly negative or repeated. Return the smallest positive whole number (1, 2, 3, …) that does not appear in it.

Example

nums = [3, 4, -1, 1] → 2

0 ≤ n ≤ 1,000,000 · −1,000,000,000 ≤ each value ≤ 1,000,000,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.