Reveal Cards In Increasing Order
Medium · Stack & Strings · Array · Queue · Sorting · Simulation
Problem
You have a deck of cards with distinct integers, deck, and you may arrange it in any order. All cards start face down. Then you repeat:
- Reveal the top card and remove it from the deck.
- If cards remain, move the next top card to the bottom of the deck.
- Stop when every card has been revealed.
Return an ordering of the deck (first element = top card) that makes the cards get revealed in increasing order.
Examples
Input: deck = [17,13,11,2,3,5,7] Output: [2,13,3,11,5,17,7]
Reveal 2, move 13 down, reveal 3, move 11 down, reveal 5, move 17 down, reveal 7, move 13 down, reveal 11, move 17 down, reveal 13, then 17.
Input: deck = [5,1,3] Output: [1,5,3]
Reveal 1, move 5 down, reveal 3, then 5.
Input: deck = [8] Output: [8]
A single card is revealed at once.
Constraints
- 1 <= len(deck) <= 1000
- 1 <= deck[i] <= 10^6
- All values in deck are distinct
Approaches
- Baseline: undo the routine with list inserts — time O(n²), space O(n)
Follow-up
The trick is to simulate on positions instead of values. The use cases run the routine forward on a given deck and generalize the move to k cards at a time.
Related problems
Start free on Cariara · Coding problems · System design studio
