Riffle the Deck in Place
MediumArrays & Hashing
Problem
A card shuffler holds a deck of 2m cards as deck = [x1, x2, …, xm, y1, y2, …, ym]. A perfect riffle interleaves the two halves into [x1, y1, x2, y2, …, xm, ym].
Perform the riffle in place with O(1) extra space. Every card value is between 1 and 1000. The function returns nothing.
Example 1
- Input:
- deck = [2, 5, 1, 3, 4, 7]
- Output:
- [2, 3, 5, 4, 1, 7]
Halves [2, 5, 1] and [3, 4, 7] are interleaved.
Example 2
- Input:
- deck = [1, 1, 2, 2]
- Output:
- [1, 2, 1, 2]
Example 3
- Input:
- deck = [9, 4]
- Output:
- [9, 4]
Constraints
- 2 ≤ deck.length = 2m ≤ 10^4
- 1 ≤ deck[i] ≤ 1000
- O(1) extra space.
Hint
Show the first hint
Where does the card at index i end up? Write the destination as a formula.
Walkthrough
How to approach it
01Clarify before coding
- Is a second array allowed? No, O(1) extra space.
- Why does the value range matter? A bounded range lets one slot carry two values at once.
- Is the deck length always even? Yes, 2m.
02Brute force
Copy the deck and write copy[i] and copy[m + i] into slots 2i and 2i + 1; or shift elements one by one into place.
Cost: The copy is O(n) time but O(n) extra space. Shifting in place is O(n²) time.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.