Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Each value may become any integer in [value - k, value + k]. After sorting, these intervals have nondecreasing left and right endpoints. Assign each interval the smallest unused value above the previous assignment, leaving as much room as possible for later intervals.

Approach

Sort nums and track the last distinct value assigned, initially negative infinity. For each value, propose max(last + 1, value - k). If it is at most value + k, accept it, increment the distinct count, and update last. Otherwise skip this value because it cannot extend the distinct assignment sequence.

Choosing a smaller feasible assignment cannot make a later interval harder to place. An optimal matching between sorted intervals and distinct chosen integers can also be ordered increasingly: crossed assignments can be swapped because both interval endpoints are ordered. These facts justify the greedy scan. Skipped elements may receive duplicate values without reducing the number of distinct accepted assignments.

class Solution:
    def maxDistinctElements(self, nums: List[int], k: int) -> int:
        nums.sort()
        res = 0
        low = float('-inf')

        for x in nums:
            curr = max(low + 1, x - k)
            if curr <= x + k:
                res += 1
                low = curr

        return res

Complexity analysis

Let n = nums.length. Time: O(n log n). Auxiliary space: O(n) in the worst case for built-in sorting.