Make lexicographically smallest array by swapping elements

Array Union-Find Sorting

60.2% acceptance

Feb 25, 2026

968

You are given a 0-indexed array of positive integers nums and a positive integer limit. In one operation, you can choose any two indices i and j and swap nums[i] and nums[j] if |nums[i] - nums[j]| <= limit. Return the lexicographically smallest array that can be obtained by performing the operation any number of times.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn lexicographically_smallest_array(nums: Vec<i32>, limit: i32) -> Vec<i32> {
    let n = nums.len();
    // Sort (value, original_index) pairs
    let mut sorted: Vec<(i32, usize)> = nums.iter().cloned().enumerate().map(|(i, v)| (v, i)).collect();
    sorted.sort_unstable();

    let mut ans = nums.clone();
    let mut i = 0;
    while i < n {
      // Find the group: consecutive elements where sorted[j].0 - sorted[j-1].0 <= limit
      let mut j = i + 1;
      while j < n && sorted[j].0 - sorted[j - 1].0 <= limit {
        j += 1;
      }
      // Group is sorted[i..j]
      // Get original indices in this group, sort them
      let mut indices: Vec<usize> = (i..j).map(|k| sorted[k].1).collect();
      indices.sort_unstable();
      // Assign sorted values to sorted positions
      for (rank, &orig_idx) in indices.iter().enumerate() {
        ans[orig_idx] = sorted[i + rank].0;
      }
      i = j;
    }
    ans
  }
}