Advertisement
Home Data Structure Arrays Pick N Random Elements from an Array

Pick N Random Elements from an Array

1
Advertisement

Title: Pick N Random Elements from an Array

Understanding the Problem

In this guide, you will learn how to pick n random elements from a Java array without ever picking the same element twice. This comes up constantly in interviews and in real applications such as sampling test data, choosing random winners from a list of entries, or shuffling a subset of items for an A/B test.

You will build a reusable method using a partial Fisher-Yates shuffle, trace it step by step on a six-element array, and walk through the edge cases and follow-up questions an interviewer is likely to ask.

Approach to Pick N Random Elements

The cleanest way to sample without repeats is to shuffle only as much of the array as you need, swapping each newly chosen element into the front of the array one position at a time.

  1. Validate the inputs: throw if array is null, or if n is negative or greater than array.length.
  2. Clone the input array with Arrays.copyOf so the caller’s original array is never mutated.
  3. Create or accept a Random instance that will drive every random choice.
  4. Loop the index i from 0 up to (but not including) n.
  5. On each iteration, pick a random index j in the unprocessed range [i, result.length - 1] using i + random.nextInt(result.length - i).
  6. Swap result[i] and result[j] so the randomly chosen element moves into the already-picked region at the front of the array.
  7. After the loop finishes, the first n elements of result are a uniformly random sample without repeats.
  8. Return a copy of just that front slice with Arrays.copyOfRange(result, 0, n).

This beats a naive retry loop that keeps picking random indices and checking a Set for collisions, because the swap approach never wastes a draw on an element that was already picked.

Java Program

Here is a complete, compilable program that implements the approach above and prints a random sample of three elements.

Java
import java.util.Arrays;
import java.util.Random;

public class RandomElementsPicker {

    public static int[] pickNRandomElements(int[] array, int n, Random random) {
        if (array == null) {
            throw new IllegalArgumentException("array must not be null");
        }
        if (n < 0 || n > array.length) {
            throw new IllegalArgumentException("n must be between 0 and array.length");
        }

        int[] result = Arrays.copyOf(array, array.length);

        for (int i = 0; i < n; i++) {
            int j = i + random.nextInt(result.length - i);
            int temp = result[i];
            result[i] = result[j];
            result[j] = temp;
        }

        return Arrays.copyOfRange(result, 0, n);
    }

    public static void main(String[] args) {
        int[] numbers = {10, 20, 30, 40, 50, 60, 70, 80};
        int n = 3;

        int[] picked = pickNRandomElements(numbers, n, new Random());

        System.out.print("Picked elements: ");
        System.out.println(Arrays.toString(picked));
    }
}

Explanation of the Program

Every line in pickNRandomElements exists to guarantee one property: n distinct elements, chosen uniformly at random, with the caller’s array left untouched.

  • Arrays.copyOf(array, array.length) creates a working copy so swapping indices never touches the array the caller passed in.
  • The loop only runs n times, not array.length times, because once the first n slots hold randomly chosen elements the job is done.
  • random.nextInt(result.length - i) shrinks its upper bound by one every iteration, which keeps the pool of still-eligible elements exactly equal to the elements not yet picked.
  • The swap at result[i] and result[j] is what prevents duplicates, because once an element lands in the front region it can never be selected again.
  • Arrays.copyOfRange(result, 0, n) trims the output down to exactly the n requested elements, leaving the fully shuffled tail discarded.

Step-by-Step Trace

Trace the swap loop on [5, 12, 9, 21, 3, 17] with n = 3, assuming random.nextInt returns 4, 3, and 0 on the three calls. The target output is the first three elements of the array after the loop.

Iterationij (random index)result[i] beforeresult[j] beforearray after swap
10453[3, 12, 9, 21, 5, 17]
214125[3, 5, 9, 21, 12, 17]
32299[3, 5, 9, 21, 12, 17] (no change, i = j)

At the end of iteration i, result[0..i] holds a uniformly random selection of i + 1 elements from the original array, and the remaining positions still contain the rest of the array in some order. The final sample here is [3, 5, 9].

Examples

Example 1: Picking 2 Random Names from a String Array

Because pickNRandomElements works on int[], you can sample index positions and use them to pull matching entries out of any other array, including an array of objects.

Java
String[] names = {"Alice", "Bob", "Charlotte", "David", "Emma"};
int n = 2;

int[] indices = pickNRandomElements(new int[]{0, 1, 2, 3, 4}, n, new Random());
String[] result = new String[n];
for (int i = 0; i < n; i++) {
    result[i] = names[indices[i]];
}

System.out.println(Arrays.toString(result));
// Sample output: [Charlotte, Emma]

Example 2: Picking All Elements (n equals array.length)

When n equals array.length, the loop processes every index, and the method degenerates into a full Fisher-Yates shuffle of the whole array.

Java
int[] deck = {1, 2, 3, 4, 5, 6, 7};
int[] shuffled = pickNRandomElements(deck, deck.length, new Random());

System.out.println(Arrays.toString(shuffled));
// Sample output: [5, 2, 7, 1, 6, 3, 4] (order changes on every run)

Example 3: Reproducible Output with a Seeded Random

Injecting a Random instance instead of creating one inside the method makes the sample reproducible, which is essential for unit tests.

Java
int[] values = {100, 200, 300, 400, 500};

int[] firstRun = pickNRandomElements(values, 3, new Random(42));
int[] secondRun = pickNRandomElements(values, 3, new Random(42));

System.out.println(Arrays.toString(firstRun));
System.out.println(Arrays.toString(secondRun));
// Both lines print the same three elements in the same order

Common Mistakes to Avoid

These are the mistakes that come up most often when developers first implement sampling without replacement.

  • Sampling with a retry loop and a HashSet of used indices – picking a random index, checking a Set for a collision, and retrying on a hit works, but the retry rate climbs sharply as n approaches array.length. The swap-based approach above shrinks the eligible pool every iteration instead, so it never retries.
  • Forgetting to clone the array before swapping – running the swap loop directly on the caller’s array silently reorders their data, which shows up as a confusing bug much later when the same array is printed again. Clone with Arrays.copyOf before the first swap.
  • Calling random.nextInt(array.length) instead of random.nextInt(array.length – i) – keeping the upper bound fixed lets an already-picked element be chosen again, which produces duplicate values in the result. The bound must shrink by one on every iteration.
  • Skipping the bounds check on n – passing an n larger than array.length throws an ArrayIndexOutOfBoundsException deep inside the loop instead of a clear error at the top of the method. Validate n first and throw IllegalArgumentException.

Edge Cases to Test

Walk through these inputs before calling the implementation finished, since an interviewer will usually ask about several of them unprompted.

  • Empty array
  • n equal to 0
  • n equal to array.length
  • n greater than array.length
  • Single-element array
  • Array containing duplicate values
  • Negative n
  • Null array reference

Additional Considerations

Time complexity is O(n), since the loop body executes exactly n times no matter how large array.length is. That is a meaningful improvement over fully shuffling the whole array, which costs O(array.length) work for elements you may not even keep.

Space complexity is O(array.length) for the cloned working array plus O(n) for the returned slice. If the input array is enormous and you cannot afford the clone, see the interview follow-up on sampling without copying.

java.util.Random is thread-safe but can become a contention point under heavy concurrent use, since every call synchronizes on shared seed state. Prefer ThreadLocalRandom.current() when this method runs on multiple threads at once.

Interview Follow-up Questions

A base implementation is only the opening move; these are the variations an interviewer is likely to push toward next.

  • What if the input arrives as a stream of unknown length? – use reservoir sampling (Algorithm R): keep the first n elements, then for each new element at index k replace a random existing slot with probability n/k.
  • What if the array is too large to clone or mutate? – sample n distinct indices directly with a small HashSet instead of a full copy, trading a little retry overhead for avoiding the O(array.length) copy.
  • What if you need the n elements with replacement instead of without? – drop the swapping entirely and call random.nextInt(array.length) independently n times, since duplicates become allowed and expected.
  • What if the results must be reproducible across test runs? – inject a seeded Random instance, as shown in Example 3, instead of constructing new Random() inside the method.
  • What if array.length is in the billions and the data does not fit in memory? – partition the data across machines, run reservoir sampling independently on each partition, then merge the partition samples with weighted reservoir sampling to get a uniform sample of the whole dataset.

Conclusion

Picking n random elements from an array comes down to a partial Fisher-Yates shuffle: shrink the eligible pool by one index on every iteration and swap the chosen element into the front of the array. The technique runs in O(n) time, never repeats an element, and needs only a Random instance and a cloned array to stay safe for the caller.

Try adapting pickNRandomElements to generic arrays with a type parameter, or swap in ThreadLocalRandom for a multithreaded service. You can learn more about array based problems like this one in the Arrays category on dailyjavaconcept.com.