Maximize Element Frequency with Limited Increments
Company: Goldman Sachs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Maximize Element Frequency with Limited Increments
Implement `max_frequency_after_increments(nums: list[int], k: int) -> int`.
In one operation, choose an element of `nums` and increase it by `1`. You may perform at most `k` operations in total. Return the largest possible frequency of any value after the operations.
### Input Domain
- `1 <= len(nums) <= 100,000`.
- `1 <= nums[i] <= 100,000`.
- `0 <= k <= 10^14`.
- Values and intermediate operation counts fit in signed 64-bit integers.
### Output Rules
- Return only the maximum attainable frequency.
- Elements may be increased but never decreased.
- If several target values attain the same maximum, the returned scalar is unchanged, so no tie-break is needed.
### Constraints
- Target time complexity is `O(n log n)` or better.
- Additional space may be `O(n)`.
### Examples
#### Example 1
Input: `nums = [1,3,5,7,8,9,10,15], k = 6`
Output: `4`
Raising `7`, `8`, and `9` to `10` costs `3 + 2 + 1 = 6`, producing four copies of `10`.
#### Example 2
Input: `nums = [1,3,5,10,10,10,10,15], k = 0`
Output: `4`
No increments are available, and `10` already appears four times.
```hint Equalize toward an existing value
After ordering the values, consider a contiguous group raised to match its largest member and maintain the cost of that choice.
```
Quick Answer: Find the largest attainable element frequency after a limited number of increment operations using an efficient ordered-window approach.
In one operation, choose an element of nums and increase it by 1. You may perform at most k operations in total. Return the largest possible frequency of any value after the operations.
Input Domain
1 <= len(nums) <= 100,000
.
1 <= nums[i] <= 100,000
.
0 <= k <= 10^14
.
Values and intermediate operation counts fit in signed 64-bit integers.
Output Rules
Return only the maximum attainable frequency.
Elements may be increased but never decreased.
If several target values attain the same maximum, the returned scalar is unchanged, so no tie-break is needed.
Constraints
Target time complexity is
O(n log n)
or better.
Additional space may be
O(n)
.
Examples
Example 1
Input: nums = [1,3,5,7,8,9,10,15], k = 6
Output: 4
Raising 7, 8, and 9 to 10 costs 3 + 2 + 1 = 6, producing four copies of 10.
Example 2
Input: nums = [1,3,5,10,10,10,10,15], k = 0
Output: 4
No increments are available, and 10 already appears four times.