Maximum number of distinct elements after operations

Array Greedy Sorting

52.2% acceptance

Feb 24, 2026

559

You are given an integer array nums and an integer k. You are allowed to perform the following operation on each element of the array at most once: Add an integer in the range [-k, k] to the element. Return the maximum possible number of distinct elements in nums after performing the operations.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_distinct_elements(mut nums: Vec<i32>, k: i32) -> i32 {
    nums.sort_unstable();
    let mut ans = 0;
    let mut prev = i64::MIN;
    for &x in &nums {
      // We want to assign a value in [x-k, x+k] that is > prev (to be distinct)
      let lo = (x as i64) - k as i64;
      let target = lo.max(prev + 1);
      if target <= (x as i64) + k as i64 {
        prev = target;
        ans += 1;
      }
    }
    ans
  }
}