⚡Flashcard Drill➔
NeetCode #809LC-950MediumGreedy
← Back to All Problems

#809 · #950 · Reveal Cards In Increasing Order(按递增顺序显示卡牌)

📌 Problem Statement & Constraints

You have a deck of distinct integers. The reveal process is: take the top card, reveal it, then (if cards remain) move the new top card to the bottom and repeat. Given the deck, return an ordering of the cards so that the revealed order is increasing. Constraints: 1 <= deck.length <= 1000, all values are distinct.

💡 Core Algorithmic Approaches

  1. Work backwards: instead of deciding which card is revealed at each step, decide which position is revealed at each step.
  2. Simulate the reveal process over positions 0..n-1 using a deque of indices: pop the front as the revealed position, then move the new front to the back.
  3. Sort the deck ascending and assign the sorted values to the positions in the order they are revealed.
  4. The result is the initial ordering that produces the sorted reveal sequence.

💻 Benchmark Python3 Implementation

class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        from collections import deque
        deck.sort()
        n = len(deck)
        idx = deque(range(n))          # positions still to be filled, in reveal order
        res = [0] * n
        for card in deck:
            res[idx.popleft()] = card  # this position is revealed now
            if idx:
                idx.append(idx.popleft())   # the next top card moves to the bottom
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): sorting dominates; the deque simulation is O(n).
💾 Space Complexity
O(n): the deque of indices and the result array.

⚠️ Interview Pitfalls & Follow-ups

  • Simulating forwards on the deck values: the process operates on positions, and only after fixing the position order can the sorted values be assigned.
  • Forgetting the if idx guard: after the last card there is nothing to move, and an unguarded rotate would corrupt the deque.
  • Assigning the largest card first: the sorted order must be assigned in reveal order, smallest first.
  • Sorting descending: the revealed order is increasing, so the assignment uses ascending order.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems