# Reveal Cards In Increasing Order **Difficulty:** MEDIUM [External](https://leetcode.com/problems/reveal-cards-in-increasing-order) Canonical: https://scaleengineer.com/dsa/problems/reveal-cards-in-increasing-order **Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting) **Data structures:** Array, Queue --- ## Problem 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 ## Brute-Force with Permutations 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. **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. **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). ### Explanation 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. ### 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`. ## Reverse Simulation with an ArrayList 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. **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. **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. ### Explanation 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: 1. Sort the input `deck` in ascending order. This gives us the cards in the order they are revealed. 2. Create an empty `ArrayList` to build our result deck. 3. Iterate through the sorted `deck` in reverse order (from largest to smallest card). 4. 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)`. 5. After processing all cards, the list contains the required deck ordering. Convert it to an array and return. ```java import java.util.Arrays; import java.util.ArrayList; import java.util.List; class Solution { public int[] deckRevealedIncreasing(int[] deck) { int n = deck.length; Arrays.sort(deck); List resultList = new ArrayList<>(); for (int i = n - 1; i >= 0; i--) { if (!resultList.isEmpty()) { // Move the last element to the front resultList.add(0, resultList.remove(resultList.size() - 1)); } // Add the new card to the front resultList.add(0, deck[i]); } int[] finalDeck = new int[n]; for (int i = 0; i < n; i++) { finalDeck[i] = resultList.get(i); } return finalDeck; } } ``` ### 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. ## Optimal Reverse Simulation with a Deque 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. **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). **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. ### Explanation 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. 1. Sort the input `deck` in ascending order. 2. Create an empty `Deque` (an `ArrayDeque` is a good choice in Java). 3. Iterate through the sorted `deck` in reverse order. 4. 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. 5. 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. ```java import java.util.Arrays; import java.util.Deque; import java.util.ArrayDeque; class Solution { public int[] deckRevealedIncreasing(int[] deck) { int n = deck.length; Arrays.sort(deck); Deque deque = new ArrayDeque<>(); for (int i = n - 1; i >= 0; i--) { if (!deque.isEmpty()) { deque.addFirst(deque.removeLast()); } deque.addFirst(deck[i]); } int[] result = new int[n]; int i = 0; for (int card : deque) { result[i++] = card; } return result; } } ``` ### 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. # Solutions ### Java ```java class Solution { public int[] deckRevealedIncreasing(int[] deck) { Deque 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; } } ``` ### CPP ```cpp class Solution { public: vector deckRevealedIncreasing(vector &deck) { sort(deck.rbegin(), deck.rend()); deque q; for (int v : deck) { if (!q.empty()) { q.push_front(q.back()); q.pop_back(); } q.push_front(v); } return vector(q.begin(), q.end()); } }; ``` ### Python ```python class Solution: 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) ```