405. Reveal in Order
A magician owns a deck of cards, each with a distinct number, and performs a dealing ritual. She repeats the following until the deck is empty: show the top card and put it aside, then (if cards remain) move the new top card to the bottom of the deck. She wants the cards to be shown in strictly increasing order of their numbers.
Given the numbers in deck, return an arrangement of the deck, listed from top to bottom, for which the ritual shows the numbers in increasing order. All numbers are distinct, so exactly one arrangement works. Instead of guessing, think about which position of the deck the smallest card must occupy, then the second smallest, and so on.
Example 1
- Input:
- deck = [9,4,12,1,6]
- Output:
- [1,12,4,9,6]
- Explanation:
The arrangement [1, 12, 4, 9, 6] works: the ritual shows 1 and moves 12 down, shows 4 and moves 9 down, shows 6 and moves 12 down, shows 9, and finally shows 12.
Example 2
- Input:
- deck = [30,10,20]
- Output:
- [10,30,20]
- Explanation:
In [10, 30, 20] the ritual shows 10, moves 30 down, shows 20, then shows 30.
Constraints
1 ≤ deck.length ≤ 1000
0 ≤ deck[i] ≤ 109, all values distinct
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)