MediumArrayMathDesignRandomizedUpdated Sep 2026

384. Shuffle an Array

Asked at Uber

Difficulty

Medium

Time

O(n) per shuffle or reset

Space

O(n)

Pattern

Array

Companies

1

Problem

Design a class Solution that holds an array of integers and can do two things on demand: return the array in its original order, or return a randomly shuffled version of it.

The key rule is fairness: every possible ordering (permutation) of the array must have the same chance of appearing. A shuffle that favors some orderings is wrong, even if it looks random.

Implement three methods. The constructor Solution(nums) saves the starting array. reset() puts the array back to that starting order and returns it. shuffle() returns a random permutation of the array. Each call to shuffle() must be independent — calling it twice can give two different results.

Two operations on the same array

original123012The constructor saves this order so reset() canrestore it later.shuffle()312012One possible shuffle result — all 6 orderings must beequally likely.
reset() must always give back the saved original, while shuffle() must give a fresh random ordering every time.

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.

Examples

Example 1
Input["Solution", "shuffle", "reset", "shuffle"] [[[1, 2, 3]], [], [], []]
Output[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
WhyThe constructor returns nothing (null). The first shuffle happens to produce [3, 1, 2] — any of the 6 orderings was equally possible. reset() brings back the saved original [1, 2, 3]. The second shuffle happens to produce [1, 3, 2], a different random ordering.
Example 2
Input["Solution", "shuffle", "reset"] [[[1]], [], []]
Output[null, [1], [1]]
WhyWith a single element there is only one permutation, so shuffle and reset both return [1].

Asked At

1 companies
CompanyDifficulty
UberMediumView all Uber questions →

How to Think About It

1

Store the original array for reset operations

2

Implement Fisher-Yates shuffle for uniform random permutation

3

Iterate from last element to first, swapping with random index

4

Ensure random index is within valid range for each position

5

Reset simply restores the original array copy

Optimal Approach

Store a copy of the original array. For shuffle, iterate from the last element to the first. For each position i, generate a random index j where 0 <= j <= i, then swap elements at positions i and j. This Fisher-Yates algorithm guarantees uniform random permutation in O(n) time. Reset simply restores the saved original array.

Fisher-Yates: swap the last slot with a random earlier slot

arr123012iStart at i = 2 (the last index).arr123012iPick j = 0 at random, then swap positions 0 and 2.arr321012iIndex 2 is now fixed. Move i to 1 and pick j in 0..1.for i from n-1 down to 1: j = random(0, i) swap(arr[i], arr[j])
Walk from the end to the front. At each index i, pick a random j in 0..i and swap, so every ordering is equally likely.
ComplexityTime O(n) per shuffle or resetSpace O(n)Each shuffle walks the array once doing one swap per position; the extra O(n) space is the saved copy of the original array.

What Trips People Up in Real Interviews

1

Clarify that shuffle must produce each permutation with equal probability

2

Explain Fisher-Yates gives O(n) time with uniform distribution

3

Discuss why copying the array for reset is necessary

4

Mention the importance of using inclusive random range correctly

5

Consider thread-safety concerns if asked about concurrent access

Solution Code

O(n) per shuffle or reset time
import random

class Solution:
    def __init__(self, nums):
        self.nums = nums
        self.original = nums[:]
    def reset(self):
        self.nums = self.original[:]
        return self.nums
    def shuffle(self):
        arr = self.nums[:]
        for i in range(len(arr) - 1, 0, -1):
            j = random.randint(0, i)
            arr[i], arr[j] = arr[j], arr[i]
        self.nums = arr
        return arr

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Shuffle an Array problem?

Design a class that shuffle an array of integers and returns it to its original configuration. The shuffle operation must generate all permutations with equal probability. Implement the shuffle using Fisher-Yates algorithm.

How do you solve Shuffle an Array?

The optimal approach runs in O(n) per shuffle or reset time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Shuffle an Array?

Shuffle an Array is asked at Uber. It is a medium difficulty problem.

What are common mistakes on Shuffle an Array?
  • Clarify that shuffle must produce each permutation with equal probability
  • Explain Fisher-Yates gives O(n) time with uniform distribution
  • Discuss why copying the array for reset is necessary
  • Mention the importance of using inclusive random range correctly
  • Consider thread-safety concerns if asked about concurrent access