Log inSign up
mediumLeetCodeNot Started

Shuffle an Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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 · Standard Shuffle and Reset:

Input: nums = [1, 2, 3]
Output: shuffle() -> [3, 1, 2] (any of 6 permutations), reset() -> [1, 2, 3]
Explanation: Each permutation has exactly 1/6 probability.

Constraints:

  • 1 <= nums.length <= 50
  • -106 <= nums[i] <= 106
  • All the elements of nums are unique.
  • At most 104 calls in total will be made to reset and shuffle.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Uniform random integer generation in [min, max]
  • Probability theory & permutation counting (N!)
  • In-place array element swapping

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Prove the uniformity of the Fisher-Yates shuffle algorithm.
  • Avoid the common naive shuffle bias mistake (swapping with range [0, n-1]).
  • Maintain pristine snapshots for reset operations.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Random Pick with BlacklistReservoir Sampling

1. Remove-From-List Simulation (Brute Force)

Intuition

To shuffle n elements: copy nums into a dynamic list. In each step, pick a random index in [0, list.size() - 1], append list[index] to the shuffled result, and remove it from the list. Removing from a dynamic list takes O(n), yielding O(n2) time.

When to apply: Use to understand the uniform selection from a shrinking urn of elements.

Urn Removal Shuffle Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3]
Current operationSTEP 1 OF 6
Initial array: [1, 2, 3]
Visual state
Values and pointers at this exact step
array
S
1
2
3
0
↑ Urn
1
2
Variables at this step
urn
[1,2,3]
res
[]
Check / comparison
Urn size = 3
Decision / next transition
Pick first element.
Why this step matters

Initial array: [1, 2, 3]. Copy to dynamic urn: [1, 2, 3].

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 private int[] original;
6 private Random rand = new Random();
7
8 public Solution(int[] nums) {
9 this.original = nums.clone();
10 }
11
12 public int[] reset() {
13 return original.clone();
14 }
15
16 public int[] shuffle() {
17 List<Integer> list = new ArrayList<>();
18 for (int x : original) list.add(x);
19 int[] res = new int[original.length];
20 for (int i = 0; i < res.length; i++) {
21 int idx = rand.nextInt(list.size());
22 res[i] = list.remove(idx);
23 }
24 return res;
25 }
26 }
27
28 public static void main(String[] args) {
29 int[] nums = {1, 2, 3};
30 Solution sol = new Solution(nums);
31 System.out.println("Shuffled: " + Arrays.toString(sol.shuffle()));
32 System.out.println("Reset: " + Arrays.toString(sol.reset()));
33 }
34}

Time & Space Complexity

  • Time complexity: O(n^2) shuffle — n removals, each shifting elements in O(n) time, takes O(n2) total time.
  • Space complexity: O(n) — O(n) auxiliary list to hold candidates.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Random Weights Sorting (Better)

Intuition

Assign each element a random key u_i in (0, 1). Sorting the elements by their keys produces a completely uniform random permutation with probability 1/n! for each arrangement.

When to apply: Use to illustrate the equivalence between random sorting keys and uniform random permutations.

Random Weight Key Sorting Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3]
Current operationSTEP 1 OF 6
Array: [1, 2, 3]
Visual state
Values and pointers at this exact step
pointers
S
1
2
3
0
↑ Init keys
1
2
Variables at this step
pairs
[(0.82, 1), (0.15, 2), (0.47, 3)]
Check / comparison
Keys: [0.82, 0.15, 0.47]
Decision / next transition
Pairs created: (0.82, 1), (0.15, 2), (0.47, 3).
Why this step matters

Array: [1, 2, 3]. Generate random keys: key(1) = 0.82, key(2) = 0.15, key(3) = 0.47.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 private int[] original;
6 private Random rand = new Random();
7
8 public Solution(int[] nums) {
9 this.original = nums.clone();
10 }
11
12 public int[] reset() {
13 return original.clone();
14 }
15
16 public int[] shuffle() {
17 int n = original.length;
18 Double[][] pairs = new Double[n][2];
19 for (int i = 0; i < n; i++) {
20 pairs[i][0] = rand.nextDouble();
21 pairs[i][1] = (double)original[i];
22 }
23 Arrays.sort(pairs, Comparator.comparingDouble(a -> a[0]));
24 int[] res = new int[n];
25 for (int i = 0; i < n; i++) {
26 res[i] = pairs[i][1].intValue();
27 }
28 return res;
29 }
30 }
31
32 public static void main(String[] args) {
33 int[] nums = {1, 2, 3};
34 Solution sol = new Solution(nums);
35 System.out.println("Shuffled: " + Arrays.toString(sol.shuffle()));
36 System.out.println("Reset: " + Arrays.toString(sol.reset()));
37 }
38}

Time & Space Complexity

  • Time complexity: O(n log n) shuffle — Sorting n elements with random keys takes O(n log n) time.
  • Space complexity: O(n) — O(n) auxiliary memory for keys and pair array.

3. Fisher-Yates Modern Shuffle (Optimal)

Intuition

The Fisher-Yates (Knuth) algorithm iterates backwards from index i = n - 1 down to 1. In each step, pick a uniformly random index j in range [0, i] and swap arr[i] with arr[j]. Each permutation has exact equal probability 1/n!, achieving optimal O(n) time and O(1) extra space outside the return clone.

When to apply: Use as the optimal industry-standard unbiased random shuffle.

Fisher-Yates Swap Interactive Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3]
Current operationSTEP 1 OF 6
Step 1: Clone arr = [1, 2, 3]
Visual state
Values and pointers at this exact step
pointers
S
3
2
1
0
↑ j=0
1
2
↑ i=2
Variables at this step
i
2
j
0
arr
[3,2,1]
Check / comparison
i = 2, random j = 0
Decision / next transition
Swap arr[2] (3) and arr[0] (1). Array becomes [3, 2, 1]. Element at index 2 is locked.
Why this step matters

Step 1: Clone arr = [1, 2, 3]. Start at i = 2. Randomly choose j in [0, 2]. Suppose j = 0.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 private int[] original;
6 private Random rand = new Random();
7
8 public Solution(int[] nums) {
9 this.original = nums.clone();
10 }
11
12 public int[] reset() {
13 return original.clone();
14 }
15
16 public int[] shuffle() {
17 int[] arr = original.clone();
18 for (int i = arr.length - 1; i > 0; i--) {
19 int j = rand.nextInt(i + 1);
20 int temp = arr[i];
21 arr[i] = arr[j];
22 arr[j] = temp;
23 }
24 return arr;
25 }
26 }
27
28 public static void main(String[] args) {
29 int[] nums = {1, 2, 3};
30 Solution sol = new Solution(nums);
31 System.out.println("Shuffled: " + Arrays.toString(sol.shuffle()));
32 System.out.println("Reset: " + Arrays.toString(sol.reset()));
33 }
34}

Time & Space Complexity

  • Time complexity: O(n) shuffle, O(1) reset — n - 1 random index generations and element swaps, each taking O(1) time.
  • Space complexity: O(n) for clone — O(n) memory to hold the cloned array returned by shuffle and the original reset copy.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — List Deletion SamplingO(N^2)O(N)Copy elements to a list, randomly pick an element, remove it from list, and append to result.List deletion / shifting.
2.Better — Sort by Random KeysO(N log N)O(N)Pair each element with a random float key, then sort by the keys.Sorting overhead.
3.Optimal — Fisher-Yates (Knuth) ShuffleOptimalO(N) shuffle, O(1) resetO(N)In-place prefix swapping with random elements chosen from remaining suffix [i..n-1].Optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Empty or Single Element Array — Handle minimal input sizes (N = 0 or N = 1) cleanly without out-of-bounds errors.
  • Duplicate Elements — Verify behavior when all elements are identical (e.g. all 0s or all equal values).
  • Extreme Numerical Values — Account for maximum/minimum allowed constraint values (-109 to 109) to prevent overflow.
  • Boundary Conditions — Ensure correct execution when target or match is located at the first or last index.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Shuffle an Array?

2.Why is the brute force approach suboptimal for large inputs in Shuffle an Array?

3.Which data structure or technique enables the optimal solution for Shuffle an Array?

Back to DSA Sheet