LeetCode Entry

3397. Maximum Number of Distinct Elements After Operations

18.10.2025 medium 2025 kotlin rust

Distincts count after adding -k..k to each

3397. Maximum Number of Distinct Elements After Operations medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1146

Problem TLDR

Distincts count after adding -k..k to each #medium

Intuition

Sort. There is a window we can take from duplicates: -k, -k+1, …, k-1, k. Slide from the left, greedily apply lowest possible change to the number. Update max of used values.

Approach

• don’t stop when current value is out of range, the next can be bigger

Complexity

• Time complexity: \(O(nlog(n))\)

• Space complexity: \(O(1)\)

Code

// 515ms
    fun maxDistinctElements(n: IntArray, k: Int): Int {
        var m = Int.MIN_VALUE; n.sort()
        return n.count { val r = m < it + k; if (m < it+k) m = max(m+1,it-k); r }
    }

// 20ms
    pub fn max_distinct_elements(n: Vec<i32>, k: i32) -> i32 {
        let mut m = i32::MIN;
        n.iter().sorted().filter(|&x| { let r = m < x+k; if (r) { m = (m+1).max(x-k)}; r }).count() as _
    }