608. Sort Array By Moving Items to Empty Space
An integer array of size n, with each entry ranging from 0 to n - 1 (inclusive), is provided to you. The elements 1 through n-1 each represent an object, while 0 denotes an empty space.
You can move anything to the vacant space in a single action. If all of the item numbers are in ascending order and the array's empty space is at the start or end, then the array is said to be sorted.
For instance, nums is ordered if n = 4 if:
If nums = [0,1,2,3] or nums = [1,2,3,0]..., it is regarded as unsorted.
Give back the bare minimum of operations required to sort numbers.
Example 1:
Input : nums = [3, 1, 0, 4, 2]
Output : 3
Explanation :
- Move item 3 to the empty space. Now, nums = [0, 1, 3, 4, 2].
- Move item 1 to the empty space. Now, nums = [1, 0, 3, 4, 2].
- Move item 2 to the empty space. Now, nums = [1, 2, 3, 4, 0].
It can be proven that 3 is the minimum number of operations needed.
Example 2:
Input : nums = [4, 3, 2, 1, 0]
Output : 4
Explanation :
- Move item 4 to the empty space. Now, nums = [0, 3, 2, 1, 4].
- Move item 3 to the empty space. Now, nums = [3, 0, 2, 1, 4].
- Move item 1 to the empty space. Now, nums = [3, 1, 2, 0, 4].
- Move item 3 to the empty space. Now, nums = [0, 1, 2, 3, 4].
It can be proven that 4 is the minimum number of operations needed.
Now Your Turn!
Pick the correct output for the given inputInput : nums = [4, 5, 1, 0, 3, 2]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- n == nums.length
- 2 <= n <= 105
- 0 <= nums[i] < n
- All the values of nums are unique.