Sort Array by Moving Items to Empty Space - Solution & Explanation
Problem Statement
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.
In one operation, you can move any item to the empty space. nums is considered to be sorted if the numbers of all the items are in ascending order and 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]ornums = [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.
Constraints:
n == nums.length2 <= n <= 1050 <= nums[i] < n- All the values of
numsare unique.
Approach Overview
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.
Solution
For a permutation cycle of length m, if 0 is in the cycle, the number of swaps is m-1; otherwise, the number of swaps is m+1.
We find all permutation cycles, first calculate the total number of swaps assuming each cycle requires m+1 swaps, then check if 0 is misplaced. If it is, it means 0 is in a permutation cycle, so we subtract 2 from the total number of swaps.
Here, 0 can be at position 0 or at position n-1. We take the minimum of these two cases.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation (Greedy Placement) | O(n²) | O(1) | Useful for understanding how the empty slot gradually fixes misplaced elements |
| Permutation Cycle Decomposition | O(n) | O(1) | Optimal approach for large inputs and the expected interview solution |
Video Solution
LeetCode 2459 - Sort Array by Moving Items to Empty Space | Google Interview Question • DepthLayer • 17 views views
Frequently Asked Questions
Is Sort Array by Moving Items to Empty Space easy or hard?
Sort Array by Moving Items to Empty Space Python/Java solution
How to solve Sort Array by Moving Items to Empty Space in O(n)?
What is the best approach for Sort Array by Moving Items to Empty Space?
Is Sort Array by Moving Items to Empty Space asked at Google/Amazon/Meta?
What data structure is used in Sort Array by Moving Items to Empty Space?
What is the time complexity of Sort Array by Moving Items to Empty Space?
Ready to solve this problem?
Practice Sort Array by Moving Items to Empty Space with our built-in code editor and test cases.
Practice on FleetCode