# LeetCode 384: Shuffle an Array

## Problem Restatement

We are given an integer array `nums`.

We need to design a class with two operations:

| Operation | Meaning |
|---|---|
| `reset()` | Return the array to its original configuration |
| `shuffle()` | Return a random permutation of the array |

The important requirement is that every possible permutation must be equally likely.

For an array of length `n`, there are `n!` possible permutations. A correct shuffle gives each one the same probability.

The problem guarantees that all elements in `nums` are unique. The array length is at least `1`, and there may be many calls to `reset()` and `shuffle()`.

## Input and Output

| Method | Input | Output |
|---|---|---|
| `Solution(nums)` | Integer array `nums` | Initializes the object |
| `reset()` | None | Original array configuration |
| `shuffle()` | None | Uniformly random permutation |

Example class shape:

```python
class Solution:

    def __init__(self, nums: list[int]):
        ...

    def reset(self) -> list[int]:
        ...

    def shuffle(self) -> list[int]:
        ...
```

## Examples

Example:

```python
solution = Solution([1, 2, 3])
```

Calling:

```python
solution.shuffle()
```

may return:

```python
[3, 1, 2]
```

Calling:

```python
solution.reset()
```

returns:

```python
[1, 2, 3]
```

Calling:

```python
solution.shuffle()
```

may return another valid shuffle:

```python
[1, 3, 2]
```

For `[1, 2, 3]`, all six permutations should be equally likely:

```python
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
```

Each one should have probability `1 / 6`.

## First Thought: Randomly Pick Until Empty

A simple way to shuffle is:

1. Put all numbers into a temporary list.
2. Randomly pick one number.
3. Remove it from the temporary list.
4. Repeat until no numbers remain.

This produces a random permutation, but removing from the middle of a Python list costs `O(n)`.

So the full shuffle can become `O(n^2)`.

We want a direct `O(n)` method.

## Key Insight

Use the Fisher-Yates shuffle.

The idea is to fill the shuffled array one position at a time.

At index `i`, choose one random index `j` from the still-unfixed range:

```python
i <= j < n
```

Then swap:

```python
arr[i], arr[j] = arr[j], arr[i]
```

After this swap, position `i` is fixed.

Then move to `i + 1`.

This works because each position chooses uniformly among the remaining elements.

## Algorithm

Store the original array:

```python
self.original = nums[:]
```

For `reset()`:

1. Return a copy of `self.original`.

For `shuffle()`:

1. Make a copy of the original array.
2. For every index `i` from `0` to `n - 1`:
   - Pick random index `j` from `i` to `n - 1`.
   - Swap `arr[i]` and `arr[j]`.
3. Return `arr`.

## Correctness

At the first position, the algorithm chooses uniformly from all `n` elements.

So every element has probability `1 / n` of being placed at index `0`.

After index `0` is fixed, there are `n - 1` remaining elements.

At index `1`, the algorithm chooses uniformly from those remaining elements.

So each remaining element has probability `1 / (n - 1)` of being placed at index `1`, conditioned on the first choice.

This continues until every position is fixed.

For any specific permutation, the probability of producing it is:

```text
(1 / n) * (1 / (n - 1)) * (1 / (n - 2)) * ... * (1 / 1)
```

That equals:

```text
1 / n!
```

Since every permutation has the same probability, the shuffle is uniform.

The `reset()` method returns the saved original configuration, so it restores the array correctly.

## Complexity

Let `n = len(nums)`.

| Operation | Time | Space | Why |
|---|---|---|---|
| Constructor | `O(n)` | `O(n)` | Stores a copy of the original array |
| `reset()` | `O(n)` | `O(n)` | Returns a copy of the original array |
| `shuffle()` | `O(n)` | `O(n)` | Copies and shuffles the array |

The extra `O(n)` space in `shuffle()` comes from returning a shuffled copy.

## Implementation

```python
import random

class Solution:

    def __init__(self, nums: list[int]):
        self.original = nums[:]

    def reset(self) -> list[int]:
        return self.original[:]

    def shuffle(self) -> list[int]:
        arr = self.original[:]
        n = len(arr)

        for i in range(n):
            j = random.randint(i, n - 1)
            arr[i], arr[j] = arr[j], arr[i]

        return arr
```

## Code Explanation

We store a copy of the original input:

```python
self.original = nums[:]
```

This protects the original order from future shuffle operations.

The `reset()` method returns a new copy:

```python
return self.original[:]
```

Returning a copy is safer than returning the internal list directly, because external code should not mutate `self.original`.

For shuffling, we also start from a fresh copy:

```python
arr = self.original[:]
```

Then we apply Fisher-Yates:

```python
for i in range(n):
    j = random.randint(i, n - 1)
    arr[i], arr[j] = arr[j], arr[i]
```

At each index `i`, we choose one of the remaining positions uniformly and swap it into place.

Finally:

```python
return arr
```

## Testing

Randomized code should not be tested by expecting one fixed shuffled output.

Instead, test structural properties:

```python
def test_solution():
    nums = [1, 2, 3]
    s = Solution(nums)

    assert s.reset() == [1, 2, 3]

    shuffled = s.shuffle()
    assert sorted(shuffled) == [1, 2, 3]

    assert s.reset() == [1, 2, 3]

    single = Solution([42])
    assert single.shuffle() == [42]
    assert single.reset() == [42]

    nums2 = [-1, 0, 7, 9]
    s2 = Solution(nums2)

    for _ in range(100):
        shuffled = s2.shuffle()
        assert sorted(shuffled) == sorted(nums2)

    assert s2.reset() == nums2

    print("all tests passed")

test_solution()
```

Test meaning:

| Test | Why |
|---|---|
| `reset()` after construction | Original order is preserved |
| Sorted shuffled output | Shuffle contains the same elements |
| `reset()` after shuffle | Shuffle does not destroy original array |
| Single element | Only one possible permutation |
| Repeated shuffles | Every shuffle remains a valid permutation |