Reveal Cards in Increasing Order — Solution

Problem

You have a deck of cards with integer values. Simulate this process: reveal the top card, move the next top card to the bottom of the deck, and repeat until every card is revealed. Given any shuffled deck, rearrange it so that the cards are revealed in strictly increasing order.

• Input: deck = [17, 13, 11, 2, 3, 5, 7]
• Output: [2, 13, 3, 11, 5, 17, 7]
• Explanation: Starting from this arrangement, the cards are revealed as 2, 3, 5, 7, 11, 13, 17 — in increasing order.

Counter-example: the naively sorted arrangement [2, 3, 5, 7, 11, 13, 17] would reveal as 2, 5, 11, 17, 13, 3, 7 — not sorted, because the "move next card to bottom" step interleaves the positions.

Intuition

Instead of guessing a permutation and checking, figure out which deck position gets revealed first, second, third, and so on. Simulate the process using a queue of position indices: whichever index comes out first gets the smallest sorted value, whichever comes out second gets the next, and so on. One sort plus one linear pass is all you need.

Solution — Queue Simulation

Simulate the reveal order of positions using a queue, then fill those positions with sorted values in order.

1. Sort the deck to get the values in increasing order.
2. Initialize a queue with positions [0, 1, 2, ..., n-1].
3. For each sorted value: dequeue the front position (it is revealed next) and assign the value there. Then, if the queue is non-empty, dequeue the next position and re-enqueue it at the back (the "move to bottom" step).
4. Return the result array.

1from collections import deque
2
3def deckRevealedIncreasing(deck: list[int]) -> list[int]:
4    deck.sort()
5    n = len(deck)
6    position_queue = deque(range(n))  # simulate which index is revealed next
7    result = [0] * n
8
9    for value in deck:
10        reveal_pos = position_queue.popleft()  # this position is revealed next
11        result[reveal_pos] = value
12        if position_queue:
13            position_queue.append(position_queue.popleft())  # move next card to bottom
14
15    return result

Time: O(n log n) — dominated by sorting; the queue simulation itself is O(n). Space: O(n) — for the position queue and the result array.

Complexity Summary

Common Mistakes

• Simulating forward by trying permutations — trying all arrangements and checking which one reveals in sorted order requires O(n!) attempts; instead, simulate which index gets revealed in what order, then assign values directly.
• Omitting the "move next card to bottom" step — after revealing a card, the next top card must be dequeued and re-enqueued; skipping this means every other position is never visited.
• Applying the cycle step when the queue is empty — on the very last card there is no "next card" to rotate; calling popleft() on an empty deque raises an error, so guard with if position_queue.
• Using a list with pop(0) instead of a deque — list.pop(0) is O(n) per call, making the whole simulation O(n²); a deque.popleft() is O(1).
• Confusing the queue contents with card values — the queue holds position indices, not the card values; only the result array holds values.

Related Problems

• time-needed-to-buy-tickets — circular queue simulation where each person's turn depends on how many full rounds pass
• rotting-oranges — BFS queue that processes elements in a layer-by-layer simulation
• evaluate-reverse-polish-notation — stack-based simulation where the processing order drives the algorithm
• decode-string — stack simulation where nested structures must be unwound in the right sequence
• daily-temperatures — monotonic stack simulation where the order elements are processed determines correctness