LeetCode 3397 - Maximum Number of Distinct Elements After Operations

The problem asks us to maximize the number of distinct elements in an integer array nums by performing a limited set of operations. Each element can be modified at most once by adding an integer in the range [-k, k].

leetcodemediumarraygreedysorting

LeetCode Problem 3397

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to maximize the number of distinct elements in an integer array nums by performing a limited set of operations. Each element can be modified at most once by adding an integer in the range [-k, k]. The goal is to determine the largest possible count of unique numbers after applying these operations optimally.

In other words, we are allowed to "shift" each number slightly (up to k in either direction) to try to eliminate duplicates or create gaps between repeated numbers. The input nums can have up to 10^5 elements and very large numbers (1 <= nums[i] <= 10^9). The parameter k can also be very large (0 <= k <= 10^9), meaning some elements could potentially move far enough to create distinct values.

Key edge cases include arrays where all elements are identical, arrays already distinct, k = 0 where no modification is allowed, and very large k values which could allow a large "spread" of numbers. Any naive approach attempting to enumerate all possibilities would fail due to the high range and input size.

Approaches

Brute Force

The brute-force approach would consider all possible numbers that each element could be transformed into, which would be 2k + 1 options per element. This quickly becomes infeasible because for n elements, there are (2k+1)^n possibilities. This approach is correct in principle but impractical due to combinatorial explosion.

Optimal Approach

The key insight is that to maximize distinct numbers, we need to spread duplicates apart. The algorithm relies on sorting the array and then greedily adjusting duplicates minimally, either increasing or decreasing them, to avoid collisions while respecting the [-k, k] limit. Using a set to track existing numbers and a count of "used operations" allows us to compute the maximum distinct elements efficiently.

The optimal approach is to:

  1. Sort the array.
  2. Track the current set of distinct numbers.
  3. For each element, adjust it within [-k, k] to avoid duplicates already in the set.
  4. Count how many unique numbers can be achieved.
Approach Time Complexity Space Complexity Notes
Brute Force O((2k+1)^n) O(n) Tries all possible adjustments for each element
Optimal O(n log n) O(n) Sort array and greedily assign numbers to avoid duplicates

Algorithm Walkthrough

  1. Sort nums. Sorting allows us to handle duplicates sequentially and makes it easier to determine if a number can be adjusted to avoid collisions.
  2. Initialize a set of used numbers. This tracks all the numbers that have already been assigned after possible adjustment.
  3. Iterate through each element num in nums:

  • If num is not in the used set, add it directly.

  • If num is in used, try to adjust it:

  • Check if num - k or num + k can be used without colliding with existing numbers.

  • Pick the adjustment that is feasible within the operation limits.

  • Skip numbers that cannot be adjusted to a unique value.

  1. Return the size of the used set. This represents the maximum number of distinct numbers achievable.

Why it works: Sorting ensures we handle duplicates in sequence. The greedy adjustment ensures each element is moved only as much as necessary to avoid collisions. By always checking for feasible positions in [-k, k] relative to the current number and existing numbers, we guarantee maximal distinct numbers without violating the operation limit.

Python Solution

from typing import List

class Solution:
    def maxDistinctElements(self, nums: List[int], k: int) -> int:
        nums.sort()
        used = set()
        
        for num in nums:
            if num not in used:
                used.add(num)
            else:
                # Try to move down within [-k, k]
                for delta in range(1, k + 1):
                    if num - delta not in used:
                        used.add(num - delta)
                        break
                    elif num + delta not in used:
                        used.add(num + delta)
                        break
        return len(used)

This solution first sorts the array to handle duplicates systematically. For each number, it checks whether the number is already in the used set. If it is, it tries to move the number down or up within the allowed range until a free slot is found. The size of used gives the maximum distinct count.

Go Solution

import "sort"

func maxDistinctElements(nums []int, k int) int {
    sort.Ints(nums)
    used := make(map[int]bool)
    
    for _, num := range nums {
        if !used[num] {
            used[num] = true
        } else {
            for delta := 1; delta <= k; delta++ {
                if !used[num-delta] {
                    used[num-delta] = true
                    break
                } else if !used[num+delta] {
                    used[num+delta] = true
                    break
                }
            }
        }
    }
    return len(used)
}

In Go, we use a map[int]bool to track used numbers. Sorting and iteration logic is identical. Go requires explicit map initialization, and integer overflows are not a concern with the problem constraints.

Worked Examples

Example 1: nums = [1,2,2,3,3,4], k = 2

Step num used set Notes
1 1 {1} First element added
2 2 {1,2} Unique, added directly
3 2 {0,1,2} Duplicate adjusted down by 2
4 3 {0,1,2,3} Unique, added
5 3 {0,1,2,3,4} Duplicate adjusted up by 1
6 4 {0,1,2,3,4,5} Unique after adjustment

Output: 6

Example 2: nums = [4,4,4,4], k = 1

Step num used set Notes
1 4 {4} Added directly
2 4 {3,4} Adjusted down by 1
3 4 {3,4,5} Adjusted up by 1
4 4 {3,4,5} Cannot adjust, skipped

Output: 3

Complexity Analysis

Measure Complexity Explanation
Time O(n log n + n*k) Sorting takes O(n log n), iteration with k adjustments takes O(n*k) in worst case
Space O(n) Set/map stores all distinct numbers

Sorting dominates for large n. The inner loop may run up to k times per element, but for small k relative to n, it is efficient.

Test Cases

# Provided examples
assert Solution().maxDistinctElements([1,2,2,3,3,4], 2) == 6
assert Solution().maxDistinctElements([4,4,4,4], 1) == 3

# Edge cases
assert Solution().maxDistinctElements([1,1,1,1,1], 0) == 1  # No adjustment possible
assert Solution().maxDistinctElements([1,2,3,4,5], 0) == 5  # Already distinct
assert Solution().maxDistinctElements([1], 100) == 1       # Single element
assert Solution().maxDistinctElements([1,1,2,2,3,3], 100) == 6 # Large k spreads duplicates
Test Why
[1,2,2,3,3,4], 2 Example from problem, tests multiple duplicates
[4,4,4,4], 1 Example from problem, small k
[1,1,1,1,1], 0 Tests k=0, no movement allowed
[1,2,3,4,5], 0 Already distinct, ensures no unnecessary adjustment
[1], 100 Single element edge case
[1,1,2,2,3,3], 100 Large k ensures maximum spreading

Edge Cases

All elements identical, k = 0: No adjustments are allowed, the result is always 1 regardless of array length. The implementation correctly adds the first element and skips duplicates.

Large k values: If k is large, duplicates can be spread widely. Our algorithm iterates over potential shifts and guarantees uniqueness within the allowed range.

Already distinct array: If the input has no duplicates, the algorithm should not attempt any unnecessary adjustments. Sorting preserves the original order of checks, and the used set prevents accidental collisions.