DSA problem
Reveal Cards In Increasing Order
You are given an integer array deck where deck[i] is the value of the i-th card. You must reorder the cards so that the following procedure reveals every card in strictly increasing order: while the deck is non-empty, take the top card and reveal it, then if at least one card remains, take the next top card and move it to the bottom. Return the deck arrangement that achieves this.
The challenge is to invert the reveal-and-rotate process: given the sorted output, recover the input. A brute-force search would be exponential, but a clean simulation handles the problem in linear time.
The optimal approach uses a deque of positions 0..n-1 and walks the deck in sorted order. For each next smallest card value, take the front index of the deque and assign that card value to the result at that position; then, if the deque is not empty, move the new front index to the back. This exactly reverses the reveal-and-rotate sequence: the front of the deque corresponds to the next slot that will be revealed, and the next slot that will be revealed only after a rotation gets moved to the back so it is processed later.
Because each index enters the deque once and is touched a constant number of times, the algorithm runs in O(n log n) time (dominated by the initial sort) and uses O(n) extra space. It is also a fantastic exercise in thinking with a deque: front pops, back pushes, and how rotation can be modeled by a single pop-then-push.
Examples
deck = [17,13,11,2,3,5,7][2,13,3,11,5,17,7]deck = [1,1000][1,1000]deck = [1,2,3][1,3,2]Constraints
- 1 <= deck.length <= 1000
- 1 <= deck[i] <= 10^6
- All the values of deck are unique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.