We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Distinct Elements After Operations

Difficulty: Medium

Problem Description

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.

Key Insights

  • The operation allows us to adjust each element by a value within the range of [-k, k].
  • The goal is to maximize the number of distinct elements after performing the operations.
  • Sorting the array can help in determining the best way to apply the operations.
  • A greedy approach can be used to ensure that as many distinct values as possible are created.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array. Space Complexity: O(n) - for storing distinct elements.

Solution

To solve the problem, we can follow these steps:

  1. Sort the array to handle elements in order.
  2. Use a set to track distinct elements.
  3. For each element, attempt to add or subtract values within the range of [-k, k] to create the largest distinct value possible.
  4. If a value already exists in the set, attempt to adjust it further until a distinct value is found or the limits of the operation are reached.
  5. Count the total distinct values at the end.

The primary data structure used is a set to maintain distinct elements, and the algorithm uses sorting followed by a greedy approach to maximize distinct values.

Code Solutions

def maxDistinctElements(nums, k):
    nums = sorted(nums)
    distinct = set()
    
    for num in nums:
        # Try to add -k to k to the current number
        for delta in range(-k, k + 1):
            adjusted_num = num + delta
            if adjusted_num not in distinct:
                distinct.add(adjusted_num)
                break
                
    return len(distinct)

# Example Usage
print(maxDistinctElements([1, 2, 2, 3, 3, 4], 2))  # Output: 6
print(maxDistinctElements([4, 4, 4, 4], 1))         # Output: 3
← Back to All Questions