384. Shuffle an Array

// LeetCode URL: https://leetcode.com/problems/shuffle-an-array/
import java.util.Random;

/**
 * Fisher-Yates Algorithm
 *
 * Refer: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
 *
 * In Shuffle function, probability of each item in array is equal (1 / N). This
 * is due to reservoir sampling with size of reservoir as 1.
 *
 * Suppose the indexes of the array are from 1 to N. You have already placed i-1
 * elements. Now you are trying to place ith element. The probability to place
 * it at an index between 1 & i is 1/i. Now you do not want to replace ith
 * number by any future numbers.. Thus, the final probability for ith element =
 * 1/i * (1 - 1/(i+1)) * (1 - 1/(i+2)) * .. * (1 - 1/N) = 1 / N.
 *
 * Time Complexity: 1) Solution() -> O(N).. 2) reset() -> O(N).. 3) shuffle() ->
 * O(N)
 *
 * Space Complexity: O(N). This is required for clone of original array.
 *
 * N = length of the input array.
 */
class Solution {

    int[] origArr;
    int[] numsArr;
    Random rand;

    public Solution(int[] nums) {
        if (nums == null) {
            return;
        }
        numsArr = nums;
        origArr = nums.clone();
        rand = new Random();
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        if (origArr == null) {
            return null;
        }
        numsArr = origArr.clone();
        return numsArr;
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        if (numsArr == null || numsArr.length <= 1) {
            return numsArr;
        }

        for (int i = 1; i < numsArr.length; i++) {
            int idx = rand.nextInt(i + 1);
            if (idx != i) {
                int temp = numsArr[i];
                numsArr[i] = numsArr[idx];
                numsArr[idx] = temp;
            }
        }

        return numsArr;
    }
}

/**
 * Your Solution object will be instantiated and called as such: Solution obj =
 * new Solution(nums); int[] param_1 = obj.reset(); int[] param_2 =
 * obj.shuffle();
 */