Intuition
We can cut down the time and space complexities of shuffle with a bit of
cleverness - namely, by swapping elements around within the array itself, we
can avoid the linear space cost of the auxiliary array and the linear time cost
of list modification.
Algorithm
- Generate a random integer between the current index and the last index of the array.
- Swap the elements at the current index and the chosen index.
import java.util.Arrays;
import java.util.Random;
public class ShuffleAnArray {
private int[] nums;
private int[] clone;
private Random rand;
public ShuffleAnArray(int[] nums) {
this.nums = nums;
this.clone = nums.clone();
this.rand = new Random();
}
private void swap(int[] clone, int i, int j) {
int temp = clone[i];
clone[i] = clone[j];
clone[j] = temp;
}
private int getRandom(int min, int max) {
return rand.nextInt(max - min) + min;
}
/** Resets the array to its original
configuration and return it. */
public int[] reset() {
return nums;
}
/** Returns a random shuffling of the
array. */
public int[] shuffle() {
for (int i = 0; i < clone.length; i++) {
int idx = getRandom(i, clone.length);
swap(clone, i, idx);
}
return clone;
}
public static void main(String[] args) {
int[] array = { 1, 2, 3
};
ShuffleAnArray shuffleAnArray = new ShuffleAnArray(array);
System.out.println("Array value before suffle "+Arrays.toString(shuffleAnArray.reset()));
System.out.println("Array value before suffle "+Arrays.toString(shuffleAnArray.shuffle()));
System.out.println("Array value after suffle "+Arrays.toString(shuffleAnArray.reset()));
}
}
Complexity
Analysis
Time complexity: O(n)
The Fisher-Yates algorithm runs in linear time, as generating a random
index and swapping two values can be done in constant time.
Space complexity: O(n)
Although we managed to avoid using linear space on the auxiliary array
from the brute force approach, we still need it for reset, so we're stuck with
linear space complexity.
