Problem Statement

We are given an array containing n objects. Each object, when created, was assigned a unique number from the range 1 to n based on their creation sequence. This means that the object with sequence number 3 was created just before the object with sequence number 4.

Write a function to sort the objects in-place on their creation sequence number in O(n) without using any extra space. For simplicity, let's assume we are passed an integer array containing only the sequence numbers, though each number is actually an object.

Example 1:

Input: [3, 1, 5, 4, 2]
Output: [1, 2, 3, 4, 5]

Example 2:

Input: [2, 6, 4, 3, 1, 5]
Output: [1, 2, 3, 4, 5, 6]

Example 3:

Input: [1, 5, 6, 4, 3, 2]
Output: [1, 2, 3, 4, 5, 6]

Note. Because the input holds every number from 1 to n exactly once, the answer to this first question is always the array 1, 2, ..., n. You could pass it by writing that array out directly. The point is the technique rather than the output: from the next question onward numbers go missing, repeat, or fall outside the range, the answer stops being 1..n, and putting each value at its own index is the only thing that still works. Write the swapping version here so it is in your fingers when it starts to matter.

Constraints:

• n == nums.length
• 1 <= n <= 10^4
• 1 <= nums[i] <= n

Try it yourself

Try solving this question here: