Domain 2MediumMEDIUM

Reveal Cards In Increasing Order

Find a permutation of cards such that simulating the reveal process yields sorted order by mapping indices using a deque.

Domain: medium•Updated: 2026-09-04
#Reverse Simulation#Deque#O(N log N)#O(N)

Problem Breakdown

We are given an array A representing unique card values. The goal is to reorder this deck so that when we simulate a specific “reveal and move” process, the cards appear in ascending order of their revealed sequence.

Inputs: A list deck containing unique integers (1≤N≤10001 \le N \le 1000). Outputs: An integer list representing a valid permutation where simulation yields sorted output. Constraints & Edge Cases:

  • Length: NN up to 1000, allowing for efficient solutions beyond brute force.
  • Values: Unique integers (A[i]≠A[j]A[i] \neq A[j]). This simplifies mapping as each value maps uniquely to a reveal step.
  • Empty Input: Constraints specify length ≥1\ge 1, but robust code handles N=0N=0 naturally (returns empty list).

Intuition

Simulating the process forward with unknown card values is impossible because we don’t know which position corresponds to which rank yet. However, the positions where cards are revealed follow a deterministic pattern based on indices alone.

Key Insight: Instead of moving physical cards, simulate the movement using empty slots (indices). If an index gets “revealed” during our simulation, it is reserved for the smallest available card value from our sorted input list. By filling these revealed positions sequentially with values from sorted(deck), we construct the required initial permutation in reverse order relative to the reveal process.

Approach

  1. Sort Input: Sort deck ascendingly. This gives us a queue of card values that must be revealed first, second, etc., regardless of their original positions.
  2. Initialize Queue of Indices: Create a deque containing indices [0, 1, ..., N-1]. These represent the physical slots in our result array waiting to be filled or moved.
  3. Simulate Process on Indices: Iterate through each card value val from the sorted list:
    • Pop an index from the front (idx). This slot is “revealed” by the process, so we assign res[idx] = val.
    • If there are remaining indices in the queue (representing cards still face down), pop one and push it back. This simulates moving a card to the bottom of the deck without revealing it yet.
  4. Return Result: After assigning all values, return res.

Complexity Analysis

  • Time Complexity: O(Nlog⁡N)O(N \log N). Sorting takes O(Nlog⁡N)O(N \log N). The simulation loop runs exactly once per card (each index is popped twice max: once for reveal, once for move). Deque operations are amortized O(1)O(1), so the loop is O(N)O(N). Total time dominated by sorting.
  • Space Complexity: O(N)O(N). We store a result array of size NN and an auxiliary deque of size at most NN.

Solution

from collections import deque

def deckRevealedIncreasing(deck: list[int]) -> list[int]:
    # Sort the input to know which value corresponds to each reveal step.
    sorted_deck = sorted(deck)
    
    n = len(sorted_deck)
    if not n:
        return []
        
    # Initialize a queue with indices representing positions in our result array.
    index_queue = deque(range(n))
    
    # Result list to store the final ordering of cards.
    res = [0] * n
    
    # Simulate the process using indices, assigning sorted values as we go.
    for val in sorted_deck:
        # Pop front: This position is "revealed" (we place a card here).
        idx = index_queue.popleft()
        
        # Assign current smallest value to this revealed slot.
        res[idx] = val
        
        # If there are remaining indices, move the next one to bottom 
        # by popping front and pushing back. This simulates moving a card down.
        if index_queue:
            idx_to_move = index_queue.popleft()
            index_queue.append(idx_to_move)
            
    return res

# Example usage matching problem description logic (not required for submission but good for verification):
if __name__ == "__main__":
    print(deckRevealedIncreasing([17, 13, 11, 2, 3, 5, 7])) 

Edge Cases Handled

  • Single Element (N=1N=1): The queue starts with [0]. Loop runs once. popleft gets 0, assigns value. Queue is empty after move check (condition fails). Returns correct single-element array.
  • Sorted Input: If input is already sorted, the logic still holds because we re-simulate positions regardless of initial order; sorting ensures values are assigned to reveal-order slots correctly.
  • Large Values (10610^6): Python handles arbitrary precision integers automatically; no overflow issues occur with standard integer types in this context.