#950 Reveal Cards In Increasing Order
frequently reported atGoogle
the problem
In plain words
You may order a deck of unique cards any way you like. Then you repeatedly reveal the top card and remove it; if cards remain, you move the next top card to the bottom. Return an ordering that reveals the cards in increasing order.
in deck = [17,13,11,2,3,5,7]
out [2,13,3,11,5,17,7]
Revealing gives 2, 3, 5, 7, 11, 13, 17.
- 1 ≤ n ≤ 1000
- 1 ≤ deck[i] ≤ 10⁶
- All values are unique
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternSimulation
The positions get revealed in a fixed order that doesn't depend on the card values. Simulate the process on positions with a queue, then drop the sorted cards into those positions.
solutions
From brute force to optimal
Replay the reveal process on indices 0..n−1; the k-th revealed index receives the k-th smallest card.
- Sort the cards.
- Queue = 0, 1, …, n−1.
- For each card: poll a position and put the card there; then move the next front position to the rear.
Sorting dominates; the simulation is O(n) queue operations.
The queue of positions and the result array.
class Solution { public int[] deckRevealedIncreasing(int[] deck) { int n = deck.length; int[] sorted = deck.clone(); Arrays.sort(sorted); // cards will be revealed smallest first Queue<Integer> positions = new ArrayDeque<>(); for (int i = 0; i < n; i++) positions.offer(i); // replay the process on positions int[] result = new int[n]; for (int card : sorted) { int pos = positions.poll(); // the next position that gets revealed result[pos] = card; // so the next smallest card goes there if (!positions.isEmpty()) { positions.offer(positions.poll()); // the following top card moves to the bottom } } return result; }}Dry run
Run the process backwards from the largest card: undo "top to bottom" by moving the bottom card to the top, then put the card back on top.
- Sort the cards.
- For cards from largest to smallest: if the deque is non-empty, move its last element to the front; then offerFirst(card).
- Read the deque front → back.
Sorting; the reverse simulation is O(n).
The deque.
class Solution { public int[] deckRevealedIncreasing(int[] deck) { int[] sorted = deck.clone(); Arrays.sort(sorted); Deque<Integer> dq = new ArrayDeque<>(); // front = top of the deck for (int i = sorted.length - 1; i >= 0; i--) { // undo the process, largest card first if (!dq.isEmpty()) dq.offerFirst(dq.pollLast()); // undo "top to bottom": bottom back to top dq.offerFirst(sorted[i]); // undo "reveal": put the card back on top } int[] result = new int[sorted.length]; int i = 0; for (int card : dq) result[i++] = card; return result; }}in the room
How to say it in the interview
talk track
- Simulate a tiny case by hand (4 cards) and notice that the order of revealed positions is always the same.
- Then say: "So I only need to know which position is revealed k-th."
traps
- Rotating after the last card — check that the queue is non-empty first.
what they ask next
Follow-ups
What if you had to reveal in decreasing order?
Same positions; fill them with cards sorted in decreasing order.
before you submit
Edge cases to test
- One card: return it as it is.
- Two cards: the answer is simply sorted order.
- Don't rotate after placing the last card — the queue is already empty.
practise next
Similar problems
- #2073Time Needed to Buy TicketsEasyin Queues
- #225Implement Stack using QueuesEasyin Queues