LeetCode Entry

75. Sort Colors

12.06.2024 medium 2024 kotlin rust

Sort 012 array

75. Sort Colors medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/637

Problem TLDR

Sort 012 array #medium

Intuition

The simple solution is to just counting sort. However, we can do one pass solution - use zeros and twos zones and fill them:

    // 1 2 0
    // z   t
    // i
    //   i
    //   0 2
    //   t
    //     i
    // 2 1 2
    // z   t
    // i
    //   t
    //   i

The corner case is when 2 and 0 must be swapped before next i. One way is to write if (nums[i] == 2) two--, another way is to not increment i when 2 swapped.

Approach

Let’s implement both solutions.

• Slice.fill in Rust helps

Complexity

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

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

Code

    fun sortColors(nums: IntArray): Unit {
        var zero = 0; var two = nums.lastIndex; var i = 0
        while (i <= two)
            if (nums[i] < 1) {
                nums[zero] = nums[i].also { nums[i++] = nums[zero++] }
            } else if (nums[i] > 1) {
                nums[two] = nums[i].also { nums[i] = nums[two--] }
            } else i++
        }

    pub fn sort_colors(nums: &mut Vec<i32>) {
        let (mut cnt, mut j) = ([0, 0, 0], 0);
        for &n in &*nums { cnt[n as usize] += 1 }
        for i in 0..cnt.len() {
            nums[j..j + cnt[i]].fill(i as _);
            j += cnt[i]
        }
    }