Practice/Uber/Leetcode 384. Shuffle an Array

Leetcode 384. Shuffle an Array

CodingMust

Problem

Implement a data structure that maintains an integer array and provides two key operations:

1. reset() - Returns the array to its original state as it was initialized
2. shuffle() - Returns a randomly permuted version of the array where every possible permutation has equal probability

The shuffle operation must be truly unbiased, meaning if there are n! possible permutations of the array, each one should have exactly 1/n! probability of occurring.

Requirements

1. Store the original array configuration permanently for reset operations
2. Implement an unbiased shuffling algorithm (all permutations equally likely)
3. The reset method should return the original array in O(1) or O(n) time
4. The shuffle method should generate a uniformly random permutation
5. Support multiple consecutive shuffle and reset operations

Constraints

• 1 ≤ array length ≤ 200
• -10^6 ≤ array[i] ≤ 10^6
• Up to 5 × 10^4 calls will be made to reset and shuffle combined
• Time complexity for shuffle should be O(n)
• Space complexity should be O(n)

Examples

Example 1:

RandomArray ra = new RandomArray([1, 2, 3]) ra.shuffle() // Returns [3, 1, 2] (one of 6 possible permutations) ra.reset() // Returns [1, 2, 3] ra.shuffle() // Returns [2, 3, 1] (any permutation possible)

Example 2:

RandomArray ra = new RandomArray([4, 4, 5]) ra.shuffle() // Returns [4, 5, 4] or any permutation ra.reset() // Returns [4, 4, 5] ra.shuffle() // Returns [5, 4, 4] or any permutation ra.reset() // Returns [4, 4, 5]

Example 3:

RandomArray ra = new RandomArray([1]) ra.shuffle() // Returns [1] (only one permutation exists) ra.reset() // Returns [1]