Solution Approach

The solution uses the binary search template to find the maximum frequency. The key insight is to search for the first frequency that cannot be achieved, then return the frequency just before it.

Step 1: Sort the array and compute prefix sums

nums.sort()
prefix_sum = [0]
for num in nums:
    prefix_sum.append(prefix_sum[-1] + num)

Step 2: Define the feasibility function

The function cannot_achieve_frequency(freq) returns True if the frequency cannot be achieved (i.e., all windows exceed the budget):

def cannot_achieve_frequency(frequency: int) -> bool:
    for right in range(frequency, n + 1):
        left = right - frequency
        window_sum = prefix_sum[right] - prefix_sum[left]
        target_element = nums[right - 1]
        operations_needed = target_element * frequency - window_sum
        if operations_needed <= k:
            return False  # This frequency IS achievable
    return True  # Cannot achieve this frequency

This creates the pattern: false, false, ..., false, true, true, ...

• Small frequencies are achievable → return false
• At some point, frequencies become too large → return true

Step 3: Binary search template

left, right = 1, n + 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if cannot_achieve_frequency(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index - 1 if first_true_index != -1 else n

The answer is first_true_index - 1 because we want the last achievable frequency.

The time complexity is O(n log n) for sorting plus O(n log n) for binary search. 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.

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. Using Wrong Binary Search Template Variant

Pitfall: Using while left < right with left = mid instead of the standard template.

Wrong Implementation:

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

Correct Implementation (using template):

left, right = 1, n + 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if cannot_achieve_frequency(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index - 1 if first_true_index != -1 else n

2. Integer Overflow in Cost Calculation

Pitfall: The multiplication target_element * frequency can cause overflow in languages with fixed integer sizes.

Solution: Use long/int64 data types in Java/C++.

3. Off-by-One Error in Window Indexing

Pitfall: Incorrectly calculating window boundaries or the target element.

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

Pitfall: The algorithm relies on the array being sorted.

Solution: Always sort the array first: nums.sort()

5. Incorrect Prefix Sum Initialization

Solution: Initialize with 0 for easier range sum calculation:

prefix_sum = [0]
for num in nums:
    prefix_sum.append(prefix_sum[-1] + num)