Reveal Cards In Increasing Order

How it works

Instead of using a queue or deque, we can simulate the assignment directly on the result array. We track which positions are still empty and use a skip flag to alternate between placing a card and skipping a position (mirroring the reveal process). This approach uses constant extra space beyond the result array.

Steps

1. Sort the deck in ascending order.
2. Create a result array res filled with zeros (to mark empty positions).
3. Initialize a deck index deckIndex pointing to the smallest card, a position pointer i at 0, and a skip flag skip set to false.
4. While cards remain to be placed:
   • If the current position is empty (value is 0):
     • If not skipping, place the current card and advance the deck index.
     • Toggle the skip flag.
   • Move to the next position (wrapping around with modulo).
5. Return the result array.

Complexity

• Time complexity: O(n log n)
• Space complexity:
  • O(1) or O(n) space depending on the sorting algorithm.
  • O(n) space for the output array.

Things to watch for

Forgetting to Sort the Deck First

A common mistake is attempting to simulate the reveal process without first sorting the deck. The algorithm relies on assigning cards from smallest to largest, so forgetting to sort results in an incorrect arrangement where cards do not reveal in increasing order.

Skipping the Queue Rotation Step

When simulating the reveal process, each card placement must be followed by rotating the next available index to the back of the queue. Forgetting this rotation step breaks the alternating pattern and places cards in wrong positions, causing the reveal sequence to be out of order.

Off-by-One Errors in Position Tracking

The skip-and-place pattern requires careful index management. A common error is miscounting positions or incorrectly handling the wrap-around when traversing the result array. This leads to cards being placed at incorrect indices or infinite loops when positions are not properly marked as filled.

from typing import List

class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        n = len(deck)
        res = [0] * n
        skip = False
        deckIndex, i = 0, 0

        deck.sort()

        while deckIndex < n:
            if res[i] == 0:
                if not skip:
                    res[i] = deck[deckIndex]
                    deckIndex += 1
                skip = not skip
            i = (i + 1) % n

        return res

class Solution {
public:
    vector<int> deckRevealedIncreasing(vector<int>& deck) {
        int n = deck.size();
        vector<int> res(n, 0);
        bool skip = false;
        int deckIndex = 0, i = 0;

        sort(deck.begin(), deck.end());

        while (deckIndex < n) {
            if (res[i] == 0) {
                if (!skip) {
                    res[i] = deck[deckIndex++];
                }
                skip = !skip;
            }
            i = (i + 1) % n;
        }

        return res;
    }
};