Reveal Cards in Increasing Order

1. Define the problem

Reveal Cards in Increasing Order

You have a deck of cards with different numbers. You will reveal them with a repeating routine: take the top card and show it, then move the new top card to the bottom, and carry on until the deck is empty. Return an ordering of the deck so that the revealed cards come out in increasing order . Instead of guessing the order, run the routine on the positions rather than the cards. Put the position numbers 0, 1, 2 and so on into a queue, then deal the sorted cards out smallest first: take a position off the front, write the next smallest card there, and move the following position to the back. The queue replays exactly the reveal routine, so wherever it says to write a card is where that card must sit in the answer.

Constraints

1 ≤ deck.length ≤ 1000
1 ≤ deck_i ≤ 10⁶
Card values may repeat, and the routine still works
Return the deck ordering, not the revealed order

Example

Inputdeck = [2, 3, 5, 7]

Output[2, 5, 3, 7]

Explanation Reveal 2, move 5 to the bottom; reveal 3, move 7 to the bottom; reveal 5, move 7 to the bottom; reveal 7. That gives 2, 3, 5, 7 in increasing order.

2. Know the words first

In plain terms

Simulation: Running the rules of a problem step by step instead of finding a formula. Here you simulate the reveal routine on positions to learn where each card belongs.
Position queue: A queue holding the slot numbers of the answer, in the order the routine will visit them. Its front is the slot the next card goes into.
Move to the bottom: Taking the front of the queue and putting it straight on the back, which is the same as sending the top card to the bottom of the deck.

3. Visualize the solution

One row of cells is the queue of answer positions, front on the left

q0 · front0

q11

q22

q3 · back3

Statusinit

Sorted cards are 2, 3, 5, 7. The position queue starts as 0, 1, 2, 3.

What happens in this step

deck = [2, 3, 5, 7], sorted = [2, 3, 5, 7]
positions queue = [0, 1, 2, 3]
answer = [_, _, _, _]

Each cell holds a position in the answer, not a card value.
The front position is where the smallest remaining card will go.

Step 1 of 8

Steps to visualize

Sort the cards first, so you always know which card to place next.
The row holds the positions of the answer that have not been filled yet.
Take the front position, write the next smallest card there.
Then move the new front position to the back, which mirrors moving a card to the bottom of the deck.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One row of cells is the queue of answer positions, front on the left

q0 · front0

q11

q22

q3 · back3

Statusinit

Sorted cards are 2, 3, 5, 7. The position queue starts as 0, 1, 2, 3.

What happens in this step

deck = [2, 3, 5, 7], sorted = [2, 3, 5, 7]
positions queue = [0, 1, 2, 3]
answer = [_, _, _, _]

Each cell holds a position in the answer, not a card value.
The front position is where the smallest remaining card will go.

Step 1 of 8

5. Solution

Solution

solution.tsTypeScript

function deckRevealedIncreasing(deck) {
  const sorted = deck.slice().sort((a, b) => a - b);
  const slots = [];

  for (let i = 0; i < deck.length; i++) {
    slots.push(i);
  }

  const result = new Array(deck.length).fill(0);

  for (let i = 0; i < sorted.length; i++) {
    result[slots.shift()] = sorted[i];

    if (slots.length > 0) {
      slots.push(slots.shift());
    }
  }

  return result;
}

Time: O(n log n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`deck = [2, 3, 5, 7]`	`[2, 5, 3, 7]`	example from the docstring
`deck = [17, 13, 11, 2, 3, 5, 7]`	`[2, 13, 3, 11, 5, 17, 7]`	a larger unsorted deck
`deck = [1]`	`[1]`	smallest possible deck
`deck = [1, 1000]`	`[1, 1000]`	two cards need no reordering
`deck = [6, 5, 4, 3, 2, 1]`	`[1, 4, 2, 6, 3, 5]`	an input in fully descending order
`deck = [1, 1, 1]`	`[1, 1, 1]`	repeated values, where every ordering already works

Reveal Cards in Increasing Order