Shuffle an Array

LeetCode 384 | Difficulty: Medium

Medium

Problem Description

Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.

Implement the Solution class:

- `Solution(int[] nums)` Initializes the object with the integer array `nums`.

- `int[] reset()` Resets the array to its original configuration and returns it.

- `int[] shuffle()` Returns a random shuffling of the array.

Example 1:

Input
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
Output
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // Shuffle the array [1,2,3] and return its result.
                       // Any permutation of [1,2,3] must be equally likely to be returned.
                       // Example: return [3, 1, 2]
solution.reset();      // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3]
solution.shuffle();    // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]

Constraints:

- `1 <= nums.length <= 50`

- `-10^6 <= nums[i] <= 10^6`

- All the elements of `nums` are **unique**.

- At most `10^4` calls **in total** will be made to `reset` and `shuffle`.

Topics: Array, Math, Design, Randomized

---

Approach

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

Design

Choose the right data structures to meet the required time complexities for each operation. Consider hash maps for O(1) access, doubly-linked lists for O(1) insertion/deletion, and combining structures for complex requirements.

When to use

Implementing a data structure or system with specific operation time requirements.

---

Solutions

Solution 1: C# (Best: 416 ms)

Metric	Value
Runtime	416 ms
Memory	N/A
Date	2018-07-04

Solution

public class Solution {

    private int[] Original { get; set; }
    private int[] Current {get; set;}
    private Random Random {get; set;}
    public Solution(int[] nums)
    {
        Original = new int[nums.Length];
        Current = new int[nums.Length];
        Array.Copy(nums, Original, nums.Length);
        Array.Copy(nums, Current, nums.Length);     
        Random = new Random();
    }

    /** Resets the array to its original configuration and return it. */
    public int[] Reset()
    {
        return Original;
    }

    /** Returns a random shuffling of the array. */
    public int[] Shuffle()
    {       
        for (int i = Original.Length-1; i >= 0; i--)
        {
            var randomIdex = Random.Next(i+1);
            var temp = Current[i];
            Current[i] = Current[randomIdex];
            Current[randomIdex] = temp;                 
        }
        return Current;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.Reset();
 * int[] param_2 = obj.Shuffle();
 */

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Clarify the expected time complexity for each operation before choosing data structures.
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: The solution expects that we always use the original array to shuffle() else some of the test cases fail. (Credits; @snehasingh31)