Loading
Loading
When values are a permutation of indices, the array is its own map.
If an array of length n holds values drawn from 1..n, then each value has a natural home: value v belongs at index v-1. Repeatedly swapping each value to its home sorts the array in linear time with no extra memory, and whatever ends up in the wrong place identifies the missing or duplicated values.
The array doubles as a hash table with a perfect hash function: index = value - 1. Each swap places at least one value correctly, so the total number of swaps is bounded by n even though the loop looks nested.
The shape, not a solution. Adapt the condition and the state to the problem in front of you.
def cyclic_sort(nums): """Place every value v at index v - 1. Values must be in 1..n.""" i = 0 while i < len(nums): home = nums[i] - 1 if 0 <= home < len(nums) and nums[i] != nums[home]: # Compare against nums[home], not against i: duplicates would # otherwise swap forever. nums[i], nums[home] = nums[home], nums[i] else: # Either already home, or a duplicate. Either way, move on. i += 1 return nums def find_missing(nums): cyclic_sort(nums) for index, value in enumerate(nums): if value != index + 1: return index + 1 return len(nums) + 1| Status | Problem | Difficulty | Role |
|---|---|---|---|
| Reprinted Badge#145 | Easy | Primary | |
| Unfilled Seats#146 | Easy | Primary | |
| Smallest Unclaimed Ticket#147 | Hard | Primary |
Sign in to keep a note here. It is free, and nobody else can see it.
Sign in