How do you solve Shuffle an Array on LeetCode?

Shuffle an Array (LeetCode #384) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The Fisher-Yates algorithm is efficient for shuffling arrays.

What is the brute force solution for Shuffle an Array?

The brute force approach for Shuffle an Array is Brute Force, with O(n²) time complexity and O(n!) space complexity. The brute force approach involves generating all possible permutations of the array and then randomly selecting one of them. This guarantees that every permutation is equally likely, but it's inefficient for larger arrays. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Shuffle an Array?

Shuffle an Array uses the following concepts: Array, Math, Design, Randomized. The recommended patterns to study are: Array, Randomized Algorithms.

What are the interview tips for Shuffle an Array?

Explain your thought process clearly; interviewers value understanding over just getting the right answer. Discuss edge cases, like very small arrays or arrays with duplicate elements, even if the problem states they are unique. Practice coding the Fisher-Yates shuffle multiple times to become comfortable with it.

What are common mistakes when solving Shuffle an Array?

Confusing shuffling with sorting; shuffling should maintain the original array's elements. Not using a random index correctly, leading to biased results.

#384

Shuffle an Array

Medium

ArrayMathDesignRandomizedArrayRandomized Algorithms

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n!)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses the Fisher-Yates shuffle algorithm, which efficiently shuffles the array in place. This method ensures that each element has an equal probability of ending up in any position, achieving the desired randomness without generating all permutations.

⚙️

Algorithm

4 steps

1Step 1: Create a copy of the original array.
2Step 2: Iterate through the array from the last index to the first.
3Step 3: For each index, generate a random index from 0 to the current index.
4Step 4: Swap the current element with the element at the random index.

solution.py17 lines

1# Full working Python code
2import random
3
4class Solution:
5    def __init__(self, nums):
6        self.original = nums[:]
7        self.nums = nums
8
9    def reset(self):
10        return self.original
11
12    def shuffle(self):
13        shuffled = self.nums[:]
14        for i in range(len(shuffled) - 1, 0, -1):
15            j = random.randint(0, i)
16            shuffled[i], shuffled[j] = shuffled[j], shuffled[i]
17        return shuffled

ℹ

Complexity note: The Fisher-Yates shuffle runs in linear time O(n) because it processes each element once, and uses O(n) space for the copy of the array.

1The Fisher-Yates algorithm is efficient for shuffling arrays.
2Randomness can be achieved without generating all permutations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.