Code Implementation

from collections import deque

class Solution:
    def deckRevealedIncreasing(self, deck):
        deck.sort()
        n = len(deck)
        index_queue = deque(range(n))
        result = [0] * n
        
        for card in deck:
            idx = index_queue.popleft()
            result[idx] = card
            if index_queue:
                index_queue.append(index_queue.popleft())
        return result
      

#include <vector>
#include <deque>
#include <algorithm>

class Solution {
public:
    std::vector<int> deckRevealedIncreasing(std::vector<int>& deck) {
        std::sort(deck.begin(), deck.end());
        int n = deck.size();
        std::deque<int> index_queue;
        for (int i = 0; i < n; ++i)
            index_queue.push_back(i);
        std::vector<int> result(n);
        for (int card : deck) {
            int idx = index_queue.front();
            index_queue.pop_front();
            result[idx] = card;
            if (!index_queue.empty()) {
                index_queue.push_back(index_queue.front());
                index_queue.pop_front();
            }
        }
        return result;
    }
};
      

import java.util.*;

class Solution {
    public int[] deckRevealedIncreasing(int[] deck) {
        Arrays.sort(deck);
        int n = deck.length;
        Deque<Integer> indexQueue = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) indexQueue.add(i);
        int[] result = new int[n];
        for (int card : deck) {
            int idx = indexQueue.pollFirst();
            result[idx] = card;
            if (!indexQueue.isEmpty()) {
                indexQueue.add(indexQueue.pollFirst());
            }
        }
        return result;
    }
}
      

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

Problem Description

You are given an array deck representing a deck of unique integer cards. You are to arrange the deck so that when you reveal cards in the following process, the revealed cards are in increasing order:

• Take the top card of the deck, reveal it, and remove it from the deck.
• If there are still cards in the deck, move the next top card to the bottom of the deck.
• Repeat until all cards are revealed.

You must return the initial ordering of deck that will result in an increasing sequence of revealed cards. Each card must be used exactly once, and there is only one valid solution for each input deck.

Thought Process

At first glance, the problem seems to ask for simulating the reveal process and finding an arrangement that works. A brute-force approach would try all permutations, simulate the reveal, and check if it results in an increasing sequence. However, this is computationally infeasible for larger decks due to factorial growth.

By analyzing the process, we realize the challenge is to "reverse engineer" the reveal operation: given a sorted list of cards, how should we place them so that the reveal order is increasing? This leads us to consider working backwards, simulating the process in reverse, or using a data structure to track indices as we assign cards to their correct positions.

Solution Approach

• Step 1: Sort the deck. Since the final revealed sequence must be increasing, we sort deck in ascending order.
• Step 2: Prepare a queue of indices. Use a queue (or deque) to keep track of the positions in the result array where the next smallest card should go.
• Step 3: Assign cards to positions. For each card in the sorted deck:
  • Pop the front index from the queue and place the card at that position in the result array.
  • If there are still indices left, move the next index from the front to the back of the queue (simulating moving the top card to the bottom in the reveal process).
• Step 4: Return the result. The result array now contains the initial arrangement that will reveal cards in increasing order.

This approach uses a queue to mimic the reveal process in reverse, efficiently determining where each card should be placed.

Example Walkthrough

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

1. Sort the deck: [2, 3, 5, 7, 11, 13, 17].
2. Initialize result array: [_, _, _, _, _, _, _].
3. Initialize index queue: [0, 1, 2, 3, 4, 5, 6].
4. For each card:
   • Place 2 at index 0 → result: [2, _, _, _, _, _, _], queue: [1,2,3,4,5,6]
   • Move 1 to back → queue: [2,3,4,5,6,1]
   • Place 3 at index 2 → result: [2, _, 3, _, _, _, _], queue: [3,4,5,6,1]
   • Move 3 to back → queue: [4,5,6,1,3]
   • Place 5 at index 4 → result: [2, _, 3, _, 5, _, _], queue: [5,6,1,3]
   • Move 5 to back → queue: [6,1,3,5]
   • Place 7 at index 6 → result: [2, _, 3, _, 5, _, 7], queue: [1,3,5]
   • Move 1 to back → queue: [3,5,1]
   • Place 11 at index 3 → result: [2, _, 3, 11, 5, _, 7], queue: [5,1]
   • Move 5 to back → queue: [1,5]
   • Place 13 at index 1 → result: [2, 13, 3, 11, 5, _, 7], queue: [5]
   • Move 5 to back → queue: [5]
   • Place 17 at index 5 → result: [2, 13, 3, 11, 5, 17, 7]
5. The final arrangement is [2, 13, 3, 11, 5, 17, 7]. Revealing cards using the process will give [2, 3, 5, 7, 11, 13, 17].

Time and Space Complexity

• Brute-force approach: Trying all permutations and simulating the process for each is O(n! * n), which is infeasible for large n.
• Optimized approach:
  • Sorting the deck: O(n \log n)
  • Queue operations for n cards: each operation is O(1), so total O(n)
  • Total time complexity: O(n \log n)
  • Space complexity: O(n) for the result array and queue

Summary

This problem requires you to reconstruct the initial deck order so that a specific card-revealing process results in an increasing sequence. The key insight is to simulate the process in reverse using a queue of indices, efficiently assigning each sorted card to its correct place. This leads to an elegant and efficient solution that avoids brute-force enumeration and leverages simple data structures.