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

Array Queue

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 i^th 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:

Take the top card of the deck, reveal it, and take it out of the deck.
If there are still cards in the deck then put the next top card of the deck at the bottom of the deck.
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] <= 10⁶
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:

Generate all unique permutations of the deck array. There are N! such permutations, where N is the number of cards.
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.
After the simulation for a permutation is complete, check if the list of revealed cards is sorted in ascending order.
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).

A more practical approach is to work backward. We know the cards must be revealed in increasing order. So, if we sort the deck, we have the exact sequence of revealed cards. We can then reverse the revealing process to reconstruct the initial deck configuration. Using a standard ArrayList for this reconstruction is intuitive but results in a quadratic time complexity due to costly insertions at the beginning of the list.

Algorithm

Sort the deck array in ascending order.
Create an empty ArrayList named result.
Iterate through the sorted deck from the last element (n-1) down to the first (0).
For each card deck[i]:
- If result is not empty, remove the last element from result and insert it at index 0.
- Insert deck[i] at index 0 of result.
Convert the result list into an array and return it.

Walkthrough

The key insight is to reverse the operations. The forward process is: 1. Reveal top card. 2. Move next top card to bottom. The reverse process is: 1. Take the card that was moved to the bottom and place it on top. 2. Add the previously revealed card to the top.

The algorithm is as follows:

Sort the input deck in ascending order. This gives us the cards in the order they are revealed.
Create an empty ArrayList to build our result deck.
Iterate through the sorted deck in reverse order (from largest to smallest card).
For each card c:
- If the result list is not empty, undo the 'move to bottom' step. This means taking the last card in our list and moving it to the front. With an ArrayList, this is result.add(0, result.remove(result.size() - 1)).
- Undo the 'reveal' step. This means adding the card c to the front of the list: result.add(0, c).
After processing all cards, the list contains the required deck ordering. Convert it to an array and return.

1import java.util.Arrays;2import java.util.ArrayList;3import java.util.List;4 5class Solution {6    public int[] deckRevealedIncreasing(int[] deck) {7        int n = deck.length;8        Arrays.sort(deck);9        List<Integer> resultList = new ArrayList<>();10        for (int i = n - 1; i >= 0; i--) {11            if (!resultList.isEmpty()) {12                // Move the last element to the front13                resultList.add(0, resultList.remove(resultList.size() - 1));14            }15            // Add the new card to the front16            resultList.add(0, deck[i]);17        }18        int[] finalDeck = new int[n];19        for (int i = 0; i < n; i++) {20            finalDeck[i] = resultList.get(i);21        }22        return finalDeck;23    }24}

Complexity

Time

O(N^2). Sorting the deck takes O(N log N). The main loop runs N times. Inside the loop, inserting an element at the beginning of an `ArrayList` (`add(0, ...)`), takes O(k) time, where k is the current size of the list. This leads to a total simulation time of approximately 1 + 2 + ... + (N-1), which is O(N^2). The overall complexity is dominated by this quadratic factor.

Space

O(N). An `ArrayList` of size N is used to store the result.

Trade-offs

Pros

Much more efficient than brute-force.
The logic of reversing the process is sound and easier to reason about.

Cons

The use of an ArrayList for operations at the front of the list is inefficient, leading to a quadratic time complexity which can be slow for larger N.

This approach builds upon the reverse simulation logic but employs a more suitable data structure, a Double-Ended Queue (Deque), to achieve optimal performance. By using a Deque, the operations of adding to the front and moving an element from the back to the front can be done in constant time, reducing the overall time complexity to be dominated by the initial sort.

Algorithm

Sort the deck array in ascending order.
Create an empty Deque (e.g., ArrayDeque).
Iterate through the sorted deck from the last element (n-1) down to the first (0).
For each card deck[i]:
- If the deque is not empty, remove the last element and add it to the front of the deque.
- Add deck[i] to the front of the deque.
Convert the final deque into an array and return it.

Walkthrough

The algorithm is identical in logic to the previous approach but differs in implementation. We still sort the deck and reconstruct the result by iterating from the largest card to the smallest.

Sort the input deck in ascending order.
Create an empty Deque (an ArrayDeque is a good choice in Java).
Iterate through the sorted deck in reverse order.
For each card c:
- If the deque is not empty, perform the reverse of 'move to bottom'. This involves taking the last element and putting it at the front: deque.addFirst(deque.removeLast()). This is an O(1) operation for a deque.
- Then, perform the reverse of 'reveal'. This involves adding the current card c to the front: deque.addFirst(c). This is also an O(1) operation.
After the loop finishes, the deque holds the cards in the correct initial order. We can then convert it to an array and return.

This use of a Deque turns the O(N^2) simulation into an O(N) one, making the entire algorithm much faster.

1import java.util.Arrays;2import java.util.Deque;3import java.util.ArrayDeque;4 5class Solution {6    public int[] deckRevealedIncreasing(int[] deck) {7        int n = deck.length;8        Arrays.sort(deck);9        Deque<Integer> deque = new ArrayDeque<>();10        for (int i = n - 1; i >= 0; i--) {11            if (!deque.isEmpty()) {12                deque.addFirst(deque.removeLast());13            }14            deque.addFirst(deck[i]);15        }16        int[] result = new int[n];17        int i = 0;18        for (int card : deque) {19            result[i++] = card;20        }21        return result;22    }23}

Complexity

Time

O(N log N). Sorting takes O(N log N). The simulation loop runs N times, and each operation on the `Deque` (`addFirst`, `removeLast`) takes O(1) constant time. Therefore, the simulation part takes O(N) time. The overall time complexity is dominated by the sorting step.

Space

O(N). A `Deque` of size N is used to store the result. If the sorting is done in-place, this is the main space overhead. Otherwise, space for the sorted copy is also O(N).

Trade-offs

Pros

Optimal time complexity.
Elegant and efficient solution.
Directly implements the reverse logic using the right data structure.

Cons

Requires familiarity with the Deque data structure and its constant-time operations at both ends.

Solutions

Solution

1class Solution {2public3  int[] deckRevealedIncreasing(int[] deck) {4    Deque<Integer> q = new ArrayDeque<>();5    Arrays.sort(deck);6    int n = deck.length;7    for (int i = n - 1; i >= 0; --i) {8      if (!q.isEmpty()) {9        q.offerFirst(q.pollLast());10      }11      q.offerFirst(deck[i]);12    }13    int[] ans = new int[n];14    for (int i = n - 1; i >= 0; --i) {15      ans[i] = q.pollLast();16    }17    return ans;18  }19}

1class Solution {2public:3  vector<int> deckRevealedIncreasing(vector<int> &deck) {4    sort(deck.rbegin(), deck.rend());5    deque<int> q;6    for (int v : deck) {7      if (!q.empty()) {8        q.push_front(q.back());9        q.pop_back();10      }11      q.push_front(v);12    }13    return vector<int>(q.begin(), q.end());14  }15};

1class Solution:2    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]: q = deque() for v in sorted(deck, reverse=True): if q: q . appendleft(q . pop()) q . appendleft(v) return list(q)

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 problem

Solution

1class Solution {2public3  int[] deckRevealedIncreasing(int[] deck) {4    Deque<Integer> q = new ArrayDeque<>();5    Arrays.sort(deck);6    int n = deck.length;7    for (int i = n - 1; i >= 0; --i) {8      if (!q.isEmpty()) {9        q.offerFirst(q.pollLast());10      }11      q.offerFirst(deck[i]);12    }13    int[] ans = new int[n];14    for (int i = n - 1; i >= 0; --i) {15      ans[i] = q.pollLast();16    }17    return ans;18  }19}

1class Solution {2public:3  vector<int> deckRevealedIncreasing(vector<int> &deck) {4    sort(deck.rbegin(), deck.rend());5    deque<int> q;6    for (int v : deck) {7      if (!q.empty()) {8        q.push_front(q.back());9        q.pop_back();10      }11      q.push_front(v);12    }13    return vector<int>(q.begin(), q.end());14  }15};

1class Solution:2    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]: q = deque() for v in sorted(deck, reverse=True): if q: q . appendleft(q . pop()) q . appendleft(v) return list(q)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.