Minimum number of operations to make elements in array distinct

Array Hash Table

71.3% acceptance

Feb 24, 2026

563

You are given an integer array nums. You need to ensure that the elements in the array are distinct. To achieve this, you can perform the following operation any number of times: Remove 3 elements from the beginning of the array. If the array has fewer than 3 elements, remove all remaining elements. Note that an empty array is considered to have distinct elements. Return the minimum number of operations needed to make the elements in the array distinct.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_operations(nums: Vec<i32>) -> i32 {
    // Binary search or linear scan: find the minimum prefix to remove (in multiples of 3)
    // Try operations = 0, 1, 2, ... and check if remaining suffix has distinct elements
    let n = nums.len();
    for ops in 0..=((n + 2) / 3) as i32 {
      let start = (ops * 3) as usize;
      let suffix = &nums[start.min(n)..];
      let mut seen = std::collections::HashSet::new();
      let distinct = suffix.iter().all(|x| seen.insert(x));
      if distinct {
        return ops;
      }
    }
    ((n + 2) / 3) as i32
  }
}