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]$.

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding on how to solve this problem.

Implement your solution in the following coding playground.