We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Reveal Cards In Increasing Order

Difficulty: Medium

Problem 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 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:

  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.

Key Insights

  • The order of revealing cards must maintain a sequence that allows for the lowest card to be revealed first, followed by the next lowest, and so forth.
  • The problem can be visualized as a queue where we repeatedly manipulate the order of the elements based on their revealed state.
  • Sorting the deck initially provides a clear way to determine the order of revealed cards.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the deck, where n is the number of cards.
Space Complexity: O(n) for storing the order of cards in a queue.

Solution

To solve the problem, we can use a queue to simulate the process of revealing cards. The algorithm follows these steps:

  1. Sort the deck array to determine the order of the cards to reveal.
  2. Use a deque (double-ended queue) to maintain the order of cards.
  3. For each card in the sorted deck, reveal the card at the front of the queue and then place the next card from the front to the back of the queue until all cards are revealed.

This approach ensures that the revealed cards are in increasing order.

Code Solutions

from collections import deque

def deckRevealedIncreasing(deck):
    # Sort the deck to get the revealing order
    deck.sort()
    
    # Create a deque for maintaining the order of cards
    queue = deque()
    
    # Add the last card to the queue first
    for card in reversed(deck):
        if queue:
            # Move the top card to the bottom of the queue
            queue.appendleft(queue.pop())
        # Add the revealed card to the front of the queue
        queue.appendleft(card)
    
    return list(queue)
← Back to All Questions