LeetCode Entry

2191. Sort the Jumbled Numbers

24.07.2024 medium 2024 kotlin rust

Sort array by digits mapping

2191. Sort the Jumbled Numbers medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/680

Problem TLDR

Sort array by digits mapping #medium

Intuition

Just sort using a comparator by key

Approach

• careful with the corner case n = 0
• in Rust using sort_by_cached_key has improved runtime from 170ms to 20ms

Complexity

• Time complexity: \(O(nlog(n))\)

• Space complexity: \(O(1)\), O(n) for Kotlin, as it didn’t have a proper sorting method for IntArray

Code

    fun sortJumbled(mapping: IntArray, nums: IntArray) =
        nums.sortedWith(compareBy {
            var n = it
            var res = if (n < 1) mapping[n] else 0
            var pow = 1
            while (n > 0) {
                res += pow * mapping[n % 10]
                pow *= 10
                n /= 10
            }
            res
        })

    pub fn sort_jumbled(mapping: Vec<i32>, mut nums: Vec<i32>) -> Vec<i32> {
        nums.sort_by_cached_key(|&x| {
            let (mut n, mut pow, mut res) = (x as usize, 1, 0);
            if x < 1 { res = mapping[n] }
            while n > 0 {
                res += pow * mapping[n % 10];
                pow *= 10; n /= 10
            }
            res
        }); nums
    }