Sort Array by Moving Items to Empty Space

Problem

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 _theminimum number of operations needed to sort _nums.

Examples

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^5
• 0 <= nums[i] < n
• All the values of nums are unique.

Solution

Method 1 - Cycle Detection and Path Finding

Intuition

The key insight is that we need to determine which elements are already in their correct positions and which need to be moved. Since we can only move items to the empty space (0), we need to find the optimal path to sort the array. The problem becomes finding the minimum number of swaps needed, considering that 0 acts as a temporary space.

Approach

1. Check if the array is already sorted (either [0,1,2,...,n-1] or [1,2,...,n-1,0])
2. Find the position of 0 (empty space)
3. Count how many elements are already in their correct positions
4. For elements not in correct positions, we need to move them through cycles
5. The minimum operations will be n minus the number of elements already in correct positions
6. Special handling for cases where 0 is at the beginning or end

Code

C++

class Solution {
public:
    int sortArray(vector<int>& nums) {
        int n = nums.size();
        
        // Check if already sorted
        bool sorted1 = true, sorted2 = true;
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) sorted1 = false;
            if (nums[i] != (i + 1) % n) sorted2 = false;
        }
        if (sorted1 || sorted2) return 0;
        
        // Find position of 0
        int zeroPos = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                zeroPos = i;
                break;
            }
        }
        
        // Count elements in correct position for both target configurations
        int correct1 = 0, correct2 = 0;
        
        // Target: [0, 1, 2, ..., n-1]
        for (int i = 0; i < n; i++) {
            if (nums[i] == i) correct1++;
        }
        
        // Target: [1, 2, ..., n-1, 0]
        for (int i = 0; i < n; i++) {
            if (nums[i] == (i + 1) % n) correct2++;
        }
        
        // Calculate moves needed for each configuration
        int moves1 = n - correct1;
        int moves2 = n - correct2;
        
        return min(moves1, moves2);
    }
};

Go

func sortArray(nums []int) int {
    n := len(nums)
    
    // Check if already sorted
    sorted1, sorted2 := true, true
    for i := 0; i < n; i++ {
        if nums[i] != i {
            sorted1 = false
        }
        if nums[i] != (i+1)%n {
            sorted2 = false
        }
    }
    if sorted1 || sorted2 {
        return 0
    }
    
    // Find position of 0
    zeroPos := 0
    for i := 0; i < n; i++ {
        if nums[i] == 0 {
            zeroPos = i
            break
        }
    }
    
    // Count elements in correct position for both configurations
    correct1, correct2 := 0, 0
    
    // Target: [0, 1, 2, ..., n-1]
    for i := 0; i < n; i++ {
        if nums[i] == i {
            correct1++
        }
    }
    
    // Target: [1, 2, ..., n-1, 0]
    for i := 0; i < n; i++ {
        if nums[i] == (i+1)%n {
            correct2++
        }
    }
    
    // Calculate moves needed
    moves1 := n - correct1
    moves2 := n - correct2
    
    if moves1 < moves2 {
        return moves1
    }
    return moves2
}

Java

class Solution {
    public int sortArray(int[] nums) {
        int n = nums.length;
        
        // Check if already sorted
        boolean sorted1 = true, sorted2 = true;
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) sorted1 = false;
            if (nums[i] != (i + 1) % n) sorted2 = false;
        }
        if (sorted1 || sorted2) return 0;
        
        // Find position of 0
        int zeroPos = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                zeroPos = i;
                break;
            }
        }
        
        // Count elements in correct position for both configurations
        int correct1 = 0, correct2 = 0;
        
        // Target: [0, 1, 2, ..., n-1]
        for (int i = 0; i < n; i++) {
            if (nums[i] == i) correct1++;
        }
        
        // Target: [1, 2, ..., n-1, 0]
        for (int i = 0; i < n; i++) {
            if (nums[i] == (i + 1) % n) correct2++;
        }
        
        // Calculate moves needed
        int moves1 = n - correct1;
        int moves2 = n - correct2;
        
        return Math.min(moves1, moves2);
    }
}

Kotlin

class Solution {
    fun sortArray(nums: IntArray): Int {
        val n = nums.size
        
        // Check if already sorted
        var sorted1 = true
        var sorted2 = true
        for (i in 0 until n) {
            if (nums[i] != i) sorted1 = false
            if (nums[i] != (i + 1) % n) sorted2 = false
        }
        if (sorted1 || sorted2) return 0
        
        // Find position of 0
        var zeroPos = 0
        for (i in 0 until n) {
            if (nums[i] == 0) {
                zeroPos = i
                break
            }
        }
        
        // Count elements in correct position for both configurations
        var correct1 = 0
        var correct2 = 0
        
        // Target: [0, 1, 2, ..., n-1]
        for (i in 0 until n) {
            if (nums[i] == i) correct1++
        }
        
        // Target: [1, 2, ..., n-1, 0]
        for (i in 0 until n) {
            if (nums[i] == (i + 1) % n) correct2++
        }
        
        // Calculate moves needed
        val moves1 = n - correct1
        val moves2 = n - correct2
        
        return minOf(moves1, moves2)
    }
}

Python

class Solution:
    def sortArray(self, nums: list[int]) -> int:
        n = len(nums)
        
        # Check if already sorted
        sorted1 = all(nums[i] == i for i in range(n))
        sorted2 = all(nums[i] == (i + 1) % n for i in range(n))
        if sorted1 or sorted2:
            return 0
        
        # Find position of 0
        zero_pos = nums.index(0)
        
        # Count elements in correct position for both configurations
        correct1 = sum(1 for i in range(n) if nums[i] == i)
        correct2 = sum(1 for i in range(n) if nums[i] == (i + 1) % n)
        
        # Calculate moves needed
        moves1 = n - correct1
        moves2 = n - correct2
        
        return min(moves1, moves2)

Rust

impl Solution {
    pub fn sort_array(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        
        // Check if already sorted
        let sorted1 = (0..n).all(|i| nums[i] == i as i32);
        let sorted2 = (0..n).all(|i| nums[i] == ((i + 1) % n) as i32);
        if sorted1 || sorted2 {
            return 0;
        }
        
        // Find position of 0
        let zero_pos = nums.iter().position(|&x| x == 0).unwrap();
        
        // Count elements in correct position for both configurations
        let correct1 = (0..n).filter(|&i| nums[i] == i as i32).count();
        let correct2 = (0..n).filter(|&i| nums[i] == ((i + 1) % n) as i32).count();
        
        // Calculate moves needed
        let moves1 = n - correct1;
        let moves2 = n - correct2;
        
        std::cmp::min(moves1, moves2) as i32
    }
}

TypeScript

class Solution {
    sortArray(nums: number[]): number {
        const n = nums.length;
        
        // Check if already sorted
        const sorted1 = nums.every((val, i) => val === i);
        const sorted2 = nums.every((val, i) => val === (i + 1) % n);
        if (sorted1 || sorted2) return 0;
        
        // Find position of 0
        const zeroPos = nums.indexOf(0);
        
        // Count elements in correct position for both configurations
        const correct1 = nums.filter((val, i) => val === i).length;
        const correct2 = nums.filter((val, i) => val === (i + 1) % n).length;
        
        // Calculate moves needed
        const moves1 = n - correct1;
        const moves2 = n - correct2;
        
        return Math.min(moves1, moves2);
    }
}

Complexity

• ⏰ Time complexity: O(n), we iterate through the array a constant number of times to check sorted status and count correct positions
• 🧺 Space complexity: O(1), we only use a constant amount of extra space for variables