Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Reveal Cards In Increasing Order

Try it yourself
MediumProblemExternal link

Description

You get a deck of cards, each with a distinct integer, in any order. A dealer handles the deck like this:

  1. Turn the top card face up and set it aside.
  2. If cards are left, move the next top card to the bottom of the deck.
  3. Repeat until no cards are left.

Return an ordering of the deck, top card first, that makes the cards come face up in increasing order.

Examples

Example 1

Input: deck = [17, 13, 11, 2, 3, 5, 7]

Output: [2, 13, 3, 11, 5, 17, 7]

Explanation: Deal [2, 13, 3, 11, 5, 17, 7]: turn up 2 and move 13 to the bottom, turn up 3 and move 11 down, and so on. The cards come up 2, 3, 5, 7, 11, 13, 17.

Example 2

Input: deck = [1, 1000]

Output: [1, 1000]

Explanation: Turn up 1, move 1000 to the bottom, then turn it up.

Example 3

Input: deck = [42]

Output: [42]

Explanation: A single card is already in order.

Constraints

  • 1 ≤ deck.length ≤ 1000
  • 1 ≤ deck[i] ≤ 10^6
  • All the values of deck are unique

Editorial

Brute Force

Intuition

Run the deal backwards. The last card turned up is the largest, and before that the dealer had just moved a card from the top to the bottom. So start from an empty pile and take the cards from the largest down: move the bottom card back to the top (undoing the move), then put the card on top (undoing the turn-up). When every card is placed, the pile is the answer.

Step-by-Step Explanation

Let's trace deck = [17, 13, 11, 2, 3, 5, 7]:

  1. Put 17, the largest, on the empty pile. The pile is 17.
  2. Move 17 from the bottom back to the top, then put 13 on top. The pile is 13, 17.
  3. Move 17 from the bottom back to the top, then put 11 on top. The pile is 11, 17, 13.
  4. Move 13 from the bottom back to the top, then put 7 on top. The pile is 7, 13, 11, 17.
  5. Move 17 from the bottom back to the top, then put 5 on top. The pile is 5, 17, 7, 13, 11.
  6. Move 11 from the bottom back to the top, then put 3 on top. The pile is 3, 11, 5, 17, 7, 13.
  7. Move 13 from the bottom back to the top, then put 2 on top. The pile is 2, 13, 3, 11, 5, 17, 7.

Undo the Deal — Each card goes on top after the bottom card moves back up.

Algorithm

  1. Sort the cards from largest to smallest.
  2. For each card: if the pile isn't empty, move its bottom card to the top. Then put the card on top.
  3. Return the pile, top first.

Code

class Solution {
public:
    vector<int> deckRevealedIncreasing(vector<int>& deck) {
        vector<int> sorted = deck;
        sort(sorted.rbegin(), sorted.rend());    // the largest first: it's turned up last
        vector<int> pile;                        // top first
        for (int card : sorted) {
            if (!pile.empty()) {                 // undo "move the top card to the bottom"
                pile.insert(pile.begin(), pile.back());
                pile.pop_back();
            }
            pile.insert(pile.begin(), card);     // undo "turn up the top card"
        }
        return pile;
    }
};

class Solution:
    def deckRevealedIncreasing(self, deck: list[int]) -> list[int]:
        pile = []                                # top first
        for card in sorted(deck, reverse=True):  # the largest first: it's turned up last
            if pile:
                pile.insert(0, pile.pop())       # undo "move the top card to the bottom"
            pile.insert(0, card)                 # undo "turn up the top card"
        return pile

class Solution {
    public int[] deckRevealedIncreasing(int[] deck) {
        int[] sorted = deck.clone();
        Arrays.sort(sorted);
        List<Integer> pile = new ArrayList<>();               // top first
        for (int i = sorted.length - 1; i >= 0; i--) {        // the largest first: it's turned up last
            if (!pile.isEmpty()) pile.add(0, pile.remove(pile.size() - 1));   // undo "move the top card down"
            pile.add(0, sorted[i]);                           // undo "turn up the top card"
        }
        int[] result = new int[pile.size()];
        for (int i = 0; i < result.length; i++) result[i] = pile.get(i);
        return result;
    }
}

var deckRevealedIncreasing = function(deck) {
    const sorted = [...deck].sort((a, b) => b - a);   // the largest first: it's turned up last
    const pile = [];                         // top first
    for (const card of sorted) {
        if (pile.length) pile.unshift(pile.pop());    // undo "move the top card to the bottom"
        pile.unshift(card);                  // undo "turn up the top card"
    }
    return pile;
};

Complexity Analysis

Time Complexity: O(n²)

Sorting is O(n log n), but every insert at the top of a list shifts the whole pile: n inserts of up to n moves each.

Space Complexity: O(n)

The pile.

Why This Approach Is Not Efficient

With at most 1,000 cards it still fits: about 10^6 moves. The cost comes from inserting at the top of a list; a deque would make those O(1). But there's a simpler way to see the whole problem: the deal itself doesn't depend on the card values at all. Position 0 is always turned up first, position 1 always goes to the bottom, and so on.

So run the dealer forwards, once, on the positions instead of the cards, with a queue. The order in which positions come up is the order the sorted cards must fill them.

Optimal Approach - Deal the Positions With a Queue

Intuition

Put the positions 0 to n − 1 in a queue: that's the face-down deck. Sort the cards. Then deal the queue the dealer's way: pop the front position, which is turned up next, and give it the smallest card not yet placed; then, if positions are left, move the next front position to the back. Each position ends up with the card that comes up at its turn, so the cards come up sorted.

Step-by-Step Explanation

Let's trace deck = [17, 13, 11, 2, 3, 5, 7], sorted 2, 3, 5, 7, 11, 13, 17:

  1. Position 0 is turned up: it gets 2. Position 1 moves to the bottom.
  2. Position 2 is turned up: it gets 3. Position 3 moves to the bottom.
  3. Position 4 is turned up: it gets 5. Position 5 moves to the bottom.
  4. Position 6 is turned up: it gets 7. Position 1 moves to the bottom.
  5. Position 3 is turned up: it gets 11. Position 5 moves to the bottom.
  6. Position 1 is turned up: it gets 13. Position 5 moves to the bottom.
  7. Position 5 is the last: it gets 17.

The arrangement is [2, 13, 3, 11, 5, 17, 7].

Deal the Positions — The queue holds the positions still face down; each one turned up gets the next smallest card.

Algorithm

  1. Sort deck. Put the positions 0 … n − 1 in a queue.
  2. For each card, smallest first: pop the front position and write the card there. If the queue isn't empty, pop its front and push it to the back.
  3. Return the result array.

Code

JavaScript keeps the queue in an array with a head index, so no shift() is needed.

class Solution {
public:
    vector<int> deckRevealedIncreasing(vector<int>& deck) {
        int n = deck.size();
        queue<int> positions;                    // the deck's positions, top first
        for (int i = 0; i < n; i++) positions.push(i);
        vector<int> sorted = deck;
        sort(sorted.begin(), sorted.end());
        vector<int> result(n);
        for (int card : sorted) {                // the smallest card goes to the first position turned up
            result[positions.front()] = card;    // turn the top position up
            positions.pop();
            if (!positions.empty()) {            // move the next one to the bottom
                positions.push(positions.front());
                positions.pop();
            }
        }
        return result;
    }
};

from collections import deque

class Solution:
    def deckRevealedIncreasing(self, deck: list[int]) -> list[int]:
        positions = deque(range(len(deck)))  # the deck's positions, top first
        result = [0] * len(deck)
        for card in sorted(deck):            # the smallest card goes to the first position turned up
            result[positions.popleft()] = card   # turn the top position up
            if positions:
                positions.append(positions.popleft())   # move the next one to the bottom
        return result

class Solution {
    public int[] deckRevealedIncreasing(int[] deck) {
        int n = deck.length;
        Deque<Integer> positions = new ArrayDeque<>();   // the deck's positions, top first
        for (int i = 0; i < n; i++) positions.offerLast(i);
        int[] sorted = deck.clone();
        Arrays.sort(sorted);
        int[] result = new int[n];
        for (int card : sorted) {                        // the smallest card goes to the first position turned up
            result[positions.pollFirst()] = card;        // turn the top position up
            if (!positions.isEmpty()) positions.offerLast(positions.pollFirst());   // move the next one to the bottom
        }
        return result;
    }
}

var deckRevealedIncreasing = function(deck) {
    const n = deck.length;
    const positions = [];                    // the deck's positions, top first, as a queue
    for (let i = 0; i < n; i++) positions.push(i);
    let head = 0;                            // the top of the queue; no shift() needed
    const result = new Array(n);
    const sorted = [...deck].sort((a, b) => a - b);
    for (const card of sorted) {             // the smallest card goes to the first position turned up
        result[positions[head++]] = card;    // turn the top position up
        if (head < positions.length) positions.push(positions[head++]);   // move the next one to the bottom
    }
    return result;
};

Complexity Analysis

Time Complexity: O(n log n)

The sort; the deal itself is O(n), one pop and at most one move per card.

Space Complexity: O(n)

The queue of positions and the result.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Moving a card down before turning one up. positions.append(positions.popleft())

On deck = [17, 13, 11, 2, 3, 5, 7] it returns [7, 2, 13, 3, 11, 5, 17], which deals as 7, 13, 11, 17, 3, 2 and 5; the answer is [2, 13, 3, 11, 5, 17, 7]. The dealer turns the top card up first and only then moves the next one to the bottom. Swapping the two steps deals a different order, so the cards land in the wrong positions.

Dealing the cards in the order given. for card in deck:

On deck = [5, 2, 4, 1, 3] it returns [5, 3, 2, 1, 4], which deals as 5, 2, 4, 1 and 3; the answer is [1, 5, 2, 4, 3]. The cards have to come up smallest first, so the smallest card goes to the first position turned up. Dealing the deck in the order it arrived only works when it arrives sorted.

Undoing the deal from the smallest card. for card in sorted(deck):

On deck = [17, 13, 11, 2, 3, 5, 7] it returns [17, 3, 13, 5, 11, 2, 7], which deals as 17, 13, 11, 7, 5, 3 and 2; the answer is [2, 13, 3, 11, 5, 17, 7]. Undoing the deal starts from the last card turned up, the largest. Starting from the smallest builds a deck that comes up in decreasing order.

Where This Pattern Is Taught

This problem practises running a process with a queue. It's taught in Introduction to Queues, alongside the Josephus circle of Find the Winner of the Circular Game.