LeetCode 2459 - Sort Array by Moving Items to Empty Space

The array contains every integer from 0 to n - 1 exactly once. The value 0 represents the empty space, while every other number represents an item that should eventually appear in sorted order. The operation is unusual compared to normal array sorting problems.

leetcodehardarrayhash-tablesorting

LeetCode Problem 2459

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Sorting

Solution

Problem Understanding

The array contains every integer from 0 to n - 1 exactly once. The value 0 represents the empty space, while every other number represents an item that should eventually appear in sorted order.

The operation is unusual compared to normal array sorting problems. In one move, we may take any item and place it into the current empty position. Since the empty position changes after every move, the process behaves similarly to swapping an element with 0.

The array is considered sorted in exactly two configurations:

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

This means the empty space may be either at the beginning or at the end, but nowhere else.

The task is to compute the minimum number of operations required to transform the initial permutation into one of these two valid target configurations.

The constraints are important:

  • n can be as large as 10^5
  • all values are unique
  • the array is a permutation of [0, n-1]

These constraints immediately rule out exponential search or simulation-heavy brute force methods. We need an algorithm that is close to linear time.

A few edge cases are especially important:

  • The array may already be sorted in one of the valid forms.
  • The empty space may already be in its final position, but other elements are not.
  • The permutation may contain cycles that do not involve 0.
  • Moving elements greedily without understanding cycle structure can produce unnecessary operations.

The uniqueness guarantee is extremely useful because it allows us to treat the array as a permutation mapping between indices and values.

Approaches

Brute Force Approach

A brute force strategy would attempt to search through all possible move sequences using BFS or DFS. Each state represents the current permutation, and each operation generates new states by moving an item into the empty position.

This approach is guaranteed to find the minimum number of operations because BFS explores states level by level. However, the number of permutations is n!, which becomes astronomically large even for moderate n.

Even for n = 10, there are already more than 3 million possible states. Since n can reach 100000, exhaustive search is completely infeasible.

Another slightly better brute force idea is to repeatedly place misplaced elements greedily. Unfortunately, greedy local decisions can fail to achieve the minimum number of operations because cycles not involving 0 require special handling.

Key Insight

The important observation is that the array forms a permutation graph.

For any target arrangement, every index has exactly one correct value. If an index currently contains the wrong value, it belongs to a cycle.

The empty space 0 plays a special role:

  • If a cycle already contains 0, we can resolve the cycle directly.
  • If a cycle does not contain 0, we first need to bring 0 into the cycle, resolve it, then move 0 back out.

This leads to a cycle-counting solution.

Since there are only two valid target arrays, we compute:

  1. Cost to transform into [0,1,2,...,n-1]
  2. Cost to transform into [1,2,3,...,n-1,0]

Then we return the minimum.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n!) Explores permutation states exhaustively
Optimal O(n) O(n) Uses permutation cycle decomposition

Algorithm Walkthrough

We define a helper function that computes the minimum operations required to transform the current array into a specific target permutation.

Step 1: Build the Target Position Mapping

For a chosen target configuration, determine where every value should be located.

For example:

  • Target [0,1,2,3,4]

  • value 0 belongs at index 0

  • value 1 belongs at index 1

  • etc.

Or:

  • Target [1,2,3,4,0]

  • value 1 belongs at index 0

  • value 2 belongs at index 1

  • value 0 belongs at index n-1

This mapping lets us determine whether each element is already in its correct position.

Step 2: Interpret the Array as a Permutation

For each index i, determine where the current value should go.

If index i contains value v, and v belongs at index target_pos[v], then there is a directed edge:

i -> target_pos[v]

This creates disjoint cycles.

Step 3: Traverse Cycles

Use a visited array to find all cycles.

If an index is already correct or already visited, skip it.

Otherwise, follow the permutation until the cycle closes.

Track:

  • cycle length
  • whether the cycle contains the empty space 0

Step 4: Compute Cost for Each Cycle

Suppose a cycle has length k.

Case 1: The cycle contains 0

This cycle can be fixed in exactly:

k - 1

operations.

Each move places one element into its correct position.

Case 2: The cycle does not contain 0

We need two extra operations:

  1. Bring 0 into the cycle
  2. Remove 0 after fixing the cycle

So the total becomes:

k + 1

operations.

Step 5: Sum Costs

Add the cost of every cycle.

Step 6: Try Both Valid Targets

Compute:

  • operations for [0,1,2,...,n-1]
  • operations for [1,2,3,...,n-1,0]

Return the minimum.

Why it works

Every misplaced element belongs to exactly one permutation cycle. A cycle containing 0 can be resolved optimally by repeatedly swapping the correct item into the empty position. A cycle without 0 requires temporarily introducing the empty space, which costs exactly two additional operations. Since cycles are independent, summing the optimal cost for each cycle produces the global minimum.

Python Solution

from typing import List

class Solution:
    def sortArray(self, nums: List[int]) -> int:
        n = len(nums)

        def solve(target: List[int]) -> int:
            target_pos = [0] * n

            for index, value in enumerate(target):
                target_pos[value] = index

            visited = [False] * n
            operations = 0

            for start in range(n):
                if visited[start]:
                    continue

                if nums[start] == target[start]:
                    visited[start] = True
                    continue

                cycle_length = 0
                contains_zero = False

                current = start

                while not visited[current]:
                    visited[current] = True
                    cycle_length += 1

                    if nums[current] == 0:
                        contains_zero = True

                    next_index = target_pos[nums[current]]
                    current = next_index

                if cycle_length > 0:
                    if contains_zero:
                        operations += cycle_length - 1
                    else:
                        operations += cycle_length + 1

            return operations

        target_front = list(range(n))
        target_back = list(range(1, n)) + [0]

        return min(solve(target_front), solve(target_back))

The implementation begins by defining a helper function named solve, which computes the minimum operations needed for a specific target arrangement.

Inside solve, the target_pos array stores the correct destination index for every value. This allows constant-time lookup of where each number should move.

The algorithm then traverses the permutation using cycle decomposition. The visited array ensures that each index is processed exactly once.

For every unvisited index that is not already correct, the code walks through the cycle by repeatedly moving to the index where the current value belongs.

During traversal, the implementation tracks:

  • the cycle length
  • whether the cycle contains 0

After the cycle finishes, the appropriate formula is applied:

  • cycle_length - 1 if 0 is inside
  • cycle_length + 1 otherwise

Finally, the code evaluates both valid target arrays and returns the smaller result.

Go Solution

package main

func sortArray(nums []int) int {
	n := len(nums)

	solve := func(target []int) int {
		targetPos := make([]int, n)

		for i, v := range target {
			targetPos[v] = i
		}

		visited := make([]bool, n)
		operations := 0

		for start := 0; start < n; start++ {
			if visited[start] {
				continue
			}

			if nums[start] == target[start] {
				visited[start] = true
				continue
			}

			cycleLength := 0
			containsZero := false

			current := start

			for !visited[current] {
				visited[current] = true
				cycleLength++

				if nums[current] == 0 {
					containsZero = true
				}

				nextIndex := targetPos[nums[current]]
				current = nextIndex
			}

			if cycleLength > 0 {
				if containsZero {
					operations += cycleLength - 1
				} else {
					operations += cycleLength + 1
				}
			}
		}

		return operations
	}

	targetFront := make([]int, n)
	for i := 0; i < n; i++ {
		targetFront[i] = i
	}

	targetBack := make([]int, n)
	for i := 0; i < n-1; i++ {
		targetBack[i] = i + 1
	}
	targetBack[n-1] = 0

	answer1 := solve(targetFront)
	answer2 := solve(targetBack)

	if answer1 < answer2 {
		return answer1
	}

	return answer2
}

The Go implementation follows the same cycle decomposition logic as the Python version.

Slices are used for arrays such as targetPos and visited. Since the constraints guarantee values fit comfortably inside standard integers, no special overflow handling is required.

Go does not support nested named functions as conveniently as Python, but anonymous functions assigned to variables work well here. The implementation also explicitly constructs the two target arrays using loops.

Worked Examples

Example 1

nums = [4,2,0,3,1]

We evaluate both targets.

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

Correct positions:

Value Correct Index
0 0
1 1
2 2
3 3
4 4

Permutation mapping:

Index Value Goes To
0 4 4
1 2 2
2 0 0
3 3 3
4 1 1

Cycles:

0 -> 4 -> 1 -> 2 -> 0

Cycle length = 4

Contains 0 = yes

Cost:

4 - 1 = 3

Total = 3

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

This produces a larger answer.

Final result:

3

Example 2

nums = [1,2,3,4,0]

This already matches the second valid target.

All indices are already correct.

No cycles need fixing.

Result:

0

Example 3

nums = [1,0,2,4,3]

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

Cycles:

0 -> 1 -> 0

Cost:

2 - 1 = 1

Second cycle:

3 -> 4 -> 3

Does not contain 0

Cost:

2 + 1 = 3

Total:

4

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

Single cycle:

1 -> 4 -> 3 -> 2 -> 1

Contains 0

Cost:

3 - 1 = 2

Final answer:

2

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index is visited at most once for each target
Space O(n) Extra arrays for visited state and target positions

The algorithm performs cycle decomposition twice, once for each valid target configuration. Since every index participates in exactly one cycle traversal, the total work remains linear. The auxiliary arrays also scale linearly with the input size.

Test Cases

sol = Solution()

assert sol.sortArray([4,2,0,3,1]) == 3  # example 1
assert sol.sortArray([1,2,3,4,0]) == 0  # already sorted with zero at end
assert sol.sortArray([1,0,2,4,3]) == 2  # example 3

assert sol.sortArray([0,1]) == 0  # smallest size, already sorted front
assert sol.sortArray([1,0]) == 0  # smallest size, already sorted back

assert sol.sortArray([2,0,1]) == 1  # single cycle containing zero
assert sol.sortArray([3,1,2,0]) == 1  # nearly sorted

assert sol.sortArray([0,2,1,3]) == 3  # non-zero cycle requires extra operations
assert sol.sortArray([2,1,0,3]) == 1  # swap through zero once

assert sol.sortArray([5,4,3,2,1,0]) == 4  # large reversed permutation
assert sol.sortArray([1,3,4,2,0]) == 2  # cycle ending at zero
assert sol.sortArray([2,3,4,5,0,1]) == 4  # long cycle

assert sol.sortArray([0,2,3,1]) == 2  # zero already at front
assert sol.sortArray([1,2,0,3]) == 1  # almost sorted toward back target
Test Why
[4,2,0,3,1] Verifies standard mixed permutation
[1,2,3,4,0] Already valid target
[1,0,2,4,3] Requires choosing the better target
[0,1] Minimum size with zero at front
[1,0] Minimum size with zero at back
[2,0,1] Single cycle involving zero
[3,1,2,0] Nearly sorted arrangement
[0,2,1,3] Non-zero cycle handling
[2,1,0,3] Simple correction through zero
[5,4,3,2,1,0] Large reverse ordering
[1,3,4,2,0] Medium-sized cycle
[2,3,4,5,0,1] Long cycle traversal
[0,2,3,1] Zero already fixed
[1,2,0,3] Close to second target

Edge Cases

One important edge case occurs when the array is already sorted. Since the problem allows both [0,1,2,...] and [1,2,3,...,0], the implementation must check both targets. A solution that only checks one configuration would incorrectly return a nonzero answer for arrays like [1,2,3,4,0].

Another tricky case happens when a cycle does not contain 0. Many incorrect solutions assume every cycle of length k costs k - 1 operations. That only works when the empty space participates directly in the cycle. If not, we must spend two extra moves to bring 0 into the cycle and remove it afterward. The implementation explicitly tracks whether 0 appears in each cycle.

A third important edge case involves very large arrays. Since n can reach 100000, recursive DFS implementations risk stack overflow. This solution uses iterative traversal with loops and a visited array, ensuring safe execution even for the largest inputs.