Problem

Given an array of size n, write a method to randomly select a set of m distinct elements from it, such that each subset of size m is equally likely to be chosen.

Examples

Example 1

1
2
3

Input: arr = [1, 2, 3, 4, 5], m = 3
Output: [2, 5, 1] (or any random subset of 3 elements)
Explanation: Each possible subset of 3 elements is equally likely.

Example 2

1
2
3

Input: arr = [10, 20, 30, 40], m = 2
Output: [30, 10] (or any random subset of 2 elements)
Explanation: Each possible subset of 2 elements is equally likely.
Similar Problems

Solution

Method 1 – Fisher-Yates Shuffle (Partial Shuffle)

Intuition

To select m elements uniformly at random from an array of size n, we can use a partial Fisher-Yates shuffle. By shuffling only the first m positions, we guarantee that every subset of size m is equally likely.

Approach

  1. Make a copy of the input array to avoid modifying the original.
  2. For each position i from 0 to m-1:
    • Pick a random index j in the range [i, n-1].
    • Swap the elements at positions i and j.
  3. After m swaps, the first m elements of the array are a random subset.
  4. Return the first m elements.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
  std::vector<int> randomSubset(std::vector<int> arr, int m) {
    int n = arr.size();
    for (int i = 0; i < m; ++i) {
      int j = i + rand() % (n - i);
      std::swap(arr[i], arr[j]);
    }
    return std::vector<int>(arr.begin(), arr.begin() + m);
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func randomSubset(arr []int, m int) []int {
  n := len(arr)
  res := make([]int, n)
  copy(res, arr)
  for i := 0; i < m; i++ {
    j := i + rand.Intn(n-i)
    res[i], res[j] = res[j], res[i]
  }
  return res[:m]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
  public int[] randomSubset(int[] arr, int m) {
    int n = arr.length;
    int[] res = arr.clone();
    Random rand = new Random();
    for (int i = 0; i < m; i++) {
      int j = i + rand.nextInt(n - i);
      int temp = res[i];
      res[i] = res[j];
      res[j] = temp;
    }
    return Arrays.copyOf(res, m);
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
  fun randomSubset(arr: IntArray, m: Int): IntArray {
    val n = arr.size
    val res = arr.copyOf()
    for (i in 0 until m) {
      val j = i + (0 until (n - i)).random()
      val tmp = res[i]
      res[i] = res[j]
      res[j] = tmp
    }
    return res.sliceArray(0 until m)
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from typing import List
import random

class Solution:
  def random_subset(self, arr: List[int], m: int) -> List[int]:
    n = len(arr)
    res = arr[:]
    for i in range(m):
      j = random.randint(i, n - 1)
      res[i], res[j] = res[j], res[i]
    return res[:m]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
  pub fn random_subset(arr: &mut [i32], m: usize) -> Vec<i32> {
    let n = arr.len();
    let mut res = arr.to_vec();
    let mut rng = rand::thread_rng();
    for i in 0..m {
      let j = i + rng.gen_range(0..(n - i));
      res.swap(i, j);
    }
    res[..m].to_vec()
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
  randomSubset(arr: number[], m: number): number[] {
    const n = arr.length;
    const res = arr.slice();
    for (let i = 0; i < m; i++) {
      const j = i + Math.floor(Math.random() * (n - i));
      [res[i], res[j]] = [res[j], res[i]];
    }
    return res.slice(0, m);
  }
}

Complexity

  • ⏰ Time complexity: O(m) — We perform m swaps, each in constant time.
  • 🧺 Space complexity: O(n) — We copy the array to avoid modifying the original.