Sort Array by Moving Items to Empty Space - Video Solutions

Problem Overview: You are given a permutation of numbers 0..n-1 where 0 represents an empty space. In one operation, you can move any element into the empty slot, effectively swapping that element with 0. The task is to compute the minimum number of moves required to rearrange the array into sorted order.

The key challenge is that elements cannot be swapped directly. Every movement must go through the empty space. This turns the array into a permutation transformation problem where the empty index acts as a temporary buffer while resolving misplaced elements.

Approach 1: Direct Simulation (Greedy Placement) (O(n²) time, O(1) space)

A straightforward idea is to repeatedly place the correct value into the empty slot. First locate where the empty position should eventually go in the sorted array. If the empty slot is not in its correct place, move the element that belongs there into the empty position. Otherwise, choose a misplaced element and move it into the empty slot to start fixing a new chain of misplaced values. This greedy simulation gradually resolves positions but may require scanning the array multiple times to find the next misplaced value. Because each operation may involve searching the array, the worst-case runtime grows to O(n²). This approach helps build intuition but is not efficient for large inputs.

Approach 2: Permutation Cycle Decomposition (O(n) time, O(1) space)

The optimal method treats the array as a permutation and analyzes cycles. Each element belongs at index equal to its value in the sorted array. When elements form a cycle of misplaced indices, they must be rotated through the empty space to reach their correct positions. If the empty slot is already inside a cycle, you can resolve the cycle in k moves for a cycle of length k. If the empty slot is outside the cycle, one extra move is needed to bring it into the cycle first.

Iterate through the array and track positions where nums[i] != i. Follow the permutation until the cycle closes. Count how many elements participate in that cycle and determine whether the empty slot is part of it. This transforms the sorting process into counting the minimum moves required to break every permutation cycle. The algorithm runs in linear time because each element is visited once.

Some implementations compute the cost for both ascending and reverse-sorted targets, since the empty slot can change cycle structure. The minimum of the two counts gives the optimal answer.

This solution relies on recognizing permutation cycles, a common pattern in array reordering problems and swap minimization tasks involving sorting and greedy strategies.

Recommended for interviews: The permutation cycle approach is what interviewers expect. It reduces the problem to cycle counting, runs in O(n), and uses constant extra space. Showing the brute-force simulation first demonstrates understanding of the constraints, but recognizing permutation cycles demonstrates stronger algorithmic insight.