398. Random Pick Index LeetCode Solution

In this guide, you will get 398. Random Pick Index LeetCode Solution with the best time and space complexity. The solution to Random Pick Index problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Random Pick Index solution in C++
  4. Random Pick Index solution in Java
  5. Random Pick Index solution in Python
  6. Additional Resources
398. Random Pick IndexLeetCode Solution image

Problem Statement of Random Pick Index

Given an integer array nums with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.
Implement the Solution class:

Solution(int[] nums) Initializes the object with the array nums.
int pick(int target) Picks a random index i from nums where nums[i] == target. If there are multiple valid i’s, then each index should have an equal probability of returning.

Example 1:

Input
[“Solution”, “pick”, “pick”, “pick”]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]

Explanation
Solution solution = new Solution([1, 2, 3, 3, 3]);
solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(1); // It should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.

See also  151. Reverse Words in a String LeetCode Solution

Constraints:

1 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 – 1
target is an integer from nums.
At most 104 calls will be made to pick.

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

398. Random Pick Index LeetCode Solution in C++

class Solution {
 public:
  Solution(vector<int>& nums) : nums(std::move(nums)) {}

  int pick(int target) {
    int ans = -1;
    int range = 0;

    for (int i = 0; i < nums.size(); ++i)
      if (nums[i] == target && rand() % ++range == 0)
        ans = i;

    return ans;
  }

 private:
  vector<int> nums;
};
/* code provided by PROGIEZ */

398. Random Pick Index LeetCode Solution in Java

class Solution {
  public Solution(int[] nums) {
    this.nums = nums;
  }

  public int pick(int target) {
    int ans = -1;
    int range = 0;

    for (int i = 0; i < nums.length; ++i)
      if (nums[i] == target && rand.nextInt(++range) == 0)
        ans = i;

    return ans;
  }

  private int[] nums;
  private Random rand = new Random();
}
// code provided by PROGIEZ

398. Random Pick Index LeetCode Solution in Python

class Solution:
  def __init__(self, nums: list[int]):
    self.nums = nums

  def pick(self, target: int) -> int:
    ans = -1
    rng = 0
    for i, num in enumerate(self.nums):
      if num == target:
        rng += 1
        if random.randint(0, rng - 1) == 0:
          ans = i
    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: