Shuffle An Array - Leetcode Solution

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:

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]

Solution:

Approach 1:

The simplest approach would be to shuffle the array randomly every time the shuffle method is called. This can be achieved by using the Fisher-Yates shuffle algorithm, which works in O(n) time complexity.

Algorithm:

1. Create an array called shuffledArray of length n, where n is the length of the input array nums.
2. Copy the contents of nums into shuffledArray.
3. For i from n - 1 to 1: a. Generate a random integer j between 0 and i inclusive. b. Swap the values in shuffledArray at indices i and j.
4. Return shuffledArray when shuffle method is called. Return copied array nums when reset method is called.

Time Complexity:

The time complexity of this approach is O(n) for every shuffle, as we are iterating over the array once for each shuffle. The time complexity of the reset method is O(n) as it involves copying the original array once.

Space Complexity:

The space complexity of this approach is O(n) as we are using an extra array to store the shuffled input array.

Code:

public class Solution { private int[] originalArray; private int[] shuffledArray; private Random random;

public Solution(int[] nums) {
    originalArray = nums;
    shuffledArray = Arrays.copyOf(nums, nums.length);
    random = new Random();
}

/** Resets the array to its original configuration and return it. */
public int[] reset() {
    shuffledArray = Arrays.copyOf(originalArray, originalArray.length);
    return shuffledArray;
}

/** Returns a random shuffling of the array. */
public int[] shuffle() {
    for (int i = shuffledArray.length - 1; i >= 1; i--) {
        int j = random.nextInt(i + 1);
        swap(shuffledArray, i, j);
    }
    return shuffledArray;
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

}

Approach 2:

A more space-efficient approach is to not use an extra array to store the shuffled input array. Instead, we can modify the input array in place and shuffle it randomly using the Fisher-Yates shuffle algorithm.

Algorithm:

1. For i from n - 1 to 1: a. Generate a random integer j between 0 and i inclusive. b. Swap the values in nums at indices i and j.
2. Return nums when shuffle method is called. Return copied array nums when reset method is called.

Time Complexity:

The time complexity of this approach is O(n) for every shuffle, as we are iterating over the array once for each shuffle. The time complexity of the reset method is O(n) as it involves copying the original array once.

Space Complexity:

The space complexity of this approach is O(1) as we are modifying the input array in place. No extra space is used.

Code:

public class Solution { private int[] originalArray; private Random random;

public Solution(int[] nums) {
    originalArray = nums;
    random = new Random();
}

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

/** Returns a random shuffling of the array. */
public int[] shuffle() {
    int[] shuffledArray = Arrays.copyOf(originalArray, originalArray.length);

    for (int i = shuffledArray.length - 1; i >= 1; i--) {
        int j = random.nextInt(i + 1);
        swap(shuffledArray, i, j);
    }
    return shuffledArray;
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

}

1