Maximize Element Frequency with Limited Increments

Quick Overview

Find the largest attainable element frequency after a limited number of increment operations using an efficient ordered-window approach.

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.

|Home/Coding & Algorithms/Goldman Sachs
Goldman Sachs logo
Goldman Sachs
Aug 15, 2026
mediumSoftware EngineerOnsiteCoding & Algorithms
2
0

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.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...