Coding - Maximum Number of Distinct Elements After Operations

Problem Statement

You are given an integer array nums and an integer k. You can perform the following operation on the array any number of times:

1. Choose any i in the array (where 1 <= i <= k) and increment nums[i] by 1.

Your goal is to maximize the number of distinct elements in the array after performing the operations.

Return the maximum number of distinct elements you can achieve.

Examples

Example 1:

` Input: nums = [1,2,2,3,2], k = 2 Output: 4 Explanation: We can perform the following operations:

• Increment nums[0] by 1, so nums becomes [2,2,2,3,2].
• Increment nums[2] by 1, so nums becomes [2,2,3,3,2]. Now, nums has 4 distinct elements: [2,3,2,3]. `

Example 2:

Input: nums = [1,2,2,3,2], k = 0 Output: 4 Explanation: Since k = 0, we cannot perform any operations, so the maximum number of distinct elements we can achieve is the number of distinct elements in the array itself.

Example 3:

Input: nums = [1,1,1,1,1,1], k = 2 Output: 2 Explanation: Regardless of how many times we perform the operation, we can only increase the value of the first two elements at most. Hence, the maximum number of distinct elements we can achieve is 2.

Constraints

• n == nums.length
• 1 <= n <= 105
• 0 <= nums[i] <= 105
• 1 <= k <= 105

Hints

1. Sort the array first.
2. Use a priority queue to keep track of the elements that can be incremented.
3. Increment the smallest element in the priority queue until it is equal to the next smallest element or until we can no longer increment it further.