A Deck That Reveals in Order

Medium

A magician holds a face-down deck of cards, each showing a different number. The numbers are given in cards in no particular order. The trick repeats while any cards are left in hand: 1. Turn over the top card and put it on the table. 2. If the deck is not empty, take the next top card without looking and slide it under the bottom of the deck. Arrange the deck so the cards come out in strictly increasing order. Return that deck as a list, with the top card first.

Example 1

cards=[40, 10, 30, 20] → [10, 30, 20, 40]

Deck [10, 30, 20, 40]: show 10, move 30 down → [20, 40, 30]; show 20, move 40 down → [30, 40]; show 30, move 40 down → [40]; show 40. The order is 10, 20, 30, 40.

Example 2

cards=[9, 4, 7] → [4, 9, 7]

Deck [4, 9, 7]: show 4, move 9 down → [7, 9]; show 7, move 9 down → [9]; show 9.

Example 3

cards=[5] → [5]

Constraints

1 ≤ len(cards) ≤ 1000
1 ≤ cards[i] ≤ 10⁶
All numbers in cards are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Queue Array Sorting Simulation

Similar problems

Shuttle Seat Plan Medium Last One in the Circle Medium Cross Out the Smallest First Medium Rounds of Row Maximums Medium Pallets After the Moves Medium

Input

cards=[40, 10, 30, 20]

Expected

[10, 30, 20, 40]

Run checks the first 3 tests in your browser. Submit checks all 75 tests on the server, hidden ones included.