Cyclic sort Flashcards
(8 cards)
What is the definition of Cyclic Sort?
Sorts array by placing elements at their index (value-1).
When is Cyclic Sort used?
Used for arrays with values 1 to n, missing/duplicates.
What are the key steps in Cyclic Sort?
- Iterate array, swap element to its correct index (value-1).
- Continue until element is correct or visited.
- Identify missing/duplicates post-sort.
How does Cyclic Sort apply to Find Missing Number?
Find missing number in array of 0 to n by placing each value at index (value) and finding missing index.
What is the time and space complexity of Cyclic Sort?
Time: O(n), Space: O(1).
What are the gotchas in Cyclic Sort?
Out-of-range values, duplicates.
Provide a code example for Find Missing Number.
```python
from typing import List
def find_missing_number(nums: List[int]) -> int:
i, n = 0, len(nums)
while i < n:
correct = nums[i]
if 0 <= correct < n and nums[i] != nums[correct]:
nums[i], nums[correct] = nums[correct], nums[i]
else:
i += 1
for i in range(n):
if nums[i] != i:
return i
return n
~~~
What is a visual representation for Cyclic Sort?
[Add image manually].
