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:
- reveal the top card;
- 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 <= 301 <= deck[i] <= 1000000All values are distinct.
Hints for Reveal Cards In Increasing Order
Hint 1
Run the reveal procedure on the positions 0, 1, …, n-1 instead of on the cards.
Hint 2
That tells you the order in which slots get filled.
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
- Sort the deck and put
0..n-1in a queue. - 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 outJava
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