Reveal Cards In Increasing Order
Problem
deck of cards with distinct values and may arrange it in
any order. Cards are then revealed by repeating: take the top card and reveal it; if cards
remain, move the new top card to the bottom. Return an ordering (top first) that makes the
revealed values come out in increasing order.deck=[17,13,11,2,3,5,7]Output[2,13,3,11,5,17,7]deck=[1,1000]Output[1,1000]1 ≤ n ≤ 1000 · 1 ≤ deck[i] ≤ 106 · all values distinct
Try it yourself
class Solution {
public int[] deckRevealedIncreasing(int[] deck) {
}
}
0..n-1 with a queue, and hand the sorted values to the
positions in the order they get revealed.Instinct Arrival order matters, or you need the max/min of a moving window - reach for a FIFO queue, or a deque of indices kept in sorted order.
Memory hack Old ones leave by the front door, weak ones get bounced out the back - so whoever stands at the front is always the champion.
Open the Queue & Monotonic Deque guide →Approaches
Brute ForceUndo the Process with a List
O(n²)Space O(n)Build the deck backwards, from the largest card to the smallest. Undoing one
round means: move the bottom card back to the top, then put the card that was just
revealed on top. With an ArrayList, inserting at the front shifts every
element.
public int[] deckRevealedIncreasing(int[] deck) { int[] sorted = deck.clone(); Arrays.sort(sorted); List<Integer> pile = new ArrayList<>(); // index 0 = top for (int i = sorted.length - 1; i >= 0; i--) { if (!pile.isEmpty()) pile.add(0, pile.remove(pile.size() - 1)); // undo "top to bottom" pile.add(0, sorted[i]); // undo "reveal top" } int[] result = new int[deck.length]; for (int i = 0; i < result.length; i++) result[i] = pile.get(i); return result; }
Correct and intuitive, but each front insertion is O(n).
OptimalIndex Queue Simulation
O(n log n)Space O(n)Put positions 0..n-1 in a queue and play the game on them: the
polled position is revealed next, then the following position goes to the back.
The i-th revealed position must hold the i-th smallest card.
Sorting dominates; the simulation itself is linear.
public int[] deckRevealedIncreasing(int[] deck) { int n = deck.length; int[] sorted = deck.clone(); Arrays.sort(sorted); Deque<Integer> positions = new ArrayDeque<>(); for (int i = 0; i < n; i++) positions.offerLast(i); int[] result = new int[n]; for (int card : sorted) { result[positions.pollFirst()] = card; // this slot is revealed now if (!positions.isEmpty()) positions.offerLast(positions.pollFirst()); // to bottom } return result; }
Dry rundeck=[17,13,11,2,3,5,7]
- 22p······q=[2,3,4,5,6,1]
- 32·3p····q=[4,5,6,1,3]
- 52·3·5p··q=[6,1,3,5]
- 72·3·5·7pq=[3,5,1]
- 11,132133115·7slots 3 then 1
- 17213311517p7done ✔
Sort plus a linear queue walk — clean, fast and the expected answer.
ArrayDeque instead of a list also gives
O(n log n) — mention it as an equally valid alternative.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Undo the Process with a List | O(n²) | O(n) |
| Optimal | Index Queue Simulation | O(n log n) | O(n) |
- Forgetting to sort first — the values must be handed out smallest first.
- Moving a card to the bottom after the last reveal (empty queue).
- Placing values by reveal step instead of by the polled position.
- Notice that only positions matter, so simulate on indices, not values.
- Trace the 7-card example to show which slot each sorted card lands in.
- Mention that undoing the process backwards is an equivalent way to think about it.