algoadvance

Leetcode 384. Shuffle an Array

Problem Statement

You are given an integer array nums. You need to implement two functions:

• shuffle(): Returns a random shuffling of the array.
• reset(): Resets the array to its original configuration and returns it.

Implement the class Solution:

• 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:

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.
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].

Clarifying Questions

1. Is there any constraint on the length of the array?
   • No specific constraints mentioned, assume reasonable length as per usual competitive programming standards.
2. Do we need to consider duplicates in the array?
   • The prompt does not prevent duplicates, so handle it appropriately.

Strategy

1. Initialization:
   • Store the original array in a variable for the reset() method to use.
   • Use an array copy to ensure the original array is not modified during shuffling.
2. Reset Function:
   • Return the original array.
3. Shuffle Function:
   • Use the Fisher-Yates shuffle algorithm to ensure a uniform random shuffle.

The Fisher-Yates algorithm ensures O(n) time complexity for shuffling in a straightforward manner.

Code

Here is the implementation in Java:

import java.util.Random;

public class Solution {
    private int[] original;
    private int[] array;
    private Random rand;
    
    public Solution(int[] nums) {
        original = nums.clone();
        array = nums.clone();
        rand = new Random();
    }

    public int[] reset() {
        array = original.clone();
        return array;
    }

    public int[] shuffle() {
        for (int i = array.length - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            swap(array, i, j);
        }
        return array;
    }
    
    private void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

Time Complexity

• Initialization: O(n) because of the cloning process.
• Reset: O(n) for cloning the original array.
• Shuffle: O(n) for the Fisher-Yates shuffle, which involves a single pass through the array.

The space complexity is O(n) due to storage of the additional copies of the array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?