IntermediateMath for DSAArrays & Strings
The pigeonhole principle
Put n + 1 items into n boxes and some box gets two. It's why an array of n+1 numbers from 1..n must contain a duplicate.
The idea
If there are more items than places, at least two items share a place. Simple, but it guarantees answers exist and points to clever solutions.
Find the Duplicate Number has n + 1 values in the range 1..n, so a duplicate must exist. First Missing Positive uses the reverse: n numbers can fill at most 1..n, so the answer is in 1..n + 1.
Worked example
First Missing Positive on [3, 4, -1, 1]
- 4 numbers can cover at most 1..4, so the answer is between 1 and 5.
- Place each value v in 1..4 at index v − 1: [1, -1, 3, 4].
- Index 1 doesn't hold 2 → the answer is 2.
In code (Python)
def first_missing_positive(nums):
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
j = nums[i] - 1
nums[i], nums[j] = nums[j], nums[i]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1O(n) time, O(1) extra space.
How to spot it
- Values limited to 1..n (or 0..n) in an array of about n items: the range itself is a hint.
Common mistakes
- Sorting to find the answer (O(n log n)) when the range allows O(n).
- Swapping without the nums[j] != nums[i] check, which loops forever on duplicates.
Where it comes up
Go further
Up next for you · Beginner
“Have I seen this?” is a set →