Reveal Cards in increasing order

Problem Link

950. Reveal Cards In Increasing Order – LeetCode

Problem Statement

You are given an integer array deck. There is a deck of cards represented by this array. You need to reorder the deck so that when the following process is applied, the cards are revealed in increasing order:

Reveal Process:

1. Reveal the top card.

2. If there are still cards, move the next top card to the bottom of the deck.

3. Repeat steps 1–2 until all cards are revealed.

Return the ordering of the deck that would reveal the cards in increasing order.

Examples

Example 1:

Input: deck = [17,13,11,2,3,5,7]
Output: [2,13,3,11,5,17,7]
Explanation:
Deck in increasing order: [2,3,5,7,11,13,17]
Revealing process:
Reveal 2 → move 3 to bottom
Reveal 5 → move 7 to bottom
Reveal 11 → move 13 to bottom
Reveal 17 → done

Example 2:

Input: deck = [1,1000]
Output: [1,1000]

Constraints

• 1 <= deck.length <= 1000

• 1 <= deck[i] <= 10⁶

• All the values of deck are unique

Intuition

The challenge is reconstructing the initial arrangement of cards so that the reveal process yields a sorted sequence.

Instead of simulating the reveal, we reverse engineer it:

• Place the smallest card in the correct position first.

• Simulate the index movement using a queue of positions 0...n-1.

Approach: Simulate Index Movement

1. Sort the deck array (target reveal order).

2. Initialize a queue of indices [0, 1, ..., n-1].

3. For each card in the sorted deck:

   • Pop the front index from the queue → place the current card at this index.

   • If queue is not empty:

     • Pop the next index, and push it to the back (simulating the "move to bottom").

4. Return the result array.

Java Code

class Solution {
    public int[] deckRevealedIncreasing(int[] deck) {
        Arrays.sort(deck);  // Sort the cards to get increasing order
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < deck.length; i++) {
            queue.add(i);  // Fill queue with indices
        }

        int[] res = new int[deck.length];

        for (int card : deck) {
            int idx = queue.poll();  // Place current card at the front index
            res[idx] = card;

            if (!queue.isEmpty()) {
                queue.add(queue.poll());  // Move next index to the back
            }
        }

        return res;
    }
}

Time and Space Complexity

Dry Run

Input:

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

Sorted deck:

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

Queue (indices):

[0,1,2,3,4,5,6]

Process:

Result: [2,13,3,11,5,17,7]

Conclusion

This problem is a creative use of reverse simulation, where we:

• Track positions, not values.

• Use a queue to simulate cyclic index movement.

• Combine sorting with custom index placement.

It reinforces understanding of simulation, queues, and reverse process modeling.