950. Reveal Cards In Increasing Order - Explanation
Description
Reorder the distinct card values in deck so that the following process reveals them in increasing order:
- Reveal and remove the top card.
- If any cards remain, move the next top card to the bottom without revealing it.
- Repeat until the deck is empty.
Return the initial arrangement from top to bottom. The first array entry is the top card. Return the arrangement to start with, rather than the sequence of revealed values.
Example 1:
Input: deck = [4,1,3,2]
Output: [1,3,2,4]Explanation: Start with [1,3,2,4]. Reveal 1 and move 3 to the bottom, leaving [2,4,3]. Reveal 2 and move 4 to the bottom, leaving [3,4]. The final reveals are 3 and 4, so the revealed values are increasing.
Example 2:
Input: deck = [9]
Output: [9]Explanation: There is only one card. Placing 9 at the top reveals 9 immediately.
Example 3:
Input: deck = [8,3,5]
Output: [3,8,5]Explanation: Starting with [3,8,5], reveal 3 and move 8 to the bottom. The remaining deck is [5,8], which reveals 5 and then 8.
Constraints:
1 <= deck.length <= 10001 <= deck[i] <= 1000000- All card values are distinct.
Topics
Prerequisites
Before attempting this problem, you should be comfortable with:
- Queue Data Structure - Understanding FIFO operations (enqueue, dequeue) is essential for simulating the card reveal process
- Deque (Double-ended Queue) - Some solutions use deque for efficient insertion/removal at both ends
- Sorting - The solution requires sorting the deck to process cards in order
- Simulation Techniques - The problem involves simulating a process either forward or in reverse
1. Simulation Using Queue - I
Intuition
The reveal process takes the top card, then moves the next card to the bottom. To arrange cards so they reveal in increasing order, we simulate this process in reverse by tracking positions. We use a queue of indices representing available positions. As we assign sorted values in order, each assignment follows the reveal pattern: take the front index, then rotate the next index to the back.
Algorithm
- Sort the deck in ascending order.
- Create a result array
resand a queueqcontaining indices0throughn-1. - For each card value
numin the sorted deck:- Dequeue the front index
iand place the current value there. - If the queue is not empty, move the new front index to the back (simulating the card rotation).
- Dequeue the front index
- Return the result array.
Time & Space Complexity
- Time complexity:
- Space complexity:
2. Simulation Using Queue - II
Intuition
Another approach processes the sorted deck from largest to smallest. We build the final arrangement by simulating the reverse of the reveal process: before placing each card, we rotate the bottom card to the top (undoing the move that would have happened during reveal). This builds the deck configuration backward.
Algorithm
- Sort the deck in ascending order.
- Initialize an empty queue
q. - Traverse the sorted deck from largest to smallest (using index
i):- If the queue is not empty, move the front element to the back (reverse rotation).
- Add the current card value to the queue.
- Extract elements from the queue in reverse order to form the result.
- Return the result array.
Time & Space Complexity
- Time complexity:
- Space complexity:
3. Simulation Using Deque
Intuition
A deque supports efficient operations at both ends, making it ideal for simulating the reverse reveal process. Starting with the largest card, we repeatedly move the back element to the front (reversing the bottom-to-top move), then insert the current card at the front. This directly constructs the deck arrangement.
Algorithm
- Sort the deck in ascending order.
- Initialize a deque
dqand add the largest card (last in sorted order). - Traverse the remaining cards from second largest to smallest (using index
i):- Move the back element to the front of the deque.
- Insert the current card at the front.
- Return the deque as the result array.
Time & Space Complexity
- Time complexity:
- Space complexity:
4. Simulation Using Two Pointers
Intuition
Instead of using a queue or deque, we can simulate the assignment directly on the result array. We track which positions are still empty and use a skip flag to alternate between placing a card and skipping a position (mirroring the reveal process). This approach uses constant extra space beyond the result array.
Algorithm
- Sort the deck in ascending order.
- Create a result array
resfilled with zeros (to mark empty positions). - Initialize a deck index
deckIndexpointing to the smallest card, a position pointeriat 0, and a skip flagskipset tofalse. - While cards remain to be placed:
- If the current position is empty (value is 0):
- If not skipping, place the current card and advance the deck index.
- Toggle the skip flag.
- Move to the next position (wrapping around with modulo).
- If the current position is empty (value is 0):
- Return the result array.
class Solution:
def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
n = len(deck)
res = [0] * n
skip = False
deckIndex, i = 0, 0
deck.sort()
while deckIndex < n:
if res[i] == 0:
if not skip:
res[i] = deck[deckIndex]
deckIndex += 1
skip = not skip
i = (i + 1) % n
return resTime & Space Complexity
- Time complexity:
- Space complexity:
- or space depending on the sorting algorithm.
- space for the output array.
Common Pitfalls
Forgetting to Sort the Deck First
A common mistake is attempting to simulate the reveal process without first sorting the deck. The algorithm relies on assigning cards from smallest to largest, so forgetting to sort results in an incorrect arrangement where cards do not reveal in increasing order.
Skipping the Queue Rotation Step
When simulating the reveal process, each card placement must be followed by rotating the next available index to the back of the queue. Forgetting this rotation step breaks the alternating pattern and places cards in wrong positions, causing the reveal sequence to be out of order.
Off-by-One Errors in Position Tracking
The skip-and-place pattern requires careful index management. A common error is miscounting positions or incorrectly handling the wrap-around when traversing the result array. This leads to cards being placed at incorrect indices or infinite loops when positions are not properly marked as filled.
Sign in to join the discussion