First Missing Positive
Find the lowest raffle ticket nobody has claimed. Tickets are numbered 1, 2, 3, and so on, and nums holds the numbers on the stubs you collected. The pile is messy: it can hold zeros, negative numbers, repeats, and numbers far beyond any ticket that was printed. Return the smallest positive whole number that appears nowhere in nums. Limits: 1 to 500,000 numbers, each from -2,147,483,648 to 2,147,483,647. Think about: how big can the answer be for a pile of n numbers? Example (stubs 6, 2, -4, 1, 2, 3, 0, 5): 1, 2 and 3 are all there (the repeated 2 only counts once) 4 never shows up, so it is the lowest unclaimed ticket 5 and 6 are in the pile too, but they come after the gap the 0 and the -4 are never candidates full answer: 4
You're looking for the lowest raffle ticket number nobody has claimed, in a messy pile that also holds zeros, negatives, repeats, and numbers far beyond anything printed. Don't let the Hard label scare you: a slow answer is easy to write, and the fast one starts by asking what the answer can possibly be. The classic traps are repeats and wildly out-of-range numbers, which break clever tricks that look fine on tidy input. You get 1 to 500,000 numbers, each anywhere in the 32-bit signed range.
Examples
You write
first_missing_positive(nums: List[int])
Example 1
- Input
- nums = [6,2,-4,1,2,3,0,5]
- returns
- 4
Example 2
- Input
- nums = [2,3,4]
- returns
- 1
Save this for your laptop
The editor and Run need a bigger screen. The link opens First Missing Positive ready to code. It is free, and the editor needs no account.
The pattern behind it
Arrays & Hashing
I reach for it when
- You catch yourself scanning the array again for every element.
- The problem asks about duplicates, pairs, counts or groups.
Say this before you type. Say what the key is and what the value remembers, before you write the loop.
All 126 Arrays & Hashing problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.