Think Like an Engineer: Optimize Swaps with Cycle Insight | Sort Array | Moving Items to Empty Space

You are given an integer array nums of size n containing each element from 0 to n - 1 (inclusive). Each of the elements from 1 to n - 1 represents an item, and the element 0 represents an empty space.

1. In one operation, you can move any item to the empty space.
2. nums is considered to be sorted if the numbers of all the items are in ascending order
3. the empty space is either at the beginning or at the end of the array.

For example, if n = 4, nums is sorted if:

• nums = [0,1,2,3] or
• nums = [1,2,3,0]
• and considered to be unsorted otherwise.

Return the minimum number of operations needed to sort nums.

Example 1:

Input: nums = [4,2,0,3,1]
Output: 3
Explanation:
- Move item 2 to the empty space. Now, nums = [4,0,2,3,1].
- Move item 1 to the empty space. Now, nums = [4,1,2,3,0].
- Move item 4 to the empty space. Now, nums = [0,1,2,3,4].
It can be proven that 3 is the minimum number of operations needed.

Example 2:

Input: nums = [1,2,3,4,0]
Output: 0
Explanation: nums is already sorted so return 0.

Example 3:

Input: nums = [1,0,2,4,3]
Output: 2
Explanation:
- Move item 2 to the empty space. Now, nums = [1,2,0,4,3].
- Move item 3 to the empty space. Now, nums = [1,2,3,4,0].
It can be proven that 2 is the minimum number of operations needed.

        [0, 1, 2, 3, 4]
         0. 1. 2. 3. 4

create a destination how our target looks like. From current to our ideal

                {
                    0: 0
                    1: 1
                    2: 2
                    3: 3
                    4: 4
                }

now we need to compare the current one

The order of the elements in the array matter more than the location of 0.We need all numbers in order (1,2,3,...) with 0 at either end.

The actual position of 0 is less important than getting the numbers in the right sequence because:

1. Once numbers are in order, moving 0 to either end takes just 1 operation
2. The hard part is getting the numbers in sequence, not positioning 0

Example Insight:

[4,2,0,3,1] (unsorted) vs [0,1,2,3,4] (sorted)

The numbers themselves need to be in order (1,2,3,4) regardless of where 0 is

We can fix the sequence first, then handle 0 last

Example Walkthrough

Let's sort [4,2,0,3,1] to [0,1,2,3,4]:

Step 1: Create Mapping

{
 0: 0, // 0 belongs at index 0
 1: 1, // 1 belongs at index 1
 2: 2, // 2 belongs at index 2
 3: 3, // 3 belongs at index 3
 4: 4  // 4 belongs at index 4
}

Step 2: Find Cycles

Start at index 0 (value = 4):

[4,2,0,3,1] to [0,1,2,3,4]:

• 4 should be at index 4 → go to index 4
• At index 4: value = 1 → should be at index 1 → go to index 1
• At index 1: value = 2 → should be at index 2 → go to index 2
• At index 2: value = 0 → should be at index 0 → back to start

This forms a cycle: 0 → 4 → 1 → 2 → 0

Step 3: Calculate Operations for Cycle

• Cycle includes 0? Yes (value 0 is in the cycle)
• Operations needed: cycle length - 1 = 4 - 1 = 3 operations

where cycle length is the total elements involved.

Why cycle length - 1?

Each swap fixes one number's position.

With 0 in the cycle, we need (n-1) swaps to fix n numbers

Remaining Element:

• Index 3 has value 3 (correct position)
• No operation needed

Visualising the Operations

Original: [4,2,0,3,1]

1. Swap 4 and 0: [0,2,4,3,1] (move 4 to where it belongs)
2. Swap 2 and 0: [2,0,4,3,1] (move 2 to its place)
3. Swap 1 and 0: [2,1,4,3,0] (move 1 to its place)
4. Now numbers are in order with 0 at end (extra operation to move 0 to start if needed)

But our cycle approach counted this as 3 operations because it's smarter about swaps.

let n = nums.length
let start = Array.from({ length: n }, (_, i) => i);
let end = Array.from({ length: n }, (_, i) => i + 1);
end[n - 1] = 0;

function calculationOps(target) {

let positionMap = {}
for (let i = 0; i < n; i++) {
    positionMap[target[i]] = i
}
let ops = 0, visited = new Array(n).fill(false)

for (let i = 0; i < n; i++) {
    if (!visited[i] && nums[i] !== target[i]) {
        let cycleSize = 0, hasZero = false, j = i
        while (!visited[j]) {
            visited[j] = true
            if (nums[j] === 0) {
                hasZero = true
            }
            cycleSize++
            j = positionMap[nums[j]]
        }
        ops += hasZero ? cycleSize - 1 : cycleSize + 1
    }
}
return ops
}

return Math.min(calculationOps(start), calculationOps(end))