Is Sort Array by Moving Items to Empty Space easy or hard?

LeetCode classifies this problem as Hard because the optimal solution requires recognizing permutation cycles and reasoning about how the empty slot affects cycle resolution. Once the cycle insight is understood, the implementation becomes relatively straightforward.

Sort Array by Moving Items to Empty Space Python/Java solution

Most implementations follow the same logic across languages: iterate through indices, detect permutation cycles, and count the required moves depending on whether the empty slot is part of the cycle. The algorithm translates directly into Python, Java, C++, or Go with simple loops and index tracking.

How to solve Sort Array by Moving Items to Empty Space in O(n)?

Traverse the array and identify permutation cycles where elements are not in their correct indices. Count the number of elements in each cycle and check whether the empty slot participates in that cycle. If the empty slot is inside the cycle, resolving it takes k moves for a cycle of length k; otherwise one extra move is needed to bring the empty slot into the cycle. Summing these operations across all cycles gives the answer in linear time.

What is the best approach for Sort Array by Moving Items to Empty Space?

The best approach is permutation cycle decomposition. Treat the array as a permutation where each value should move to its index and analyze cycles of misplaced elements. The empty slot (0) acts as a buffer to rotate elements within a cycle. This method computes the minimum moves in O(n) time and O(1) extra space.

Is Sort Array by Moving Items to Empty Space asked at Google/Amazon/Meta?

Permutation and cycle-based array reordering problems appear frequently in interviews at large tech companies including Google, Amazon, and Meta. Variants that involve minimizing swaps or using a buffer slot like an empty index are common in system design and algorithm interviews.

What data structure is used in Sort Array by Moving Items to Empty Space?

The problem primarily uses arrays and permutation cycle analysis. No complex data structures are required. The algorithm relies on index traversal, cycle detection, and constant-space counters.

What is the time complexity of Sort Array by Moving Items to Empty Space?

The optimal solution runs in O(n) time because each index is visited at most once while detecting permutation cycles. Space complexity is O(1) since the algorithm only tracks counters and indices without additional data structures.

Description Hints 3 Solution Video 33:52

2459. Sort Array by Moving Items to Empty Space

Hard45.7% acceptance1 companyPremium elsewhere, free here

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] 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.

Constraints:

n == nums.length
2 <= n <= 10⁵
0 <= nums[i] < n
All the values of nums are unique.

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

There are two possibilities for nums to be sorted. Find the minimum number of operations needed for the first possibility, then find the minimum number of operations needed for the second possibility. The answer is the minimum out of the two.

Hint 2

If the empty space is not at its ending position, then you can move the item that should be where the empty space is to the empty space.

Hint 3

If the empty space is at its ending position, then you need to move an out-of-place item to the empty space.

33:52

Still stuck?Read the written solution, or watch a walkthrough.

Open solution