Watch 10 video solutions for Maximum Number of Distinct Elements After Operations, a medium level problem involving Array, Greedy, Sorting. This walkthrough by codestorywithMIK has 8,429 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |