Minimum number of operations to have distinct elements

Array Hash Table

42.0% acceptance

Feb 25, 2026

You are given an integer array nums. In one operation, you remove the first three elements of the current array. If there are fewer than three elements remaining, all remaining elements are removed. Repeat this operation until the array is empty or contains no duplicate values. Return an integer denoting the number of operations required.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(nums: Vec<i32>) -> i32 {
    // O(n): for each value track the second-to-last occurrence index.
    // We need to remove all prefixes up to past that index so the
    // remaining suffix has no duplicates.
    // min_start = max(second_last_occurrence) + 1
    // ops = ceil(min_start / 3)
    let mut last: std::collections::HashMap<i32, usize> = std::collections::HashMap::new();
    let mut min_start: usize = 0;
    for (i, &v) in nums.iter().enumerate() {
      if let Some(&prev) = last.get(&v) {
        // prev is the last seen index before i; we need start > prev
        let needed = prev + 1;
        if needed > min_start {
          min_start = needed;
        }
      }
      last.insert(v, i);
    }
    ((min_start + 2) / 3) as i32
  }
}