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:
[-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 <= 1051 <= nums[i] <= 1090 <= k <= 109Problem Overview: You receive an integer array nums and a value k. Each element can be adjusted once by adding any integer in the range [-k, k]. The goal is to choose final values so the array contains the maximum possible number of distinct integers.
The key challenge is that every number has a flexible interval [nums[i] - k, nums[i] + k]. If multiple elements choose the same final value, they stop being distinct. The task becomes assigning each element a value from its interval while avoiding collisions with previously chosen numbers.
Approach 1: Brute Force with Hash Tracking (Exponential / impractical)
A direct idea is to try different values inside each element’s allowed range and track chosen numbers using a hash set. For each element, iterate through [nums[i]-k, nums[i]+k] and attempt assignments that keep the set distinct. Backtracking or DFS can explore combinations and record the best distinct count.
This approach demonstrates the constraint structure but quickly becomes infeasible. Each element may have up to 2k+1 choices, producing a combinatorial explosion. Even with pruning, the worst‑case complexity grows exponentially. Time complexity is roughly O((2k+1)^n) with O(n) recursion space. It only works for tiny inputs.
Approach 2: Greedy + Sorting (O(n log n) time, O(1) space)
The optimal approach treats each element as an interval and assigns values greedily. First sort the array using a sorting algorithm so smaller numbers are processed earlier. For every number x, compute its valid range: low = x - k and high = x + k.
Maintain the last assigned distinct value prev. For the current element, choose the smallest feasible number that is still greater than prev. This candidate becomes candidate = max(low, prev + 1). If candidate ≤ high, assign it and update prev. Otherwise the interval cannot produce a new distinct number and must be skipped.
This greedy rule works because picking the smallest valid number preserves space for future intervals. Assigning a larger value too early could block later elements from finding unique values. Sorting ensures intervals with smaller centers are resolved first, preventing unnecessary conflicts.
The algorithm performs one sort and a single linear scan. Time complexity is O(n log n) due to sorting, while the scan itself is O(n). Space complexity is O(1) aside from the sort (or O(log n) stack depending on implementation). The technique combines ideas from array processing, greedy algorithms, and interval scheduling.
Recommended for interviews: Interviewers expect the Greedy + Sorting solution. Explaining the brute-force idea first shows you understand the search space. Then pivot to the greedy interval assignment strategy and justify why choosing the smallest feasible value maximizes future flexibility.
We can sort the array nums and then consider each element x from left to right.
For the first element, we can greedily change it to x - k, making x as small as possible to leave more space for subsequent elements. We use the variable pre to track the maximum value of the elements used so far, initialized to negative infinity.
For subsequent elements x, we can greedily change it to min(x + k, max(x - k, pre + 1)). Here, max(x - k, pre + 1) means we try to make x as small as possible but not smaller than pre + 1. If this value exists and is less than x + k, we can change x to this value, increment the count of distinct elements, and update pre to this value.
After traversing the array, we obtain the maximum number of distinct elements.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array nums.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Hash Set | O((2k+1)^n) | O(n) | Conceptual understanding of the search space or extremely small inputs |
| Greedy + Sorting | O(n log n) | O(1) | Optimal solution for interviews and production when each element has an adjustable interval |
Maximum Number of Distinct Elements After Operations | Brute Force | Optimal | Leetcode 3397 | MIK • codestorywithMIK • 8,429 views views
Watch 9 more video solutions →Practice Maximum Number of Distinct Elements After Operations with our built-in code editor and test cases.
Practice on FleetCode