Sort array by moving items to empty space

Array Hash Table Sorting

45.7% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn sort_array(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    
    // Helper: compute cost for a given target permutation
    // perm[i] = where the value at position i should go
    fn cost(perm: &[usize], p0: usize) -> i32 {
      let n = perm.len();
      let mut visited = vec![false; n];
      let mut total = 0i32;
      for i in 0..n {
        if visited[i] || perm[i] == i { continue; }
        let mut len = 0;
        let mut j = i;
        let mut has_p0 = false;
        while !visited[j] {
          visited[j] = true;
          if j == p0 { has_p0 = true; }
          j = perm[j];
          len += 1;
        }
        if has_p0 {
          total += len - 1;
        } else {
          total += len + 1;
        }
      }
      total
    }
    
    let p0 = nums.iter().position(|&x| x == 0).unwrap();
    
    // Target 1: [0,1,...,n-1] → perm[i] = nums[i]
    let perm1: Vec<usize> = nums.iter().map(|&x| x as usize).collect();
    let c1 = cost(&perm1, p0);
    
    // Target 2: [1,2,...,n-1,0] → perm[i] = (nums[i]+n-1)%n
    let perm2: Vec<usize> = nums.iter().map(|&x| (x as usize + n - 1) % n).collect();
    let c2 = cost(&perm2, p0);
    
    c1.min(c2)
  }
}