Reveal Cards In Increasing Order - Solution & Explanation
Problem Statement
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:
- Take the top card of the deck, reveal it, and take it out of the deck.
- If there are still cards in the deck then put the next top card of the deck at the bottom of the deck.
- If there are still unrevealed cards, go back to step 1. Otherwise, stop.
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] <= 106- All the values of
deckare unique.
Approach Overview
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 1: Using a Queue to Simulate the Process
This approach involves using a queue to simulate the process of revealing cards in increasing order. The given deck is first sorted to achieve this order. We then place the lowest cards at the positions where they will eventually be revealed.
The process is as follows:
- Sort the deck.
- Initialize an empty queue and the result deck with the same size as the input deck.
- Place the indices of the result deck into the queue.
- Iterate over the sorted deck; for every card, dequeue two indices (one for placing the card and another for recycling the top card to the bottom of the deck).
The card is placed at the index dequeued first, and after checking if there are still indices left, the second index is enqueued to the queue for the recycling process.
We use a deque to simulate the revealing process according to the problem's steps. By sorting the deck, we prepare to place the smallest card first and follow the steps iteratively to position each card correctly.
Complexity
Time Complexity: O(n log n), where n is the number of cards, because we sort the deck first. Space Complexity: O(n), since we use a deque to manage the card indices.
Approach 2: Mathematical Induction Method
Consider using a mathematical pattern to determine the correct order of cards. Start by handling small cases and rebalance the reordering according to the general steps defined. This approach focuses on finding the sequence by mathematical induction, considering the card's positions multiplication pattern to simulate the reveal process. Given the position pos[i], the card is added during the iteration, assume it follows a position pattern according to pos[i - 2 ^ {k-t}].
Mathematical deduction does not require additional changes, this code finds the correct order for revealing cards using pattern observation and queue manipulation.
Complexity
Time Complexity: O(n log n), caused by sorting. Space Complexity: Approximates O(n) due to storage requirements.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Using a Queue to Simulate the Process | Time Complexity: O(n log n), where n is the number of cards, because we sort the deck first. Space Complexity: O(n), since we use a deque to manage the card indices. |
| Mathematical Induction Method | Time Complexity: O(n log n), caused by sorting. Space Complexity: Approximates O(n) due to storage requirements. |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Reveal Cards In Increasing Order - Leetcode 950 - Python • NeetCodeIO • 20,220 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Reveal Cards In Increasing Order easy or hard?
Reveal Cards In Increasing Order Python/Java solution
How to solve Reveal Cards In Increasing Order in O(n)?
What is the best approach for Reveal Cards In Increasing Order?
Is Reveal Cards In Increasing Order asked at Google/Amazon/Meta?
What data structure is used in Reveal Cards In Increasing Order?
What is the time complexity of Reveal Cards In Increasing Order?
Ready to solve this problem?
Practice Reveal Cards In Increasing Order with our built-in code editor and test cases.
Practice on FleetCode