Leetcode 950. Reveal Cards In Increasing Order

Problem Explanation:

Given a deck of cards with unique integers, we want to return an ordered deck that, if revealed using the steps described, will show the cards in increasing order.

The steps we'll use are as follows:

1. Take the top card of the deck, reveal it, and discard it.
2. If there are still cards in the deck, move the top card to the bottom, then repeat from step 1.

For example, given the deck [17,13,11,2,3,5,7], we want to reorder it in such a way that following the steps above will result in revealing the cards in order from smallest to largest. One possible solution is [2,13,3,11,5,17,7]. Here, we can see the reveal order would be 2, 3, 5, 7, 11, 13, 17 which is in increasing order.

Approach Explanation:

The problem can be solved using the queue data structure. The algorithm consists of sorting the given deck in decreasing order, then iteratively discarding the top card and moving the next top card to the bottom of the queue. This process simulates the card revealing process described earlier, but in reverse.

Python Solution:

1
2python
3from collections import deque
4from typing import List
5
6class Solution:
7    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
8        # Sorting the deck in reverse order
9        deck.sort(reverse=True)
10        
11        # Initializing the deque with the first element of sorted deck
12        q = deque([deck[0]])
13
14        for card in deck[1:]:
15            # Move last element to front
16            q.appendleft(q.pop())
17            
18            # Adding new card at the front
19            q.appendleft(card)
20            
21        return list(q)

Here we sort the given deck in reverse and add each element one by one in the deque q. For each card, we simulate the process of moving a card to the bottom of the deck before revealing the next card. This is done by popping the rightmost element from the deque and appending it to the front.

Java Solution:

1
2java
3class Solution {
4    public int[] deckRevealedIncreasing(int[] deck) {
5        int n = deck.length;
6        Arrays.sort(deck);
7        Queue<Integer> queue = new LinkedList<>();
8        for (int i = 0; i < n; i++) {
9            queue.add(i);
10        }
11        int[] res = new int[n];
12        for (int i = 0; i < n; i++) {
13            res[queue.poll()] = deck[i];
14            if (!queue.isEmpty()) {
15                queue.add(queue.poll());
16            }
17        }
18        return res;
19    }
20}

The Java solution uses a queue to store the indices in order.

JavaScript Solution:

1
2javascript
3var deckRevealedIncreasing = function(deck) {
4    deck.sort((a, b) => b - a);
5    let q = [];
6    for(let x of deck){
7        q.unshift(x);
8        q.unshift(q.pop())
9    }
10    q.push(q.shift());
11    return q;
12};

C++ Solution:

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

The C++ code utilizes std::deque, which is a double-ended queue to cycle through the cards as described. We are using Reverse Iterators rbegin() and rend() to sort array in reverse order.

C# Solution:

1
2csharp
3public class Solution {
4    public int[] DeckRevealedIncreasing(int[] deck) {
5        int n = deck.Length;
6        Array.Sort(deck);
7        Queue<int> q = new Queue<int>();
8        for (int i = 0; i < n; ++i)
9            q.Enqueue(i);
10        int[] res = new int[n];
11        foreach (int card in deck){
12            res[q.Dequeue()] = card;
13            if (q.Count > 0)
14                q.Enqueue(q.Dequeue());
15         }
16        return res;
17    }
18}

The C# solution again uses a Queue but this time it's storing the indices and takes advantage of the Dequeue method to achieve the result.

In conclusion, we make use of sorting and Queue data structures to approach this problem. By simulating the process of moving cards around in reverse, we're able to determine the initial order of the deck that would result in the cards being revealed in increasing order.## R Solution:

The R code below uses the R's built-in queue class to reorder the given list of cards.

1
2r
3deckRevealedIncreasing <- function(deck) {
4    n <- length(deck)
5    deck <- sort(deck)
6    queue <- 1 : n
7    res <- numeric(n)
8    for (i in 1 : n) {
9        res[queue[1]] <- deck[i]
10        if(i < n) {
11            queue <- c(queue[3 : n], queue[2])
12        }
13    }
14    res
15}

In the R solution above, we are first sorting the deck in increasing order. Then we initialize a sequence from 1 to number of cards, which serves as our queue. We sequentially assign the sorted cards into the res vector according to the indices in the queue. After each assignment, we insert the second element of the queue to the tail end and then remove the first two elements from the queue, which simulates the process of removing the top card and then the next top card to the bottom.

By implementing this solution in a variety of programming languages, we can see that the overall logic remains the same. Sorting in reverse and then using queues allows us to rearrange our deck of cards so that when shown following the given steps, results in a sequence in ascending order. Regardless of the language the solution is implemented in, understanding the core logic of queuing and sorting is crucial in solving this problem.