LeetCode Entry

950. Reveal Cards In Increasing Order

10.04.2024 medium 2024 kotlin rust

Sort cards by rules: take top, next goes bottom

950. Reveal Cards In Increasing Order medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/567

Problem TLDR

Sort cards by rules: take top, next goes bottom #medium

Intuition

Let’s reverse the problem: go from the last number, then prepend a value and rotate.

Approach

We can use ArrayDeque in Kotlin and just a vec[] in Rust (however VecDeque is also handy and make O(1) operation instead of O(n)).

Complexity

• Time complexity: \(O(nlogn)\), O(n^2) for vec[] solution, but the real time is still 0ms.

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

Code

    fun deckRevealedIncreasing(deck: IntArray) = with(ArrayDeque<Int>()) {
        deck.sortDescending()
        for (n in deck) {
            if (size > 0) addFirst(removeLast())
            addFirst(n)
        }
        toIntArray()
    }

    pub fn deck_revealed_increasing(mut deck: Vec<i32>) -> Vec<i32> {
        deck.sort_unstable_by_key(|n| -n);
        let mut queue = vec![];
        for n in deck {
            if queue.len() > 0 { queue.rotate_right(1) }
            queue.insert(0, n)
        }
        queue
    }