3397. Maximum Number of Distinct Elements After Operations LeetCode Solution

In this guide, you will get 3397. Maximum Number of Distinct Elements After Operations LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Distinct Elements After Operations problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Maximum Number of Distinct Elements After Operations solution in C++
4. Maximum Number of Distinct Elements After Operations solution in Java
5. Maximum Number of Distinct Elements After Operations solution in Python
6. Additional Resources

Problem Statement of Maximum Number of Distinct Elements After Operations

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:

Input: nums = [1,2,2,3,3,4], k = 2
Output: 6
Explanation:
nums changes to [-1, 0, 1, 2, 3, 4] after performing operations on the first four elements.

Example 2:

Input: nums = [4,4,4,4], k = 1
Output: 3
Explanation:
By adding -1 to nums[0] and 1 to nums[1], nums changes to [3, 5, 4, 4].

Constraints:

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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

3397. Maximum Number of Distinct Elements After Operations LeetCode Solution in C++

class Solution {
 public:
  int maxDistinctElements(vector<int>& nums, int k) {
    int ans = 0;
    int occupied = INT_MIN;

    ranges::sort(nums);

    for (const int num : nums)
      if (occupied < num + k) {
        occupied = max(occupied + 1, num - k);
        ++ans;
      }

    return ans;
  }
};
/* code provided by PROGIEZ */

3397. Maximum Number of Distinct Elements After Operations LeetCode Solution in Java

class Solution {
  public int maxDistinctElements(int[] nums, int k) {
    int ans = 0;
    int occupied = Integer.MIN_VALUE;

    Arrays.sort(nums);

    for (final int num : nums)
      if (occupied < num + k) {
        occupied = Math.max(occupied + 1, num - k);
        ++ans;
      }

    return ans;
  }
}
// code provided by PROGIEZ

3397. Maximum Number of Distinct Elements After Operations LeetCode Solution in Python

class Solution:
  def maxDistinctElements(self, nums: list[int], k: int) -> int:
    ans = 0
    occupied = -math.inf

    for num in sorted(nums):
      if occupied < num + k:
        occupied = max(occupied + 1, num - k)
        ans += 1

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.