Scale Engineer

Reveal Cards In Increasing Order

Med
#0904Time: O(N! * N). There are N! permutations to check. For each permutation, the simulation involves N reveal steps. If a queue is used for the simulation, each step (poll, add) is O(1), making the simulation O(N). Thus, the total time complexity is O(N! * N).Space: O(N). We need space to store the current permutation being tested and the queue for the simulation, both of which are of size N.
Algorithms
Sorting
Data structures
ArrayQueue

Prompt

You are given an integer array deck. There is a deck of cards where every card has a unique integer. The integer on the ith card is deck[i].

You can order the deck in any order you want. Initially, all the cards start face down (unrevealed) in one deck.

You will do the following steps repeatedly until all cards are revealed:

  1. Take the top card of the deck, reveal it, and take it out of the deck.
  2. If there are still cards in the deck then put the next top card of the deck at the bottom of the deck.
  3. If there are still unrevealed cards, go back to step 1. Otherwise, stop.

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

Note that the first entry in the answer is considered to be the top of the deck.

 

Example 1:

Input: deck = [17,13,11,2,3,5,7]
Output: [2,13,3,11,5,17,7]
Explanation: 
We get the deck in the order [17,13,11,2,3,5,7] (this order does not matter), and reorder it.
After reordering, the deck starts as [2,13,3,11,5,17,7], where 2 is the top of the deck.
We reveal 2, and move 13 to the bottom.  The deck is now [3,11,5,17,7,13].
We reveal 3, and move 11 to the bottom.  The deck is now [5,17,7,13,11].
We reveal 5, and move 17 to the bottom.  The deck is now [7,13,11,17].
We reveal 7, and move 13 to the bottom.  The deck is now [11,17,13].
We reveal 11, and move 17 to the bottom.  The deck is now [13,17].
We reveal 13, and move 17 to the bottom.  The deck is now [17].
We reveal 17.
Since all the cards revealed are in increasing order, the answer is correct.

Example 2:

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

 

Constraints:

  • 1 <= deck.length <= 1000
  • 1 <= deck[i] <= 106
  • All the values of deck are unique.

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward but highly inefficient approach is to try every possible arrangement of the deck. We can generate all permutations of the input cards and, for each permutation, simulate the revealing process to see if it produces cards in increasing order.

Algorithm

  • Generate all permutations of the input deck.
  • For each permutation p:
    • Create a queue q from p.
    • Create an empty list revealed.
    • While q is not empty:
      • Reveal a card: revealed.add(q.poll()).
      • If q is not empty, move the next card to the bottom: q.add(q.poll()).
    • Check if revealed is sorted in increasing order.
    • If it is, return p.

Walkthrough

The algorithm works as follows:

  1. Generate all unique permutations of the deck array. There are N! such permutations, where N is the number of cards.
  2. For each permutation, treat it as the initial deck and simulate the card revealing process:
    • Use a queue to represent the deck.
    • Repeatedly take the top card (reveal it) and if the deck is not empty, move the next top card to the bottom.
    • Store the revealed cards in a list.
  3. After the simulation for a permutation is complete, check if the list of revealed cards is sorted in ascending order.
  4. If it is, we have found the correct ordering, so we can return it. If we check all permutations and none work (which is impossible given the problem statement), we would have no solution.

This method is guaranteed to find the solution but is computationally infeasible for the given constraints.

Complexity

Time

O(N! * N). There are N! permutations to check. For each permutation, the simulation involves N reveal steps. If a queue is used for the simulation, each step (poll, add) is O(1), making the simulation O(N). Thus, the total time complexity is O(N! * N).

Space

O(N). We need space to store the current permutation being tested and the queue for the simulation, both of which are of size N.

Trade-offs

Pros

  • Conceptually simple to understand if a permutation generation utility is available.

Cons

  • Extremely inefficient due to the factorial time complexity.

  • Only feasible for very small inputs (e.g., N < 10), making it impractical for the problem's constraints (N <= 1000).

Solutions

class Solution {public  int[] deckRevealedIncreasing(int[] deck) {    Deque<Integer> q = new ArrayDeque<>();    Arrays.sort(deck);    int n = deck.length;    for (int i = n - 1; i >= 0; --i) {      if (!q.isEmpty()) {        q.offerFirst(q.pollLast());      }      q.offerFirst(deck[i]);    }    int[] ans = new int[n];    for (int i = n - 1; i >= 0; --i) {      ans[i] = q.pollLast();    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem