LeetCode Entry

2948. Make Lexicographically Smallest Array by Swapping Elements

29.08.2026 medium 2026 kotlin rust

Smallest array by swapping numbers with diff in 0..L

2948. Make Lexicographically Smallest Array by Swapping Elements medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1466

Problem TLDR

Smallest array by swapping numbers with diff in 0..L

Intuition

Find groups then sort inside each. All numbers are reachable inside the group.

Approach

• use heap or just sort ad-hoc

Complexity

• Time complexity: \(O(nlogn)\)

• Space complexity: \(O(n)\)

Code

    fun lexicographicallySmallestArray(n: IntArray, l: Int) = run {
        val m = HashMap<Int, PriorityQueue<Int>>()
        var q = PriorityQueue<Int>(); var p = -l - 1
        for (x in n.sorted()) {
            if (x - p > l) q = PriorityQueue()
            q += x; m[x] = q; p = x
        }
        IntArray(n.size) { m[n[it]]!!.poll() }
    }

    pub fn lexicographically_smallest_array(n: Vec<i32>, l: i32) -> Vec<i32> {
        let (mut r, mut s) = (n.clone(), (0..n.len()).collect::<Vec<_>>());
        s.sort_by_key(|&i| n[i]);
        for g in s.chunk_by(|&a, &b| n[b] - n[a] <= l) {
            let mut p = g.to_vec(); p.sort();
            for (i, &j) in p.into_iter().zip(g) { r[i] = n[j] }
        } r
    }