// Proof: Suppose this algorithm works, i.e. for each position j (starting from 0), the probability
// of any number in the range[0,j] to be at position j is 1/(1+j).
// Let's look at int i = random.nextInt(j + 1):
// 1. If i == j, nums[j] does not need to change its position, which has probability 1/(1+j).
// 2. if i != j, nums[j] needs to be swapped with nums[i]. The probability of any number x in the
// range [0, j-1] to be at position j = nums[j] changes its position =>
// x is at position i = (1-1/(1+j)) * (1/j) = 1/(1+j)
// Each number has equal probability to be at any position.
public class Solution {
  private Random random;
  private int[] original;

  public Solution(int[] nums) {
    this.random = new Random();
    this.original = nums;
  }

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

  /** Returns a random shuffling of the array. */
  public int[] shuffle() {
    int[] arr = new int[this.original.length];
    System.arraycopy(this.original, 0, arr, 0, this.original.length);
    for (int i = arr.length - 1; i > 0; i--) {
      int j = this.random.nextInt(i + 1);
      int t = arr[i];
      arr[i] = arr[j];
      arr[j] = t;
    }
    return arr;
  }
}

/**
 * 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();
 */

@@ -1,586 +1,987 @@
 // 
-Proof: Suppose this algorithm works, i.e. for each position j (start
+The probability that ith element (including the last one) goes to last position is 1/n, because%0A// we randomly pick an element 
 in
-g
  f
-rom 0), the probability%0A// of any number in the range%5B0,j%5D to be at position j is 1/(1+j).%0A// Let's look at int i = random.nextInt(j + 1):%0A// 1. If i == j, nums%5Bj%5D does not need to change its position, which has probability 1/(1+j).%0A// 2. if i != j, nums%5Bj%5D needs to be swapped with nums%5Bi%5D. The probability of any number x in the%0A// range %5B0, j-1%5D to be at position j = nums%5Bj%5D changes
+irst iteration.%0A%0A// The probability that ith element goes to second last position can be proved to be 1/n by dividing%0A// it in two cases.%0A// Case 1: i = n-1 (index of last element):%0A//    The probability of last element going to second last position is = (probability that last%0A//    element doesn't stay at its original position) x (probability that the index picked in%0A//    previous step is picked again so that the last element is swapped)%0A//    So the probability = ((n-1)/n) x (1/(n-1)) = 1/n%0A// Case 2: 0 %3C i %3C n-1 (index of non-last):%0A//    The probability of ith element going to second position = (probability that ith element
  i
-t
 s 
-position =%3E%0A// x is at position i = (1-1/(1+j)) *
+not%0A//    picked in previous iteration) x (probability that ith element is picked in this iteration)%0A//    So the probability = ((n-1)/n) x
  (1/
-j
+(n-1)
 ) = 1/
-(1+j)%0A// Each number has equal probability to be at any
+n%0A// We can easily generalize above proof for any other
  pos

update proof