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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Distinct Elements After Operations

Number: 3620

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

You are given an integer array nums and an integer k. Each element in nums can be adjusted at most once by adding any integer between -k and k (inclusive) to it. The goal is to choose adjustments to maximize the number of distinct elements in the resulting array.

Key Insights

  • Each element x in nums has a range [x - k, x + k] to which it can be adjusted.
  • The problem can be transformed into an interval assignment task where for each element you must pick one integer from its allowed interval.
  • A greedy strategy is effective: sort the intervals by their ending value and assign the smallest possible integer that is greater than the number assigned previously.
  • The greedy approach is similar to interval scheduling, ensuring that we leave room to assign distinct values for subsequent intervals.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the intervals. Space Complexity: O(n) for storing interval ranges (or O(1) additional space if done in-place).

Solution

We first convert each element nums[i] into an interval [nums[i] - k, nums[i] + k]. Once we have these intervals, we sort them by the end (right boundary). Then, we iterate over each interval and greedily choose the smallest number that is larger than the last assigned number while still lying within the current interval. If such a number exists, we assign it and update our last assigned number; otherwise, we skip that interval. This process ensures that we maximize the number of distinct assignments.

The main data structures used are:

  • An array of intervals.
  • A variable to track the last assigned distinct value.

The algorithmic approach is greedy, with the key trick being the sort by interval ending, which guarantees that when we assign a value for the current interval, we leave as much room as possible for future intervals.

Code Solutions

# Python solution with line-by-line comments

def maxDistinctnums(nums, k):
    # Create list of intervals for each number in nums
    intervals = [(num - k, num + k) for num in nums]
    # Sort the intervals based on the right endpoint (end value)
    intervals.sort(key=lambda interval: interval[1])
    
    # Initialize the last assigned number to a very small value
    last_assigned = -10**18  # Arbitrary very small number
    distinct_count = 0
    
    # Iterate over each interval
    for start, end in intervals:
        # Determine the candidate assignment: must be greater than last_assigned
        candidate = max(last_assigned + 1, start)
        # If candidate is within the current interval, assign it
        if candidate <= end:
            distinct_count += 1
            last_assigned = candidate  # update last assigned
    return distinct_count

# Example usage:
print(maxDistinctnums([1, 2, 2, 3, 3, 4], 2))  # Expected output: 6
print(maxDistinctnums([4, 4, 4, 4], 1))          # Expected output: 3
← Back to All Questions