# LeetCode 950: Reveal Cards In Increasing Order

## Problem Restatement

We are given an array:

```python
deck
```

Each card has a unique integer.

We may reorder the deck however we want. The first element of the returned array is considered the top of the deck.

Then the reveal process works like this:

1. Reveal the top card and remove it.
2. If cards remain, move the next top card to the bottom.
3. Repeat until all cards are revealed.

Return an initial deck order such that the cards are revealed in increasing order.

The official statement asks for an ordering of the deck that reveals the cards in increasing order. It also notes that the first entry in the answer is the top of the deck.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `deck` with unique integers |
| Output | A reordered deck |
| Top card | First element of the returned array |
| Goal | Revealed cards appear in increasing order |
| Constraint | `1 <= deck.length <= 1000` |

Function shape:

```python
class Solution:
    def deckRevealedIncreasing(self, deck: list[int]) -> list[int]:
        ...
```

## Examples

Example 1:

```python
deck = [17, 13, 11, 2, 3, 5, 7]
```

One correct output is:

```python
[2, 13, 3, 11, 5, 17, 7]
```

Reveal process:

```text
reveal 2
move 13 to bottom
reveal 3
move 11 to bottom
reveal 5
move 17 to bottom
reveal 7
move 13 to bottom
reveal 11
move 17 to bottom
reveal 13
reveal 17
```

The revealed order is:

```python
[2, 3, 5, 7, 11, 13, 17]
```

which is increasing.

Example 2:

```python
deck = [1, 1000]
```

A valid answer is:

```python
[1, 1000]
```

The reveal order is already increasing.

## First Thought

The final revealed order must be the sorted deck.

So instead of guessing the card order directly, we can simulate which positions are revealed first.

For example, with `n` cards, the reveal process reveals some index first, then moves the next index to the back, then reveals another index.

If we know the order of revealed positions, we can place the sorted cards into those positions.

## Key Insight

Use a queue of indices.

The queue represents positions in the deck that are still unrevealed.

At each step:

1. Pop the front index.
2. Put the next smallest card there.
3. Move the next front index to the back.

This simulates the reveal process on positions instead of cards.

Because we assign sorted cards in the exact order positions are revealed, the actual reveal process will output cards in increasing order.

## Algorithm

Sort the deck:

```python
deck.sort()
```

Create an answer array:

```python
ans = [0] * len(deck)
```

Create a queue of indices:

```python
queue = deque(range(len(deck)))
```

For each card in sorted order:

1. Remove the front index.
2. Place the card at that index.
3. If the queue still has indices, move the next front index to the back.

Return `ans`.

## Walkthrough

Use:

```python
deck = [17, 13, 11, 2, 3, 5, 7]
```

Sort:

```python
[2, 3, 5, 7, 11, 13, 17]
```

Initial index queue:

```python
[0, 1, 2, 3, 4, 5, 6]
```

| Card | Revealed index | Move next index to back | Partial answer |
|---:|---:|---|---|
| 2 | 0 | move 1 | `[2, _, _, _, _, _, _]` |
| 3 | 2 | move 3 | `[2, _, 3, _, _, _, _]` |
| 5 | 4 | move 5 | `[2, _, 3, _, 5, _, _]` |
| 7 | 6 | move 1 | `[2, _, 3, _, 5, _, 7]` |
| 11 | 3 | move 5 | `[2, _, 3, 11, 5, _, 7]` |
| 13 | 1 | move 5 | `[2, 13, 3, 11, 5, _, 7]` |
| 17 | 5 | none | `[2, 13, 3, 11, 5, 17, 7]` |

Return:

```python
[2, 13, 3, 11, 5, 17, 7]
```

## Correctness

The queue stores exactly the deck positions that have not yet been revealed.

At each step, the forward reveal process would reveal the current top position. The algorithm removes that same front index from the queue and assigns the next smallest card to it.

Then the forward process would move the next top card to the bottom. The algorithm performs the same operation on the remaining indices by moving the next front index to the back.

Therefore, the algorithm computes the exact order in which positions will be revealed.

The deck is sorted before assignment. The first revealed position receives the smallest card, the second revealed position receives the second smallest card, and so on.

So when the returned deck is processed by the reveal rules, the revealed cards appear in sorted increasing order.

Therefore, the returned deck is valid.

## Complexity

Let:

```python
n = len(deck)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n)` | Sorting dominates |
| Space | `O(n)` | Answer array and queue |

## Implementation

```python
from collections import deque

class Solution:
    def deckRevealedIncreasing(self, deck: list[int]) -> list[int]:
        deck.sort()

        n = len(deck)
        ans = [0] * n
        queue = deque(range(n))

        for card in deck:
            index = queue.popleft()
            ans[index] = card

            if queue:
                queue.append(queue.popleft())

        return ans
```

## Code Explanation

Sort the cards so we assign them in the desired reveal order:

```python
deck.sort()
```

Create the result array:

```python
ans = [0] * n
```

Create a queue of positions:

```python
queue = deque(range(n))
```

For each sorted card, choose the next revealed position:

```python
index = queue.popleft()
ans[index] = card
```

Then simulate moving the next top position to the bottom:

```python
if queue:
    queue.append(queue.popleft())
```

At the end, `ans` is the required starting deck order.

## Testing

```python
from collections import deque

def reveal_order(deck):
    q = deque(deck)
    revealed = []

    while q:
        revealed.append(q.popleft())

        if q:
            q.append(q.popleft())

    return revealed

def run_tests():
    s = Solution()

    ans = s.deckRevealedIncreasing([17, 13, 11, 2, 3, 5, 7])
    assert ans == [2, 13, 3, 11, 5, 17, 7]
    assert reveal_order(ans) == [2, 3, 5, 7, 11, 13, 17]

    ans = s.deckRevealedIncreasing([1, 1000])
    assert ans == [1, 1000]
    assert reveal_order(ans) == [1, 1000]

    ans = s.deckRevealedIncreasing([1])
    assert ans == [1]
    assert reveal_order(ans) == [1]

    ans = s.deckRevealedIncreasing([4, 3, 2, 1])
    assert reveal_order(ans) == [1, 2, 3, 4]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[17,13,11,2,3,5,7]` | Standard example |
| `[1,1000]` | Two-card case |
| `[1]` | Single-card case |
| `[4,3,2,1]` | Confirms reveal order, not input order |