950. Reveal Cards In Increasing Order - Explanation

1. Simulation Using Queue - I

Intuition

The reveal process takes the top card, then moves the next card to the bottom. To arrange cards so they reveal in increasing order, we simulate this process in reverse by tracking positions. We use a queue of indices representing available positions. As we assign sorted values in order, each assignment follows the reveal pattern: take the front index, then rotate the next index to the back.

Algorithm

Sort the deck in ascending order.
Create a result array res and a queue q containing indices 0 through n-1.
For each card value num in the sorted deck:
- Dequeue the front index i and place the current value there.
- If the queue is not empty, move the new front index to the back (simulating the card rotation).
Return the result array.

class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        deck.sort()
        res = [0] * len(deck)
        q = deque(range(len(deck)))

        for num in deck:
            i = q.popleft()
            res[i] = num
            if q:
                q.append(q.popleft())

        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

2. Simulation Using Queue - II

Intuition

Another approach processes the sorted deck from largest to smallest. We build the final arrangement by simulating the reverse of the reveal process: before placing each card, we rotate the bottom card to the top (undoing the move that would have happened during reveal). This builds the deck configuration backward.

Algorithm

Sort the deck in ascending order.
Initialize an empty queue q.
Traverse the sorted deck from largest to smallest (using index i):
- If the queue is not empty, move the front element to the back (reverse rotation).
- Add the current card value to the queue.
Extract elements from the queue in reverse order to form the result.
Return the result array.

class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        deck.sort()
        q = deque()
        for i in range(len(deck) - 1, -1, -1):
            if q:
                q.append(q.popleft())
            q.append(deck[i])
        return list(q)[::-1]

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Simulation Using Deque

Intuition

A deque supports efficient operations at both ends, making it ideal for simulating the reverse reveal process. Starting with the largest card, we repeatedly move the back element to the front (reversing the bottom-to-top move), then insert the current card at the front. This directly constructs the deck arrangement.

Algorithm

Sort the deck in ascending order.
Initialize a deque dq and add the largest card (last in sorted order).
Traverse the remaining cards from second largest to smallest (using index i):
- Move the back element to the front of the deque.
- Insert the current card at the front.
Return the deque as the result array.

class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        deck.sort()
        dq = deque()
        dq.append(deck.pop())
        for i in range(len(deck) - 1, -1, -1):
            dq.appendleft(dq.pop())
            dq.appendleft(deck[i])
        return list(dq)

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

4. Simulation Using Two Pointers

Intuition

Instead of using a queue or deque, we can simulate the assignment directly on the result array. We track which positions are still empty and use a skip flag to alternate between placing a card and skipping a position (mirroring the reveal process). This approach uses constant extra space beyond the result array.

Algorithm

Sort the deck in ascending order.
Create a result array res filled with zeros (to mark empty positions).
Initialize a deck index deckIndex pointing to the smallest card, a position pointer i at 0, and a skip flag skip set to false.
While cards remain to be placed:
- If the current position is empty (value is 0):
  - If not skipping, place the current card and advance the deck index.
  - Toggle the skip flag.
- Move to the next position (wrapping around with modulo).
Return the result array.

class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        n = len(deck)
        res = [0] * n
        skip = False
        deckIndex, i = 0, 0

        deck.sort()

        while deckIndex < n:
            if res[i] == 0:
                if not skip:
                    res[i] = deck[deckIndex]
                    deckIndex += 1
                skip = not skip
            i = (i + 1) % n

        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity:
- $O(1)$ or $O(n)$ space depending on the sorting algorithm.
- $O(n)$ space for the output array.

Common Pitfalls

Forgetting to Sort the Deck First

A common mistake is attempting to simulate the reveal process without first sorting the deck. The algorithm relies on assigning cards from smallest to largest, so forgetting to sort results in an incorrect arrangement where cards do not reveal in increasing order.

Skipping the Queue Rotation Step

When simulating the reveal process, each card placement must be followed by rotating the next available index to the back of the queue. Forgetting this rotation step breaks the alternating pattern and places cards in wrong positions, causing the reveal sequence to be out of order.

Off-by-One Errors in Position Tracking

The skip-and-place pattern requires careful index management. A common error is miscounting positions or incorrectly handling the wrap-around when traversing the result array. This leads to cards being placed at incorrect indices or infinite loops when positions are not properly marked as filled.