Leetcode: Reveal Cards In Increasing Order

Revealing a Deck of Cards in Increasing Order

Description

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:

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, 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.

Revealing a deck of cards in increasing order can be a fascinating problem to solve efficiently. In this article, we'll explore an approach that utilises a specific pattern to reveal the cards in ascending order, considering a given initial ordering.

Approach

By observing the behaviour from the bottom to the top of the sorted deck, I notice a repetitive process: pop the last element, place it at the beginning, and insert the next element from the original deck also at the beginning. This pattern ensures that the revealed deck ends up in increasing order.

Complexity Analysis

• Time Complexity: Sorting the deck initially dominates the time complexity. We use the sort() function, which typically employs an efficient sorting algorithm such as QuickSort. Therefore, the time complexity of sorting is O(n log n), where n is the size of the deck. However, if the deck is already sorted, the time complexity reduces to O(n) as there would be no need for sorting.

• Space Complexity: The space complexity is O(n) since we use an additional vector to store the revealed deck.

Implementation

Here's a C++ implementation of the above approach:

class Solution {
public:
    vector<int> deckRevealedIncreasing(vector<int>& deck) {
        // Sort the deck in descending order
        sort(deck.begin(), deck.end(), greater<int>());

        // Initialize a vector to store the revealed deck
        std::vector<int> revealedDeck;

        // Iterate through the sorted deck to reveal cards in increasing order
        for (const int& card : deck) {
            if (revealedDeck.empty()) {
                revealedDeck.insert(revealedDeck.begin(), card);
            } else {
                // Pop the last card and place it at the beginning
                int lastCard = revealedDeck.back();
                revealedDeck.pop_back();
                revealedDeck.insert(revealedDeck.begin(), lastCard);
                // Insert the next card from the original deck at the beginning
                revealedDeck.insert(revealedDeck.begin(), card);
            }
        }

        return revealedDeck;
    }
};

By following this approach, we can efficiently reveal a deck of cards in increasing order based on a given initial ordering.

Stats