Reveal Cards In Increasing Order: Reverse Simulation with a Deque

You have a deck of cards, and you want to reorder the deck so that when you repeatedly reveal the top card (removing it) and then move the next top card to the bottom, the revealed cards come out in increasing order. This is LeetCode 950: Reveal Cards In Increasing Order, a medium problem that combines sorting with a simulation twist.

The problem

Given an integer array deck, reorder it so that the following process reveals the cards in increasing order:

1. Take the top card off the deck and reveal it.
2. If there are still cards in the deck, move the next top card to the bottom of the deck.
3. Repeat until all cards are revealed.

Return the deck ordering that produces a sorted reveal sequence.

Why this problem matters

This problem teaches you to think backwards. The reveal process is easy to simulate forwards, but the real challenge is figuring out the initial arrangement that produces the desired output. Problems like this train you to reverse-engineer a process, a skill that appears in scheduling, task ordering, and reconstruction problems throughout competitive programming and interviews.

It also reinforces the idea that a deque (double-ended queue) is the right tool when you need efficient operations at both ends. Recognizing when to reach for a deque instead of a plain list can make the difference between an elegant O(n) solution and a clunky O(n^2) one.

The brute force approach

One way to think about brute force is to try all permutations of the deck, simulate the reveal process for each one, and check if the revealed order is sorted. For a deck of size n, that means n! permutations, each requiring O(n) to simulate.

from itertools import permutations

def deck_revealed_increasing_brute(deck):
    target = sorted(deck)
    for perm in permutations(deck):
        cards = list(perm)
        revealed = []
        while cards:
            revealed.append(cards.pop(0))
            if cards:
                cards.append(cards.pop(0))
        if revealed == target:
            return list(perm)
    return []

This is O(n! * n) and completely impractical for any reasonable input size. We need a smarter approach.

The key insight: simulate the index placement

Instead of trying to reverse the reveal process by working backwards through the cards, you can simulate the reveal process on the indices of the result array. Here is the idea:

1. Sort the input deck.
2. Create a deque containing the indices [0, 1, 2, ..., n-1].
3. For each card in sorted order, pop the front index from the deque and place the card at that position in the result. Then pop the next front index and push it to the back (simulating the "move to bottom" step).

The deque of indices mirrors exactly what the reveal process does, but instead of revealing cards, you are deciding where each sorted card should go.

Walking through it step by step

Let's trace through deck = [17, 13, 11, 2, 3, 5, 7]. We sort it to get [2, 3, 5, 7, 11, 13, 17], then use a deque of indices to place each card.

The result [2, 13, 3, 11, 5, 17, 7] is the deck ordering that, when you perform the reveal process, produces cards in the order 2, 3, 5, 7, 11, 13, 17.

The solution

from collections import deque

def deckRevealedIncreasing(deck):
    n = len(deck)
    deck.sort()
    indices = deque(range(n))
    result = [0] * n
    for card in deck:
        result[indices.popleft()] = card
        if indices:
            indices.append(indices.popleft())
    return result

The algorithm has three parts:

1. Sort the deck so you process cards from smallest to largest.
2. Initialize a deque with indices 0 through n-1. This deque simulates which position gets filled next.
3. For each sorted card, pop the front index and place the card there. Then pop the next front index and send it to the back, mirroring the "move next card to bottom" step.

When the loop finishes, every position in result has been filled with the correct card. The deque ensures the placement order matches the reveal process.

Complexity analysis

Sorting dominates the time complexity. The deque simulation is O(n) because each index is pushed and popped at most twice (once for placement, once for the "move to bottom" step). Total: O(n log n) time and O(n) space.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Sort-then-assign

Many problems follow the pattern of sorting the input first, then using the sorted order to drive placement or comparison logic. In this problem, sorting tells you the order in which cards should be revealed. In Sort an Array, you learn the sorting primitives. In Advantage Shuffle, you sort both arrays to greedily assign the best matchups. The pattern is the same: sort first to establish an ordering, then use that ordering to build the answer.

2. Deque simulation

Using a deque to simulate a process where elements move from front to back is a pattern that recurs in queue-based problems. Here, the deque tracks which indices are "next" in the reveal order. In Queue Reconstruction by Height, you use a similar idea of placing elements in specific positions based on a sorted order. The deque gives you O(1) operations at both ends, which keeps the simulation efficient.

Edge cases

• Single card. With deck = [5], the answer is [5]. No reveal or move step happens.
• Two cards. With deck = [2, 1], you reveal the top card (should be 1), then the second card is 2. So the result is [1, 2].
• Already sorted input. The algorithm handles this without special cases. Sorting a sorted array is a no-op, and the deque simulation still produces the correct arrangement.
• All identical values. If every card has the same value, any ordering works, and the algorithm returns a valid one.
• Large deck. The O(n log n) time means even n = 1000 runs instantly.

Common mistakes

1. Simulating the reveal process forwards and trying to reverse it manually. Some people try to work backwards through the reveal steps, reversing each operation. This is doable but error-prone. The deque-of-indices approach avoids the reversal entirely.

2. Using a list instead of a deque. If you use a Python list and call pop(0), each pop is O(n) because it shifts all elements. With n pops, that makes the simulation O(n^2). A deque gives O(1) pops from both ends.

3. Forgetting the "move to bottom" step for the last card. When only one card remains, there is no card to move to the bottom. The if indices check prevents an error here.

4. Not sorting the deck first. The entire approach depends on processing cards in increasing order. Skipping the sort produces garbage output.

From understanding to recall

You understand the deque simulation now. Sort the cards, use a deque of indices to mirror the reveal process, and place each card at the position the deque tells you. The logic is clean and the code is short.

But will you remember it in two weeks? The tricky part is not the code itself. It is the mental model: "simulate the reveal process on indices, not on cards." That insight is what you need to recall under pressure, and it fades quickly without practice.

Spaced repetition locks it in. You write the deque simulation from scratch at increasing intervals, each time reinforcing the connection between the problem pattern and the solution technique. After a few rounds, the approach is automatic. You see "reorder so a process produces sorted output" and immediately think "sort, deque of indices, simulate."

The sort-then-assign and deque simulation patterns are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the insights stick.

Related posts

• Sort an Array - The sorting foundation used as the first step in this solution
• Queue Reconstruction by Height - Another problem where sorting drives placement into specific positions
• Advantage Shuffle - Sort-then-assign with a greedy matching strategy

CodeBricks breaks the reveal cards in increasing order LeetCode problem into its sort-then-assign and deque simulation building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a simulation-based ordering question shows up in your interview, you do not think about it. You just write it.