Solution: Cyclic Sort

Statement

You are given an integer array, nums of size $n$, where each number is distinct and falls within the range $[1, n]$. Your task is to sort the array in place while ensuring a time complexity of $O(n)$ and using only $O(1)$ extra space.

Constraints:

• $n ==$ nums.length

• $1 \leq$ $n$ $\leq10^3$

• Each element in nums is unique and within the range $[1, n]$.

Solution

The essence of this solution lies in sorting the given array in place using the cyclic sort pattern, which is useful for sorting arrays where numbers fall within a fixed range $[1, n]$. The approach ensures each element is placed at its correct index ($nums[i] - 1$) by repeatedly swapping misplaced elements until all numbers are in their correct indexes. Importantly, if the new element is still misplaced after a swap, the swapping process continues, and another swap is performed until it lands in the correct spot. This guarantees a fully sorted array without requiring extra memory.

Now, let’s look at the solution steps below:

1. We initialize a pointer, i = 0, to iterate through the array.

2. We iterate through nums, and for each element nums[i], we determine its correct index as correct = nums[i] - 1.

3. If nums[i] is not at its correct index (nums[i] != nums[correct]), we swap nums[i] with nums[correct], placing the current number in its correct position. However, we do not increment i after swapping because the new element at the index i may still be out of place. So, the process repeats until nums[i] is correctly positioned.

4. Otherwise, if nums[i] is already in the correct place, we increment i and move to the next element.

5. This process continues until all elements are in their correct indexes, ensuring the array is fully sorted.

Let’s look at the following illustration to get a better understanding of the solution: