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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reveal Cards In Increasing Order

Number: 987

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Bloomberg

Problem Description

Given a deck of unique integer cards, we wish to order the deck so that when we reveal the top card and then move the next card to the bottom, repeating these steps, the revealed cards are in increasing order. The first card revealed should be the smallest, the next the second smallest, and so on.

Key Insights

  • The final revealed sequence must be the sorted order of the deck.
  • Instead of simulating the process forward, we simulate it in reverse.
  • Use a queue (or deque) to efficiently perform operations on both ends.
  • Start from the largest card and reverse the process to reconstruct the initial order.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the deck. Space Complexity: O(n) for storing the recreated ordering and using a deque.

Solution

To solve the problem, sort the deck in ascending order. Then, simulate the revealing process in reverse: Initialize an empty deque. Iterate over the sorted deck in descending order. For each card, if the deque is non-empty, remove the last element and insert it at the front to simulate reversing the "move next card to bottom" step. Then, insert the current card at the front. The resulting deque represents the required deck order that, when processed by the given steps, reveals the cards in increasing order.

Code Solutions

# Python solution using collections.deque for efficient O(1) pop and append operations on both ends.

from collections import deque

def deckRevealedIncreasing(deck):
    # Sort the deck in ascending order.
    sorted_deck = sorted(deck)
    # Initialize an empty deque to simulate the reverse process.
    dq = deque()
    
    # Process each card from the largest to smallest
    for card in reversed(sorted_deck):
        # If the deque is not empty, simulate moving the last element to the front.
        if dq:
            dq.appendleft(dq.pop())
        # Place the current card at the front of the deque.
        dq.appendleft(card)
    
    # Convert deque back to list which is the required order.
    return list(dq)

# Example usage
deck = [17, 13, 11, 2, 3, 5, 7]
print(deckRevealedIncreasing(deck))  # Expected output: [2, 13, 3, 11, 5, 17, 7]
← Back to All Questions