Random Pick Index - Practice Coding Problems

Random Pick Index - Problem

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 indices, then each index should have an equal probability of returning.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3,3,3], target = 3

› Output: One of [2,3,4]

💡 Note: Target 3 appears at indices 2, 3, 4. Each index should be returned with equal 1/3 probability

Example 2 — Single Occurrence

$ Input: nums = [1,2,3,3,3], target = 1

› Output: 0

💡 Note: Target 1 appears only at index 0, so we must return 0

Example 3 — Multiple Duplicates

$ Input: nums = [1,1,1,1,1], target = 1

› Output: One of [0,1,2,3,4]

💡 Note: Target 1 appears at all indices. Each index should be returned with equal 1/5 probability

Constraints

1 ≤ nums.length ≤ 2×10⁴
-2³¹ ≤ nums[i] ≤ 2³¹ - 1
target is guaranteed to exist in nums

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,3,3,3] with target=3

Find Matches

Locate all indices where nums[i] == target

Random Pick

Select one index with equal probability

Key Takeaway

🎯 Key Insight: Multiple approaches exist, from simple linear scan to elegant reservoir sampling, each with different time-space tradeoffs

Asked in

f Facebook 35 G Google 28 a Amazon 22 M Microsoft 18

The key insight is ensuring equal probability when multiple indices contain the target value. The hash map approach offers O(1) pick time after preprocessing, while reservoir sampling provides O(1) space with mathematical elegance. Time: O(n) for single query, Space: O(1) to O(n) depending on approach.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Preprocessing	O(1)	O(n)	Store all indices for each value in a hash map, then randomly pick from stored list
Linear Scan Every Time	O(n)	O(k)	Scan array to find all target indices, then randomly select one
Reservoir Sampling	O(n)	O(1)	Use reservoir sampling algorithm to pick random index with equal probability in one pass

Hash Map Preprocessing — Algorithm Steps

Build hash map: value → list of indices
For pick: access target's index list
Generate random index to select from the list

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Map

Create value → indices mapping during initialization

Direct Access

Look up target value to get all its indices

Random Select

Pick random index from the pre-stored list

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define MAX_NUMS 1000
#define MAX_VAL 1000

int indexMap[MAX_VAL * 2 + 1][MAX_NUMS];
int counts[MAX_VAL * 2 + 1];

int solution(int* nums, int numsSize, int target) {
    memset(counts, 0, sizeof(counts));
    int offset = MAX_VAL;
    
    for (int i = 0; i < numsSize; i++) {
        int idx = nums[i] + offset;
        indexMap[idx][counts[idx]++] = i;
    }
    
    int targetIdx = target + offset;
    srand(time(NULL));
    return indexMap[targetIdx][rand() % counts[targetIdx]];
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[MAX_NUMS];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int target;
    scanf("%d", &target);
    
    printf("%d\n", solution(nums, numsSize, target));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Pick operation is O(1) average time after O(n) preprocessing

✓ Linear Growth

Space Complexity

O(n)

Hash map stores all n indices distributed across different keys

⚡ Linearithmic Space

64.5K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Preprocessing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler