#3397

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Number of Distinct Elements After Operations

Maximize distinct elements in an array by performing at most one operation on each element.

Problem Statement

You are given an array of integers, nums, and a non-negative integer k. You can apply at most one operation to each element of the array, where the operation is either adding or subtracting 1. Your goal is to maximize the number of distinct elements in the array after performing these operations.

To achieve this, you need to decide which elements should undergo the operation, while ensuring the total number of distinct elements is maximized. Your task is to return the maximum possible number of distinct elements in the array after the operations.

Examples

Example 1

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

Output: 6

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

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

Solution Approach

Sort the Array

Begin by sorting the array to handle elements in increasing order. This helps in making greedy choices about which elements to modify to maximize distinct elements.

Greedy Operation on Duplicates

Focus on modifying the duplicate elements by either adding or subtracting 1, ensuring that these changes result in new distinct values. The greedy approach is optimal here as it tries to create new distinct elements by focusing on the most frequent ones.

Track Distinct Elements

Use a set or similar data structure to track distinct elements as you modify the array. This ensures that after performing the operations, the distinct element count is accurately maintained.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the sorting step, which is O(n log n). After sorting, the greedy approach runs in linear time, O(n), making the overall time complexity O(n log n). Space complexity is O(n) due to the storage required for the set of distinct elements.

What Interviewers Usually Probe

Understanding of greedy algorithms
Ability to optimize operations on duplicates
Familiarity with sorting and its impact on optimization

Common Pitfalls or Variants

Common pitfalls

Incorrect application of the operation (add or subtract 1) to non-duplicate elements
Failing to prioritize duplicates when applying operations
Overlooking the need to track distinct elements during modification

Follow-up variants

Allowing more than one operation per element
Considering a larger k value or different operations
Limiting the number of elements that can be modified

FAQ

What is the main pattern in this problem?

The main pattern is greedy choice plus invariant validation, where sorting helps maximize the number of distinct elements.

How does sorting help in this problem?

Sorting the array ensures that you can handle the smallest duplicates first, maximizing the chances of creating new distinct elements.

How should I decide which elements to modify?

Focus on the most frequent elements and modify them first, using either addition or subtraction to create distinct values.

What is the time complexity of this solution?

The time complexity is O(n log n) due to sorting, followed by a linear pass to apply operations and track distinct elements.

What if k is very large?

Even with large k, the greedy approach remains valid, as long as the number of operations is limited to creating distinct values efficiently.

terminal

Solution

Solution 1: Greedy + Sorting

We can sort the array $\textit{nums}$ and then consider each element $x$ from left to right.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxDistinctElements(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans = 0
        pre = -inf
        for x in nums:
            cur = min(x + k, max(x - k, pre + 1))
            if cur > pre:
                ans += 1
                pre = cur
        return ans

Continue Practicing

#3413 maximum coins from k consecutive bags #3424 minimum cost to make arrays identical #3362 zero array transformation iii