Watch 10 video solutions for Reveal Cards In Increasing Order, a medium level problem involving Array, Queue, Sorting. This walkthrough by NeetCodeIO has 19,694 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array deck. There is a deck of cards where every card has a unique integer. The integer on the ith card is deck[i].
You can order the deck in any order you want. Initially, all the cards start face down (unrevealed) in one deck.
You will do the following steps repeatedly until all cards are revealed:
Return an ordering of the deck that would reveal the cards in increasing order.
Note that the first entry in the answer is considered to be the top of the deck.
Example 1:
Input: deck = [17,13,11,2,3,5,7] Output: [2,13,3,11,5,17,7] Explanation: We get the deck in the order [17,13,11,2,3,5,7] (this order does not matter), and reorder it. After reordering, the deck starts as [2,13,3,11,5,17,7], where 2 is the top of the deck. We reveal 2, and move 13 to the bottom. The deck is now [3,11,5,17,7,13]. We reveal 3, and move 11 to the bottom. The deck is now [5,17,7,13,11]. We reveal 5, and move 17 to the bottom. The deck is now [7,13,11,17]. We reveal 7, and move 13 to the bottom. The deck is now [11,17,13]. We reveal 11, and move 17 to the bottom. The deck is now [13,17]. We reveal 13, and move 17 to the bottom. The deck is now [17]. We reveal 17. Since all the cards revealed are in increasing order, the answer is correct.
Example 2:
Input: deck = [1,1000] Output: [1,1000]
Constraints:
1 <= deck.length <= 10001 <= deck[i] <= 106deck are unique.Problem Overview: You are given a deck of unique integers. Cards are revealed by repeatedly revealing the top card, then moving the next top card to the bottom of the deck. The task is to arrange the deck initially so that the revealed sequence appears in strictly increasing order.
Approach 1: Using a Queue to Simulate the Process (O(n log n) time, O(n) space)
The key observation is that the reveal process itself is deterministic. Instead of trying to guess the initial arrangement directly, simulate the positions where cards will be revealed. Start by sorting the deck so the smallest card should be revealed first. Maintain a queue containing indices 0..n-1, representing positions in the result array. Place the smallest card at the index popped from the queue. After placing a card, move the next index in the queue to the back to mimic the “move top card to bottom” rule. Continue until all cards are placed.
This approach uses a queue to simulate the reveal operation and a sorted array to guarantee increasing order. The simulation runs once per card, and sorting dominates the complexity. Time complexity is O(n log n) due to sorting, while the queue operations require O(n) space.
Approach 2: Mathematical Induction Method (Reverse Simulation) (O(n log n) time, O(n) space)
This method reconstructs the deck by reversing the reveal process. Instead of simulating forward, imagine building the deck from the largest card backward. Sort the cards in ascending order. Start from the largest card and repeatedly reconstruct the previous deck state: if the deck already has elements, move the last element to the front (the reverse of moving the top card to the bottom). Then insert the current card at the front.
The structure used here is typically a deque because it supports efficient front and back operations. Each step reverses the effect of the original reveal operation, gradually building the valid starting order. Sorting contributes O(n log n) time, while deque operations are O(1) each, leading to O(n) extra space.
Both strategies rely on sorting the deck first using a standard sorting algorithm, then simulating the reveal mechanics described in the problem. Conceptually, this is a classic simulation problem where understanding the sequence of operations is more important than complex data structures.
Recommended for interviews: The queue-based simulation is usually expected in interviews. It directly models the process described in the problem and clearly demonstrates understanding of queues and index simulation. The reverse (induction) method is elegant and slightly more clever, showing deeper insight into reversing operations, but interviewers typically expect the queue simulation first because it is easier to reason about and implement under time pressure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Queue Simulation with Sorted Deck | O(n log n) | O(n) | General solution; easiest to reason about and commonly expected in interviews |
| Mathematical Induction (Reverse Simulation) | O(n log n) | O(n) | When you want a more elegant reverse-process solution using deque operations |