398. Random Pick Index

// LeetCode URL: https://leetcode.com/problems/random-pick-index/
import java.util.Random;

/**
 * Reservoir Sampling
 *
 * Suppose the indexes of the target element in 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(1).. 2) pick() -> O(N)
 *
 * Space Complexity: O(1)
 *
 * N = Length of the input array.
 */
class Solution {

    int[] numsArr;
    Random rand;

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

    public int pick(int target) {
        if (numsArr == null || numsArr.length == 0) {
            return -1;
        }

        int count = 0;
        int result = -1;
        for (int i = 0; i < numsArr.length; i++) {
            if (numsArr[i] == target) {
                count++;
                if (rand.nextInt(count) == 0) {
                    result = i;
                }
            }
        }

        return result;
    }
}

/**
 * Your Solution object will be instantiated and called as such: Solution obj =
 * new Solution(nums); int param_1 = obj.pick(target);
 */