Reveal Cards In Increasing Order

medium queue simulation sorting

Problem

You are given a deck of cards. The reveal procedure is: take the top card and reveal it, then move the next top card to the bottom of the deck; repeat until every card is revealed. Order the deck (return any such arrangement) so that the revealed cards come out in increasing order.

Inputdeck = [17, 13, 11, 2, 3, 5, 7]

Output[2, 13, 3, 11, 5, 17, 7]

Revealing top-to-bottom with the move-to-bottom rule yields 2, 3, 5, 7, 11, 13, 17 in increasing order.

deck (comma-separated)

from collections import deque

def deckRevealedIncreasing(deck):
    deck.sort()
    n = len(deck)
    q = deque(range(n))
    ans = [0] * n
    for x in deck:
        ans[q.popleft()] = x
        if q:
            q.append(q.popleft())
    return ans

function deckRevealedIncreasing(deck) {
  deck.sort((a, b) => a - b);
  const n = deck.length;
  const q = [];
  for (let i = 0; i < n; i++) q.push(i);
  const ans = new Array(n);
  for (const x of deck) {
    ans[q.shift()] = x;
    if (q.length) q.push(q.shift());
  }
  return ans;
}

class Solution {
    public int[] deckRevealedIncreasing(int[] deck) {
        Arrays.sort(deck);
        int n = deck.length;
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) q.add(i);
        int[] ans = new int[n];
        for (int x : deck) {
            ans[q.poll()] = x;
            if (!q.isEmpty()) q.add(q.poll());
        }
        return ans;
    }
}

vector<int> deckRevealedIncreasing(vector<int>& deck) {
    sort(deck.begin(), deck.end());
    int n = deck.size();
    queue<int> q;
    for (int i = 0; i < n; i++) q.push(i);
    vector<int> ans(n);
    for (int x : deck) {
        ans[q.front()] = x; q.pop();
        if (!q.empty()) { q.push(q.front()); q.pop(); }
    }
    return ans;
}

Explanation

Instead of guessing an arrangement, we simulate the reveal process in reverse on the positions. We figure out the exact order in which slots get filled, then drop the sorted values into those slots.

First we sort the deck ascending, because the revealed cards must come out smallest to largest. Then we make a queue of the slot indices 0, 1, …, n-1 — these mimic the deck positions during the reveal.

The reveal rule is "show the top card, then move the next card to the bottom." So for each value x (smallest first), we pop the front index and place x there with ans[q.popleft()] = x. Then, if the queue isn't empty, we move the new front to the back with q.append(q.popleft()) — exactly the move-to-bottom step.

Because we assign the smallest remaining value to whatever slot would be revealed next, the deck we build reveals cards in increasing order by construction.

Example: deck = [17, 13, 11, 2, 3, 5, 7] sorts to [2, 3, 5, 7, 11, 13, 17] and produces [2, 13, 3, 11, 5, 17, 7], which reveals as 2, 3, 5, 7, 11, 13, 17. The sort dominates the cost at O(n log n).

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