LeetCode 950: Reveal Cards In Increasing Order

Problem Restatement

We are given an array:

deck

Each card has a unique integer.

We may reorder the deck however we want. The first element of the returned array is considered the top of the deck.

Then the reveal process works like this:

1. Reveal the top card and remove it.
2. If cards remain, move the next top card to the bottom.
3. Repeat until all cards are revealed.

Return an initial deck order such that the cards are revealed in increasing order.

The official statement asks for an ordering of the deck that reveals the cards in increasing order. It also notes that the first entry in the answer is the top of the deck.

Input and Output

Function shape:

class Solution:
    def deckRevealedIncreasing(self, deck: list[int]) -> list[int]:
        ...

Examples

Example 1:

deck = [17, 13, 11, 2, 3, 5, 7]

One correct output is:

[2, 13, 3, 11, 5, 17, 7]

Reveal process:

reveal 2
move 13 to bottom
reveal 3
move 11 to bottom
reveal 5
move 17 to bottom
reveal 7
move 13 to bottom
reveal 11
move 17 to bottom
reveal 13
reveal 17

The revealed order is:

[2, 3, 5, 7, 11, 13, 17]

which is increasing.

Example 2:

deck = [1, 1000]

A valid answer is:

[1, 1000]

The reveal order is already increasing.

First Thought

The final revealed order must be the sorted deck.

So instead of guessing the card order directly, we can simulate which positions are revealed first.

For example, with n cards, the reveal process reveals some index first, then moves the next index to the back, then reveals another index.

If we know the order of revealed positions, we can place the sorted cards into those positions.

Key Insight

Use a queue of indices.

The queue represents positions in the deck that are still unrevealed.

At each step:

1. Pop the front index.
2. Put the next smallest card there.
3. Move the next front index to the back.

This simulates the reveal process on positions instead of cards.

Because we assign sorted cards in the exact order positions are revealed, the actual reveal process will output cards in increasing order.

Algorithm

Sort the deck:

deck.sort()

Create an answer array:

ans = [0] * len(deck)

Create a queue of indices:

queue = deque(range(len(deck)))

For each card in sorted order:

1. Remove the front index.
2. Place the card at that index.
3. If the queue still has indices, move the next front index to the back.

Return ans.

Walkthrough

Use:

deck = [17, 13, 11, 2, 3, 5, 7]

Sort:

[2, 3, 5, 7, 11, 13, 17]

Initial index queue:

[0, 1, 2, 3, 4, 5, 6]

Return:

[2, 13, 3, 11, 5, 17, 7]

Correctness

The queue stores exactly the deck positions that have not yet been revealed.

At each step, the forward reveal process would reveal the current top position. The algorithm removes that same front index from the queue and assigns the next smallest card to it.

Then the forward process would move the next top card to the bottom. The algorithm performs the same operation on the remaining indices by moving the next front index to the back.

Therefore, the algorithm computes the exact order in which positions will be revealed.

The deck is sorted before assignment. The first revealed position receives the smallest card, the second revealed position receives the second smallest card, and so on.

So when the returned deck is processed by the reveal rules, the revealed cards appear in sorted increasing order.

Therefore, the returned deck is valid.

Complexity

Let:

n = len(deck)

Implementation

from collections import deque

class Solution:
    def deckRevealedIncreasing(self, deck: list[int]) -> list[int]:
        deck.sort()

        n = len(deck)
        ans = [0] * n
        queue = deque(range(n))

        for card in deck:
            index = queue.popleft()
            ans[index] = card

            if queue:
                queue.append(queue.popleft())

        return ans

Code Explanation

Sort the cards so we assign them in the desired reveal order:

deck.sort()

Create the result array:

ans = [0] * n

Create a queue of positions:

queue = deque(range(n))

For each sorted card, choose the next revealed position:

index = queue.popleft()
ans[index] = card

Then simulate moving the next top position to the bottom:

if queue:
    queue.append(queue.popleft())

At the end, ans is the required starting deck order.

Testing

from collections import deque

def reveal_order(deck):
    q = deque(deck)
    revealed = []

    while q:
        revealed.append(q.popleft())

        if q:
            q.append(q.popleft())

    return revealed

def run_tests():
    s = Solution()

    ans = s.deckRevealedIncreasing([17, 13, 11, 2, 3, 5, 7])
    assert ans == [2, 13, 3, 11, 5, 17, 7]
    assert reveal_order(ans) == [2, 3, 5, 7, 11, 13, 17]

    ans = s.deckRevealedIncreasing([1, 1000])
    assert ans == [1, 1000]
    assert reveal_order(ans) == [1, 1000]

    ans = s.deckRevealedIncreasing([1])
    assert ans == [1]
    assert reveal_order(ans) == [1]

    ans = s.deckRevealedIncreasing([4, 3, 2, 1])
    assert reveal_order(ans) == [1, 2, 3, 4]

    print("all tests passed")

run_tests()