Problem Description

You are given an integer array nums and an integer k. The frequency of an element is the number of times it appears in the array.

In one operation, you can select any index in nums and increment the element at that index by 1. You can perform at most k operations total.

Your goal is to find the maximum possible frequency of any element after performing at most k operations.

For example, if nums = [1, 2, 4] and k = 5, you could increment the first element three times (1→2→3→4) and the second element twice (2→3→4), using all 5 operations. This would give you the array [4, 4, 4], where the element 4 has a frequency of 3, which is the maximum possible frequency.

The key insight is that you want to make multiple elements equal to maximize frequency, and since you can only increment values, you'll typically want to increase smaller elements to match a larger target value. The challenge is determining which elements to modify and what target value to choose to maximize the frequency while staying within the operation budget k.

Intuition

Let's think about what happens when we try to maximize frequency. We want to make as many elements equal as possible using our limited operations.

First, consider which value we should target. Since we can only increment elements (never decrement), if we want to make multiple elements equal, we must choose a target value that's at least as large as all the elements we're modifying. The most efficient choice is to pick one of the existing elements as our target - specifically, the largest element in the group we're modifying. Why? Because if we pick any value larger than the maximum element, we're wasting operations by incrementing that maximum element unnecessarily.

Next, which elements should we modify? If we sort the array first, it becomes clear that we should pick consecutive elements. For instance, if we have [1, 2, 5, 8, 10] and want to make three elements equal to 5, it makes sense to choose [1, 2, 5] rather than [1, 2, 8] because the closer the elements are to our target, the fewer operations we need.

Now, how do we find the maximum frequency? We could check every possible window size (frequency), but that would be inefficient. Here's a key observation: if we can achieve a frequency of m, then we can definitely achieve any frequency less than m (we just use fewer elements). This monotonic property suggests binary search!

For binary search, we need to check if a given frequency m is achievable. We slide a window of size m through the sorted array and for each window, calculate the cost to make all elements equal to the maximum element in that window. If the window ends at index i, the maximum element is nums[i-1], and the cost is nums[i-1] * m - sum(window). We use a prefix sum array to quickly calculate the sum of any window.

The binary search finds the largest frequency where at least one window of that size can be transformed within our operation budget k.

Learn more about Greedy, Binary Search, Prefix Sum, Sorting and Sliding Window patterns.

Solution Approach

Let's implement the solution step by step based on our intuition:

Step 1: Sort the array and compute prefix sums

First, we sort the array to group similar elements together. This allows us to work with consecutive elements when trying to maximize frequency.

nums.sort()
s = list(accumulate(nums, initial=0))

The prefix sum array s helps us quickly calculate the sum of any subarray. Here, s[i] represents the sum of the first i elements (with s[0] = 0).

Step 2: Set up binary search

We binary search on the answer - the maximum possible frequency. The search range is from 1 (minimum possible frequency) to n (maximum possible frequency if all elements can be made equal).

l, r = 1, n

Step 3: Define the check function

For a given frequency m, we need to check if it's achievable. We slide a window of size m through the sorted array:

def check(m: int) -> bool:
    for i in range(m, n + 1):
        if nums[i - 1] * m - (s[i] - s[i - m]) <= k:
            return True
    return False

For each window ending at index i:

• The window contains elements from index i-m to i-1
• The target value is nums[i-1] (the largest element in the window)
• The current sum of the window is s[i] - s[i-m]
• The cost to make all elements equal to nums[i-1] is nums[i-1] * m - (s[i] - s[i-m])
• If this cost is at most k, then frequency m is achievable

Step 4: Binary search execution

while l < r:
    mid = (l + r + 1) >> 1
    if check(mid):
        l = mid
    else:
        r = mid - 1

We use the binary search pattern where:

• If frequency mid is achievable, we know all smaller frequencies are also achievable, so we search for larger frequencies by setting l = mid
• If frequency mid is not achievable, we need to search for smaller frequencies by setting r = mid - 1
• We use (l + r + 1) >> 1 to avoid infinite loops when l and r are adjacent

Step 5: Return the result

After the binary search converges, l contains the maximum achievable frequency.

The time complexity is O(n log n) for sorting plus O(n log n) for binary search (log n iterations, each checking n windows), giving overall O(n log n). The space complexity is O(n) for the prefix sum array.

Example Walkthrough

Let's walk through a concrete example with nums = [1, 4, 8, 13] and k = 5.

Step 1: Sort and compute prefix sums

• Array is already sorted: [1, 4, 8, 13]
• Prefix sums: s = [0, 1, 5, 13, 26]
  • s[0] = 0
  • s[1] = 0 + 1 = 1
  • s[2] = 1 + 4 = 5
  • s[3] = 5 + 8 = 13
  • s[4] = 13 + 13 = 26

Step 2: Binary search setup

• Search range: l = 1, r = 4 (minimum frequency 1, maximum frequency 4)

Step 3: Binary search execution

First iteration: mid = (1 + 4 + 1) / 2 = 3

• Check if frequency 3 is achievable:
  • Window 1: indices 0-2, elements [1, 4, 8]
    • Target: nums[2] = 8
    • Cost: 8 × 3 - (s[3] - s[0]) = 24 - 13 = 11
    • 11 > 5, too expensive
  • Window 2: indices 1-3, elements [4, 8, 13]
    • Target: nums[3] = 13
    • Cost: 13 × 3 - (s[4] - s[1]) = 39 - 25 = 14
    • 14 > 5, too expensive
  • Frequency 3 is NOT achievable, so r = 2

Second iteration: mid = (1 + 2 + 1) / 2 = 2

• Check if frequency 2 is achievable:
  • Window 1: indices 0-1, elements [1, 4]
    • Target: nums[1] = 4
    • Cost: 4 × 2 - (s[2] - s[0]) = 8 - 5 = 3
    • 3 ≤ 5, achievable! ✓
  • Frequency 2 is achievable, so l = 2

Third iteration: l = 2, r = 2, loop exits

Result: Maximum frequency = 2

We can verify: With 3 operations, we can increment 1→2→3→4, giving us [4, 4, 8, 13] with frequency 2 for element 4.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity consists of two main parts:

• Sorting the array nums takes O(n × log n) time
• Binary search runs O(log n) iterations, where each iteration calls the check function
• The check function iterates through at most n elements in its for loop, taking O(n) time
• Therefore, the binary search portion takes O(n × log n) time
• The overall time complexity is O(n × log n) + O(n × log n) = O(n × log n)

Space Complexity: O(n)

The space complexity analysis:

• The prefix sum array s stores n + 1 elements, requiring O(n) space
• The sorting operation may require O(log n) space for the recursion stack (depending on the sorting algorithm implementation)
• Other variables use constant space O(1)
• The dominant space usage is the prefix sum array, giving an overall space complexity of O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Binary Search Boundary Update

One of the most common mistakes is using the wrong binary search pattern, particularly with the mid calculation and boundary updates:

Incorrect Implementation:

while left_bound < right_bound:
    mid = (left_bound + right_bound) // 2  # Floor division
    if can_achieve_frequency(mid):
        left_bound = mid  # This creates infinite loop!
    else:
        right_bound = mid - 1

Problem: When left_bound = right_bound - 1 and can_achieve_frequency(mid) returns True, setting left_bound = mid doesn't change anything since mid = (left_bound + right_bound) // 2 = left_bound, causing an infinite loop.

Solution: Use ceiling division when updating left_bound = mid:

while left_bound < right_bound:
    mid = (left_bound + right_bound + 1) // 2  # Ceiling division
    if can_achieve_frequency(mid):
        left_bound = mid
    else:
        right_bound = mid - 1

2. Integer Overflow in Cost Calculation

When calculating the operations needed, the multiplication target_element * frequency can cause integer overflow in languages with fixed integer sizes:

Problematic Code (in languages like C++ or Java):

operations_needed = target_element * frequency - window_sum

Solution: Use appropriate data types or check for overflow:

# In Python, this isn't an issue due to arbitrary precision integers
# But in other languages, use long/int64 or check for overflow:
if target_element > (k + window_sum) // frequency:
    return False  # Would overflow or exceed k
operations_needed = target_element * frequency - window_sum

3. Off-by-One Error in Window Indexing

A subtle but critical mistake is incorrectly calculating window boundaries or the target element:

Incorrect:

for right in range(frequency - 1, n):  # Wrong starting point
    left = right - frequency + 1
    window_sum = prefix_sum[right + 1] - prefix_sum[left]  # Wrong indices
    target_element = nums[right]  # Might not be the maximum

Solution: Ensure correct window boundaries:

for right in range(frequency, n + 1):  # right is exclusive end
    left = right - frequency  # left is inclusive start
    window_sum = prefix_sum[right] - prefix_sum[left]
    target_element = nums[right - 1]  # Maximum element in sorted window

4. Forgetting to Sort the Array

The algorithm relies on the array being sorted to ensure that the rightmost element in any window is the maximum:

Incorrect:

def maxFrequency(self, nums: List[int], k: int) -> int:
    # Missing: nums.sort()
    n = len(nums)
    prefix_sum = [0]
    # ... rest of the code

Solution: Always sort the array first:

nums.sort()  # Critical for the algorithm to work correctly

5. Incorrect Prefix Sum Initialization

Using the wrong initial value or building the prefix sum incorrectly:

Incorrect:

prefix_sum = list(accumulate(nums))  # No initial 0
# or
prefix_sum = [nums[0]]
for i in range(1, n):
    prefix_sum.append(prefix_sum[-1] + nums[i])

Solution: Initialize with 0 for easier range sum calculation:

prefix_sum = [0]
for num in nums:
    prefix_sum.append(prefix_sum[-1] + num)
# Now prefix_sum[i] - prefix_sum[j] gives sum from index j to i-1