Sort Array by Moving Items to Empty Space

Sort Array by Moving Items to Empty Space

What is this problem about?

"Sort Array by Moving Items to Empty Space" is a complex "Hard" difficulty problem that feels like a sliding puzzle. You are given an array that is a permutation of $0$ to $n-1$, where $0$ represents an "empty space." You can move any number into the empty space. Your goal is to find the minimum number of moves to sort the array into one of two targets:

1. [0, 1, 2, ..., n-1]
2. [1, 2, ..., n-1, 0]

This problem isn't just about sorting; it's about finding the shortest sequence of swaps where one of the swapped elements is always the designated "zero."

Why is this asked in interviews?

Google asks this question to see if candidates can visualize a sorting problem as a graph problem—specifically, identifying cycles. It tests your ability to think beyond standard sorting algorithms and understand the mechanics of permutations. It requires a deep understanding of how "swaps" affect the structure of an array and how to minimize those swaps by leveraging the "empty space" effectively.

Algorithmic pattern used

The problem can be solved using Cycle Decomposition. In any permutation, the elements form a set of disjoint cycles. To sort an array using swaps, the number of swaps needed is typically $N - (\text{number of cycles})$. However, because we can only swap with the "empty space" (0), the logic changes slightly.

• If 0 is part of a cycle, it takes cycle_size - 1 moves to fix that cycle.
• If 0 is not part of a cycle, we must first move 0 into the cycle (1 move), fix the cycle (cycle_size moves), and we end up with 0 in the correct spot.

Example explanation

Input: [1, 0, 2] Target: [0, 1, 2]

1. Current 0 is at index 1. The target at index 1 is '1'.
2. Find where '1' is. It's at index 0.
3. Swap 0 and 1. Array becomes [0, 1, 2]. Total moves: 1. If the input was [2, 0, 1], we would need more moves to put 2 and 1 in their correct spots by using the 0 as a buffer.

Common mistakes candidates make

The biggest mistake is trying to use BFS to find the shortest path. While BFS works for small arrays, the state space ($N!$) is too large for typical constraints. Another error is not realizing that there are two possible sorted targets and that you must calculate the minimum moves for both and take the overall minimum. Candidates also often struggle to correctly implement the cycle-finding logic, especially the special handling for when the 0 is already in its target position but other elements are not.

Interview preparation tip

This "Sort Array by Moving Items to Empty Space coding problem" is a great way to learn about Permutation Cycles. Practice similar problems like "Minimum Swaps to Sort." Understand that a cycle of length $K$ can be sorted in $K-1$ swaps if you can swap any two elements, but the rules change when you have a restricted swap (like swapping with 0). Mastering cycle decomposition will make many "Hard" array problems much easier to handle.