Welcome to Subscribe On Youtube
3397. Maximum Number of Distinct Elements After Operations
Description
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:
- Add an integer in the range
[-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 <= 105
1 <= nums[i] <= 109
0 <= k <= 109
Solutions
Solution 1: Greedy + Sorting
We can sort the array $\textit{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 $\textit{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, \textit{pre} + 1))$. Here, $\max(x - k, \textit{pre} + 1)$ means we try to make $x$ as small as possible but not smaller than $\textit{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 $\textit{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 $\textit{nums}$.
-
class Solution { public int maxDistinctElements(int[] nums, int k) { Arrays.sort(nums); int n = nums.length; int ans = 0, pre = Integer.MIN_VALUE; for (int x : nums) { int cur = Math.min(x + k, Math.max(x - k, pre + 1)); if (cur > pre) { ++ans; pre = cur; } } return ans; } }
-
class Solution { public: int maxDistinctElements(vector<int>& nums, int k) { ranges::sort(nums); int ans = 0, pre = INT_MIN; for (int x : nums) { int cur = min(x + k, max(x - k, pre + 1)); if (cur > pre) { ++ans; pre = cur; } } return ans; } };
-
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
-
func maxDistinctElements(nums []int, k int) (ans int) { sort.Ints(nums) pre := math.MinInt32 for _, x := range nums { cur := min(x+k, max(x-k, pre+1)) if cur > pre { ans++ pre = cur } } return }
-
function maxDistinctElements(nums: number[], k: number): number { nums.sort((a, b) => a - b); let [ans, pre] = [0, -Infinity]; for (const x of nums) { const cur = Math.min(x + k, Math.max(x - k, pre + 1)); if (cur > pre) { ++ans; pre = cur; } } return ans; }