Reveal Cards In Increasing Order

Medium
392.

Reveal Cards In Increasing Order

Reveal Cards In Increasing Order is a medium coding problem on arrays, sorting and simulation, asked in Amazon and Google interviews.

You have a deck of cards with distinct values, face down. You reveal them like this, repeating until the deck is empty:

  1. reveal the top card;
  2. if any cards remain, move the next top card to the bottom of the deck.

Return the ordering of the deck that would reveal the cards in increasing order.

Example 1

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

Example 2

Input
deck = [1,1000]
Output
[1,1000]

Example 3

Input
deck = [1]
Output
[1]

Constraints

  • 1 <= deck.length <= 30
  • 1 <= deck[i] <= 1000000
  • All values are distinct.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} deck
 * @return {number[]}
 */
var deckRevealedIncreasing = function(deck) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Reveal Cards In Increasing Order — Problem & Solution

Reveal Cards In Increasing Order solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Reveal Cards In Increasing Order is a medium coding problem on arrays, sorting and simulation, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Simulation, Queue
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You have a deck of cards with distinct values, face down. You reveal them like this, repeating until the deck is empty:

  1. reveal the top card;
  2. if any cards remain, move the next top card to the bottom of the deck.

Return the ordering of the deck that would reveal the cards in increasing order.

Example 1

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

Example 2

Input: deck = [1,1000]
Output: [1,1000]

Example 3

Input: deck = [1]
Output: [1]

Constraints

  • 1 <= deck.length <= 30
  • 1 <= deck[i] <= 1000000
  • All values are distinct.

Hints for Reveal Cards In Increasing Order

  1. Hint 1

    Run the reveal procedure on the positions 0, 1, …, n-1 instead of on the cards.

  2. Hint 2

    That tells you the order in which slots get filled.

  3. Hint 3

    Fill those slots with the sorted values, smallest first.

How to solve Reveal Cards In Increasing Order

Run the reveal procedure on the slot indices 0..n-1 to learn the order in which positions are revealed, then fill those positions with the sorted values.

Approach

  1. Sort the deck and put 0..n-1 in a queue.
  2. For each sorted value: pop a slot and assign the value; if slots remain, move the next slot to the back.

Why it works

The reveal order is a fixed permutation of positions independent of the card values, so assigning increasing values to positions in reveal order produces the required deck.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Do the rotate step only when the queue is non-empty after the pop.

Reference solution

Python

from collections import deque

def deckRevealedIncreasing(deck):
    ordered = sorted(deck)
    slots = deque(range(len(deck)))
    out = [0] * len(deck)
    for value in ordered:
        out[slots.popleft()] = value
        if slots:
            slots.append(slots.popleft())
    return out

Java

public static int[] deckRevealedIncreasing(int[] deck) {
    int[] sorted = deck.clone();
    Arrays.sort(sorted);
    Deque<Integer> slots = new ArrayDeque<>();
    for (int i = 0; i < deck.length; i++) slots.addLast(i);
    int[] out = new int[deck.length];
    for (int value : sorted) {
        out[slots.pollFirst()] = value;
        if (!slots.isEmpty()) slots.addLast(slots.pollFirst());
    }
    return out;
}

C++

vector<int> deckRevealedIncreasing(vector<int>& deck) {
    vector<int> sorted = deck;
    sort(sorted.begin(), sorted.end());
    deque<int> slots;
    for (int i = 0; i < (int) deck.size(); i++) slots.push_back(i);
    vector<int> out(deck.size(), 0);
    for (int value : sorted) {
        out[slots.front()] = value;
        slots.pop_front();
        if (!slots.empty()) {
            slots.push_back(slots.front());
            slots.pop_front();
        }
    }
    return out;
}

JavaScript

var deckRevealedIncreasing = function(deck) {
    const sorted = deck.slice().sort(function(a, b) { return a - b; });
    const slots = [];
    for (let i = 0; i < deck.length; i++) slots.push(i);
    const out = [];
    for (let i = 0; i < deck.length; i++) out.push(0);
    let head = 0;
    for (let i = 0; i < sorted.length; i++) {
        out[slots[head++]] = sorted[i];
        if (head < slots.length) {
            slots.push(slots[head++]);
        }
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms