3620. Maximum Number Of Distinct Elements After Operations¶

LeetCode Problem View on GitHub

3620. Maximum Number of Distinct Elements After Operations

Medium

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.

Example 1:

Example 2:

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 0 <= k <= 109

Solution¶

class Solution {
    public int maxDistinctElements(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        TreeSet<Integer> set = new TreeSet<>();
        for (int ele : nums) {
            int mini = ele - k, maxi = ele + k;
            if (set.size() == 0 || !set.contains(mini)) set.add(mini);
            else {
                int last = set.getLast();
                if (last + 1 <= maxi) set.add(last + 1);
                else set.add(ele);
            }
        }
        return set.size();
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here