LeetCode Entry

912. Sort an Array

25.07.2024 medium 2024 kotlin rust

Sort array using minimum memory

912. Sort an Array medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/681

Problem TLDR

Sort array using minimum memory #medium

Intuition

The most memory-friendly algorithm would be the Heap Sort - O(1). However, I didn’t know it, so let’s implement a QuickSort.

Approach

• in the partition we must use some border value and border position, everything less must be to the left of the border.
• worst case is O(n^2), so we must use the shuffle

Complexity

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

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

Code

    fun sortArray(nums: IntArray): IntArray {
        fun swap(a: Int, b: Int)
            { nums[a] = nums[b].also { nums[b] = nums[a] }}
        fun partition(from: Int, to: Int) {
            if (from >= to) return
            var x = nums[from]
            var lo = from
            for (i in from + 1..to) if (nums[i] <= x)
                swap(i, ++lo)
            swap(from, lo)
            partition(from, lo - 1)
            partition(lo + 1, to)
        }
        nums.shuffle()
        partition(0, nums.lastIndex)
        return nums
    }

    pub fn sort_array(mut nums: Vec<i32>) -> Vec<i32> {
        fn partition(nums: &mut Vec<i32>, from: usize, to: usize) {
            if from >= to { return }
            let (mut x, mut lo) = (nums[to], from);
            for i in from..to {
                if nums[i] < x { nums.swap(i, lo); lo += 1 }}
            nums.swap(to, lo);
            if lo > 0 { partition(nums, from, lo - 1) }
            partition(nums, lo + 1, to);
        }
        nums.shuffle(&mut thread_rng()); let n = nums.len();
        partition(&mut nums, 0, n - 1); nums
    }