LeetCode 950 - Reveal Cards In Increasing Order
The problem gives us a deck of unique integer cards and asks us to arrange the deck so that a very specific reveal process produces the cards in increasing order. The reveal process works like this: 1. Reveal the top card and remove it from the deck. 2.
Difficulty: 🟡 Medium
Topics: Array, Queue, Sorting, Simulation
Solution
Problem Understanding
The problem gives us a deck of unique integer cards and asks us to arrange the deck so that a very specific reveal process produces the cards in increasing order.
The reveal process works like this:
- Reveal the top card and remove it from the deck.
- Move the next top card to the bottom of the deck.
- Repeat until no cards remain.
The important detail is that we are allowed to reorder the deck before the process starts. Our task is to find one initial ordering such that the revealed sequence becomes sorted in ascending order.
For example, suppose the revealed order must become:
2, 3, 5, 7, 11, 13, 17
We need to determine what initial arrangement causes the reveal simulation to output exactly that sequence.
The input is an integer array deck, where every value is unique. The output is another array containing the same values, but arranged so the reveal process produces increasing order.
The constraints are relatively small:
1 <= deck.length <= 1000- All card values are unique
- Card values can be as large as
10^6
Because the input size is only 1000, we do not need extremely advanced optimizations. An O(n log n) solution is more than sufficient.
Several edge cases are important:
- A deck containing only one card. The answer is simply the original card.
- A deck containing two cards. The reveal process becomes trivial.
- Already sorted input. The correct output is usually not the same as the sorted array.
- Large card values. Since only ordering matters, magnitude does not affect the algorithm.
- Small deck sizes. Queue operations must correctly handle empty states after removals.
The problem guarantees that all values are unique, which simplifies the logic because we never need to handle ties.
Approaches
Brute Force Approach
A brute force solution would try every possible ordering of the deck and simulate the reveal process for each arrangement.
For every permutation:
- Simulate the reveal operation.
- Record the revealed sequence.
- Check whether the revealed sequence is sorted in increasing order.
This approach is correct because it exhaustively checks all possible deck arrangements. Eventually, it will find the valid ordering.
However, this method is computationally infeasible. A deck of size n has n! permutations. Even for relatively small values like n = 10, the number of permutations becomes enormous.
The simulation itself costs O(n) time, so the total complexity becomes approximately O(n! * n), which is far too slow.
Optimal Approach
The key insight is to reverse the reveal process instead of guessing arrangements.
Suppose we already know the order in which cards must be revealed:
sorted(deck)
Instead of simulating forward, we reconstruct the original deck backward.
The forward process is:
- Reveal top card.
- Move next top card to bottom.
The reverse process becomes:
- Take the last revealed card and place it at the front.
- Reverse the rotation by moving the bottom card to the top before inserting the next value.
A simpler and more intuitive version uses a queue of indices.
We simulate the positions where cards will be revealed:
- Sort the deck.
- Maintain a queue containing indices
0...n-1. - Place the smallest card into the first revealed index.
- Move the next index to the back of the queue to simulate the rotation step.
- Continue until all cards are placed.
This directly models the reveal process and produces the correct initial arrangement efficiently.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n! * n) | O(n) | Tries every possible deck ordering |
| Optimal | O(n log n) | O(n) | Uses sorting and queue simulation |
Algorithm Walkthrough
- Sort the deck in ascending order.
The reveal process must produce cards in increasing order, so the first revealed card should be the smallest value, the second revealed card should be the second smallest value, and so on. 2. Create a queue containing all deck indices.
If the deck has length n, initialize a queue with:
[0, 1, 2, ..., n-1]
These indices represent positions in the final answer array.
3. Create an answer array of size n.
This array will eventually store the initial deck ordering. 4. Process cards from smallest to largest.
For each card in the sorted deck:
- Remove the front index from the queue.
- Place the current card into that position in the answer array.
This works because the front of the queue represents the next position that would be revealed. 5. Simulate the rotation step.
After placing a card:
-
If the queue is not empty:
-
Remove the next front index.
-
Push it to the back of the queue.
This mirrors the operation of moving the next top card to the bottom of the deck. 6. Continue until all cards are placed.
Once all sorted cards are assigned to reveal positions, the answer array represents the required initial deck ordering.
Why it works
The queue always maintains the order in which positions will be revealed during the simulation. By assigning sorted cards to reveal positions in ascending order, we guarantee that the reveal process outputs cards in increasing order. The rotation of indices exactly mirrors the movement of cards in the original problem statement, so the constructed arrangement is correct.
Python Solution
from collections import deque
from typing import List
class Solution:
def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
n = len(deck)
sorted_deck = sorted(deck)
index_queue = deque(range(n))
result = [0] * n
for card in sorted_deck:
reveal_index = index_queue.popleft()
result[reveal_index] = card
if index_queue:
index_queue.append(index_queue.popleft())
return result
The implementation begins by sorting the input deck because we know the reveal order must be increasing.
A deque is used to efficiently simulate queue behavior. The queue stores indices instead of card values. This is an important design choice because we are determining where each sorted card should be placed in the final arrangement.
The result array stores the reconstructed deck order.
For every card in the sorted deck:
- The algorithm removes the front index from the queue.
- That index represents the next revealed position.
- The current smallest remaining card is placed there.
After placement, the next index is moved to the back of the queue to simulate the card rotation operation described in the problem.
The process continues until all cards are assigned.
Because deque operations are O(1), the simulation is efficient.
Go Solution
package main
import "sort"
func deckRevealedIncreasing(deck []int) []int {
n := len(deck)
sort.Ints(deck)
queue := make([]int, n)
for i := 0; i < n; i++ {
queue[i] = i
}
result := make([]int, n)
for _, card := range deck {
revealIndex := queue[0]
queue = queue[1:]
result[revealIndex] = card
if len(queue) > 0 {
moved := queue[0]
queue = queue[1:]
queue = append(queue, moved)
}
}
return result
}
The Go solution follows the same logic as the Python version.
One difference is that Go does not provide a built in deque structure in the standard library, so the queue is simulated using slices.
Removing the front element is done with:
queue = queue[1:]
Appending to the back uses:
queue = append(queue, moved)
Because the problem size is small, this implementation is fully efficient for the constraints.
There are no integer overflow concerns because values are only rearranged, not mathematically manipulated.
Worked Examples
Example 1
Input:
deck = [17,13,11,2,3,5,7]
Sorted deck:
[2,3,5,7,11,13,17]
Initial queue of indices:
[0,1,2,3,4,5,6]
| Card | Reveal Index | Result After Placement | Queue After Rotation |
|---|---|---|---|
| 2 | 0 | [2,0,0,0,0,0,0] | [2,3,4,5,6,1] |
| 3 | 2 | [2,0,3,0,0,0,0] | [4,5,6,1,3] |
| 5 | 4 | [2,0,3,0,5,0,0] | [6,1,3,5] |
| 7 | 6 | [2,0,3,0,5,0,7] | [3,5,1] |
| 11 | 3 | [2,0,3,11,5,0,7] | [1,5] |
| 13 | 1 | [2,13,3,11,5,0,7] | [5] |
| 17 | 5 | [2,13,3,11,5,17,7] | [] |
Final answer:
[2,13,3,11,5,17,7]
Example 2
Input:
deck = [1,1000]
Sorted deck:
[1,1000]
Initial queue:
[0,1]
| Card | Reveal Index | Result After Placement | Queue After Rotation |
|---|---|---|---|
| 1 | 0 | [1,0] | [1] |
| 1000 | 1 | [1,1000] | [] |
Final answer:
[1,1000]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n) | Sorting dominates the runtime |
| Space | O(n) | Queue and result array both require linear space |
The queue simulation itself runs in linear time because every index is pushed and popped a constant number of times. The sorting step costs O(n log n), which becomes the dominant factor in the overall complexity.
The auxiliary space usage is linear because we store both the result array and the queue of indices.
Test Cases
from typing import List
from collections import deque
class Solution:
def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
n = len(deck)
sorted_deck = sorted(deck)
queue = deque(range(n))
result = [0] * n
for card in sorted_deck:
idx = queue.popleft()
result[idx] = card
if queue:
queue.append(queue.popleft())
return result
solution = Solution()
# Provided example
assert solution.deckRevealedIncreasing([17,13,11,2,3,5,7]) == [2,13,3,11,5,17,7]
# Two element deck
assert solution.deckRevealedIncreasing([1,1000]) == [1,1000]
# Single element deck
assert solution.deckRevealedIncreasing([42]) == [42]
# Already sorted input
assert solution.deckRevealedIncreasing([1,2,3,4]) == [1,3,2,4]
# Reverse sorted input
assert solution.deckRevealedIncreasing([4,3,2,1]) == [1,3,2,4]
# Larger values
assert solution.deckRevealedIncreasing([1000000, 5, 999999]) == [5,1000000,999999]
# Odd number of cards
assert solution.deckRevealedIncreasing([9,7,5,3,1]) == [1,9,3,7,5]
# Even number of cards
assert solution.deckRevealedIncreasing([8,6,4,2]) == [2,6,4,8]
# Random ordering
assert solution.deckRevealedIncreasing([10,20,30,40,50]) == [10,50,20,40,30]
| Test | Why |
|---|---|
[17,13,11,2,3,5,7] |
Validates the main example |
[1,1000] |
Tests minimal nontrivial deck |
[42] |
Tests single element edge case |
[1,2,3,4] |
Ensures sorted input is handled correctly |
[4,3,2,1] |
Confirms ordering does not depend on input arrangement |
[1000000, 5, 999999] |
Tests large card values |
[9,7,5,3,1] |
Tests odd sized deck behavior |
[8,6,4,2] |
Tests even sized deck behavior |
[10,20,30,40,50] |
Tests generic ordering correctness |
Edge Cases
Single Card Deck
If the deck contains only one card, the reveal process immediately reveals that card and stops. This case can expose bugs in queue rotation logic because there is no second card to move to the bottom.
The implementation handles this naturally because after placing the only card, the queue becomes empty and the rotation step is skipped.
Two Card Deck
With two cards, the reveal process becomes very short:
- Reveal first card.
- Reveal second card.
A buggy implementation might incorrectly rotate indices after the queue becomes empty.
The solution explicitly checks:
if queue:
before performing the rotation step, preventing invalid operations.
Already Sorted Input
An important subtlety is that the answer is usually not the sorted deck itself.
For example:
[1,2,3,4]
does not reveal in increasing order if used directly.
A naive implementation might incorrectly assume sorting alone is sufficient. The queue simulation correctly computes the actual required arrangement.
Very Large Card Values
Card values may be as large as 10^6, but only relative ordering matters. The algorithm never performs arithmetic on card values, only comparisons during sorting.
As a result, large integers do not introduce overflow or precision problems.
Odd Versus Even Deck Sizes
The reveal and rotation process behaves slightly differently depending on whether the number of remaining cards is odd or even.
Incorrect queue manipulation can easily produce off by one errors in these situations. Because the algorithm directly simulates reveal positions step by step, both odd and even deck sizes are handled uniformly and correctly.