Smallest missing non negative integer after operations

Array Hash Table Math Greedy

55.9% acceptance

Feb 25, 2026

802

174

You are given a 0-indexed integer array nums and an integer value. In one operation, you can add or subtract value from any element of nums. For example, if nums = [1,2,3] and value = 2, you can choose to subtract value from nums[0] to make nums = [-1,2,3]. The MEX (minimum excluded) of an array is the smallest missing non-negative integer in it. For example, the MEX of [-1,2,3] is 0 while the MEX of [1,0,3] is 2. Return the maximum MEX of nums after applying the mentioned operation any number of times.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_smallest_integer(nums: Vec<i32>, value: i32) -> i32 {
    // Numbers can be shifted by multiples of value, so group by remainder mod value.
    // For each target non-negative integer t = q*value + r, we need at least (q+1) numbers
    // in the remainder class r. Find the smallest t where this is not satisfied.
    use std::collections::HashMap;
    let mut counts: HashMap<i32, i32> = HashMap::new();
    for &x in &nums {
      let r = ((x % value) + value) % value;
      *counts.entry(r).or_insert(0) += 1;
    }
    let mut mex = 0i32;
    loop {
      let r = mex % value;
      let need = mex / value + 1;
      if *counts.get(&r).unwrap_or(&0) >= need {
        mex += 1;
      } else {
        break;
      }
    }
    mex
  }
}