Reveal Cards In Increasing Order
Last Updated: March 29, 2026
Understanding the Problem
This problem asks us to figure out how to arrange a deck of cards so that when we repeatedly take the top card and move the next card to the bottom, the revealed cards come out in sorted (increasing) order.
Think of it like this: you know the reveal process (take top, move next to bottom, repeat), and you know the desired output (sorted order). You need to work backwards to find the starting arrangement.
The key insight is that the reveal process is deterministic. Given the deck size, we can figure out exactly which position gets revealed at each step. So the question becomes: in what order do the positions get visited? Once we know that, we just place the sorted values into those positions.
Key Constraints:
1 <= deck.length <= 1000-> With at most 1,000 cards, even an O(n^2) approach is fine. But the natural simulation approach is O(n log n) due to sorting, which is more than enough.1 <= deck[i] <= 10^6-> Positive integers only. No negatives or zeros to worry about.- All values are unique -> No need to handle duplicates or tie-breaking.
Approach 1: Brute Force (Try All Permutations)
Intuition
The most straightforward idea: try every possible ordering of the deck, simulate the reveal process for each one, and check if the revealed order is sorted. Return the first ordering that works.
This is pure brute force. There are n! permutations of n cards, and for each permutation we need O(n) to simulate the reveal. It works, but only for tiny inputs.
Algorithm
- Sort the deck to get the target reveal order.
- Generate all permutations of the deck.
- For each permutation, simulate the reveal process (take top, move next to bottom, repeat).
- If the simulated reveal order matches the sorted order, return this permutation.
Example Walkthrough
Input:
Sorted target: [2, 3, 5, 7, 11, 13, 17]
We try permutations until we find one where the reveal process produces the sorted order. The winning arrangement is [2, 13, 3, 11, 5, 17, 7]:
Code
- Time Complexity: O(n! * n). There are n! permutations, and for each one we simulate the reveal process in O(n). This is astronomically slow for anything beyond n = 10.
- Space Complexity: O(n). We use a queue of size n for the simulation and an array of size n for tracking used elements.
The brute force tries every arrangement blindly. Instead of guessing, what if we simulated the reveal process on indices to figure out exactly where each sorted value should go?
Approach 2: Queue Simulation (Optimal)
Intuition
Here is the key realization: the reveal process is completely determined by the number of cards. It does not depend on the values at all. Given n cards, the process always visits positions in the same order. So we can simulate the reveal process on indices (0, 1, 2, ..., n-1) to figure out the reveal order, then place sorted values into those positions.
Put index 0 through n-1 into a queue. Simulate the exact reveal process: dequeue the front (this position is revealed first), then dequeue-and-enqueue the next (move it to the bottom). The order in which indices come out tells us which position is revealed at each step.
Now the mapping is straightforward. Sort the deck values. The smallest value should go into the position that is revealed first. The second smallest into the position revealed second. And so on.
The reveal process visits deck positions in a fixed order determined entirely by the deck size. By simulating that process on indices, we discover exactly which position gets revealed 1st, 2nd, 3rd, and so on. Placing sorted values into those positions in order guarantees that when the actual reveal happens, the values come out sorted.
It is essentially a mapping problem. We compute the function "reveal step k maps to position p(k)" and then set result[p(k)] = sorted[k] for all k. The queue simulation is just an efficient way to compute that mapping.
Algorithm
- Sort the deck values in increasing order.
- Create a queue containing indices 0, 1, 2, ..., n-1.
- Simulate the reveal process on this queue of indices:
- Dequeue the front index. This is the position revealed at this step.
- If the queue is not empty, dequeue the next front index and enqueue it to the back (simulating "move to bottom").
- As you dequeue each index, assign the next sorted value to that position in the result array.
- Return the result array.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting takes O(n log n). The queue simulation processes each index exactly once with O(1) dequeue/enqueue operations, so the simulation is O(n). The total is dominated by sorting.
- Space Complexity: O(n). We use a queue of n indices and a result array of size n.
Approach 2 is already optimal in terms of time complexity. But there is an alternative way to think about it: instead of simulating forward on indices, what if we built the deck backwards from the last revealed card?
Approach 3: Reverse Simulation with Deque
Intuition
Instead of simulating forward (figuring out where each sorted value goes), we can work backwards. Start with the largest card (the last one to be revealed) and reconstruct the deck by reversing each step.
In the forward process, each step does: (1) reveal the top card, (2) move the next top card to the bottom. Reversing this means: (1) move the bottom card to the top, (2) place the new card on top.
So we start with an empty deque, iterate through the sorted values from largest to smallest, and for each value: move the back of the deque to the front, then push the current value to the front. At the end, the deque contains the answer.
Every step of the forward reveal process is invertible. "Reveal top card" undoes to "place card on top." "Move next card to bottom" undoes to "move bottom card to top." By applying these inverse operations in reverse order (from the last revealed card to the first), we reconstruct the original deck arrangement.
This works because the reveal process is deterministic and reversible. No information is lost at any step, so we can always uniquely reconstruct the previous state from the current state plus the knowledge of which card was revealed.
Algorithm
- Sort the deck in increasing order.
- Initialize an empty deque.
- Iterate from the largest value down to the smallest:
- If the deque is not empty, move the element at the back of the deque to the front.
- Push the current value to the front of the deque.
- Convert the deque to an array and return it.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting takes O(n log n). The deque operations (push front, pop back) are each O(1), and we do n iterations, so the simulation is O(n). Total: O(n log n).
- Space Complexity: O(n). We use a deque of up to n elements.