Problem Description

You have an array of integers nums (0-indexed) and an integer k representing the maximum number of operations you can perform.

In each operation, you can:

• Select any index i in the array
• Either increase or decrease nums[i] by 1

Your goal is to maximize the frequency of the most frequent element in the final array. The frequency of an element is simply how many times it appears in the array.

For example, if you have nums = [1, 2, 4] and k = 5:

• You could change the array to [2, 2, 2] by decreasing 4 twice (2 operations) and increasing 1 once (1 operation), using 3 operations total
• This gives you a maximum frequency of 3 (the element 2 appears 3 times)

The key insight is that you want to make as many elements equal as possible within your operation budget k. Each operation moves an element one step closer to your target value, so elements that are already close to each other will require fewer operations to become equal.

The solution uses binary search to find the maximum possible frequency. For each candidate frequency, it checks if it's possible to create a subarray of that length where all elements can be made equal using at most k operations. The optimal strategy is to change all elements to the median value of the subarray, as this minimizes the total number of operations needed.

Intuition

The first key observation is that if we want to make multiple elements equal, it's most efficient to work with elements that are already close to each other in value. This suggests we should sort the array first, as consecutive elements in a sorted array have the smallest differences.

Once sorted, we realize that to maximize frequency, we should focus on making a contiguous segment of the sorted array equal. Why? Because if we try to make non-contiguous elements equal, we'd be wasting operations on elements in between that we're not including.

Now, what value should we change all elements in a segment to? The median is optimal. Consider a segment [1, 2, 5]:

• If we change all to 1: operations needed = 0 + 1 + 4 = 5
• If we change all to 2: operations needed = 1 + 0 + 3 = 4
• If we change all to 5: operations needed = 4 + 3 + 0 = 7

The median minimizes the total distance (and thus operations) needed.

The next insight is about the search strategy. If we can achieve a frequency of x (meaning we can make x elements equal), then we can definitely achieve any frequency less than x - we'd just use fewer elements. This monotonic property screams binary search!

So our approach becomes:

1. Binary search on the answer (the maximum frequency)
2. For each candidate frequency mid, check if it's achievable
3. To check if frequency mid is achievable, try all possible windows of size mid in the sorted array
4. For each window, calculate the cost to make all elements equal to the median
5. If any window has cost ≤ k, then frequency mid is achievable

The cost calculation uses prefix sums for efficiency. For a window from index i to j, we need:

• Elements below the median to increase to reach the median
• Elements above the median to decrease to reach the median

This gives us the formula: left + right where:

• left = sum of differences between median and elements below it
• right = sum of differences between elements above median and the median itself

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

Solution Approach

Let's walk through the implementation step by step:

1. Sorting and Prefix Sum Setup

First, we sort the array to group similar values together:

nums.sort()

Then we build a prefix sum array for efficient range sum queries:

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

This allows us to calculate the sum of any subarray nums[i:j] as s[j] - s[i] in O(1) time.

2. Binary Search Framework

We binary search on the possible frequency values:

l, r = 0, n
while l < r:
    mid = (l + r + 1) >> 1

• l = 0: minimum possible frequency
• r = n: maximum possible frequency (all elements become equal)
• mid = (l + r + 1) >> 1: middle value with upward rounding

3. Checking Feasibility of a Frequency

For each candidate frequency mid, we check all possible windows of size mid:

for i in range(n - mid + 1):
    j = i + mid
    x = nums[(i + j) // 2]  # median element

4. Calculating Operations Needed

For each window [i, j), we calculate the cost to make all elements equal to the median x:

left = ((i + j) // 2 - i) * x - (s[(i + j) // 2] - s[i])
right = (s[j] - s[(i + j) // 2]) - ((j - (i + j) // 2) * x)

Breaking down the formulas:

• Left cost: Elements from index i to (i+j)//2 - 1 need to increase to x

  • Number of elements: (i + j) // 2 - i
  • Target sum if all were x: ((i + j) // 2 - i) * x
  • Current sum: s[(i + j) // 2] - s[i]
  • Operations needed: target sum - current sum

• Right cost: Elements from index (i+j)//2 + 1 to j-1 need to decrease to x

  • Current sum: s[j] - s[(i + j) // 2]
  • Target sum if all were x: (j - (i + j) // 2) * x
  • Operations needed: current sum - target sum

5. Binary Search Decision

If any window can be transformed with at most k operations:

if left + right <= k:
    ok = True
    break

Based on feasibility:

• If feasible (ok = True): This frequency works, try larger (l = mid)
• If not feasible: This frequency is too large, try smaller (r = mid - 1)

Time Complexity: O(n² log n)

• Binary search: O(log n) iterations
• Each iteration checks O(n) windows
• Each window check: O(1) using prefix sums

Space Complexity: 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 Build Prefix Sum

• Array is already sorted: [1, 4, 8, 13]
• Prefix sum array: s = [0, 1, 5, 13, 26]
  • This allows us to quickly calculate range sums

Step 2: Binary Search on Frequency

We'll binary search between frequency 1 and 4 (array length).

First iteration: mid = 2

• Can we make 2 elements equal with ≤ 5 operations?

• Check all windows of size 2:

  Window [1, 4] (indices 0-1):

  • Median element: nums[0] = 1
  • Cost to make both equal to 1: We need to decrease 4 to 1
  • Operations = 3 ✓ (≤ 5, so frequency 2 is achievable)

Second iteration: mid = 3

• Can we make 3 elements equal with ≤ 5 operations?

• Check all windows of size 3:

  Window [1, 4, 8] (indices 0-2):

  • Median element: nums[1] = 4
  • Cost calculation:
    • Left side: Change 1 to 4 = 3 operations
    • Right side: Change 8 to 4 = 4 operations
    • Total = 7 operations ✗ (> 5)

  Window [4, 8, 13] (indices 1-3):

  • Median element: nums[2] = 8
  • Cost calculation:
    • Left side: Change 4 to 8 = 4 operations
    • Right side: Change 13 to 8 = 5 operations
    • Total = 9 operations ✗ (> 5)

  Frequency 3 is not achievable with k=5.

Binary Search Continues:

• Since frequency 3 failed, we search lower
• We already know frequency 2 works
• Binary search converges to answer: 2

Verification of the Answer: With k=5 operations, we can transform [1, 4, 8, 13] to have at most frequency 2:

• One possibility: Change 4 to 1 (3 operations) → [1, 1, 8, 13]
• Another possibility: Change 8 to 4 (4 operations) → [1, 4, 4, 13]

The maximum frequency achievable is 2.

Template Solution

def maxFrequency(self, nums: List[int], k: int) -> int:
    nums.sort()
    n = len(nums)
    s = list(accumulate(nums, initial=0))
  
    l, r = 0, n
    while l < r:
        mid = (l + r + 1) >> 1
        ok = False
      
        # Check all windows of size mid
        for i in range(n - mid + 1):
            j = i + mid
            x = nums[(i + j) // 2]  # median element
          
            # Calculate operations needed for left side
            left = ((i + j) // 2 - i) * x - (s[(i + j) // 2] - s[i])
          
            # Calculate operations needed for right side  
            right = (s[j] - s[(i + j) // 2]) - ((j - (i + j) // 2) * x)
          
            if left + right <= k:
                ok = True
                break
      
        if ok:
            l = mid
        else:
            r = mid - 1
  
    return l

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity consists of two main parts:

• Sorting the array takes O(n log n) time
• Binary search on the answer space: The binary search runs for O(log n) iterations (searching from 0 to n for the maximum frequency). In each iteration, we check all possible subarrays of length mid, which takes O(n) time. Therefore, this part contributes O(n × log n) time.

Since both operations are O(n × log n), the overall time complexity is O(n × log n).

Space Complexity: O(n)

The space complexity comes from:

• The prefix sum array s which stores n+1 elements, requiring O(n) space
• The sorting operation may require O(log n) space for the recursion stack in the worst case (depending on the sorting algorithm implementation)
• Other variables like l, r, mid, i, j, x, left, right, and ok use O(1) space

The dominant term is O(n) from the prefix sum array, so the overall space complexity is O(n).

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

Common Pitfalls

1. Incorrect Median Index Calculation for Even-Length Windows

One of the most common mistakes is mishandling the median index calculation when the window has an even number of elements. The code uses (window_start + window_end) // 2, but developers often confuse whether this gives the lower or upper median.

The Issue: For even-length windows, there are two middle elements. The formula (i + j) // 2 gives us the upper median index. This inconsistency can lead to:

• Incorrect cost calculations
• Off-by-one errors in counting elements on each side

Solution: Be explicit about which median you're using and ensure consistency:

# For a window [window_start, window_end)
median_index = (window_start + window_end) // 2
# This gives the upper median for even-length windows

# Alternative: use lower median consistently
# median_index = (window_start + window_end - 1) // 2

2. Confusion with Prefix Sum Boundaries

The prefix sum array uses initial=0, making prefix_sum[i] represent the sum of elements from index 0 to i-1 (exclusive of i). This off-by-one relationship often causes errors.

The Issue: Developers might incorrectly calculate range sums:

# Wrong: sum from i to j inclusive
wrong_sum = prefix_sum[j] - prefix_sum[i]  # This actually gives sum from i to j-1

# Correct: sum from i to j inclusive
correct_sum = prefix_sum[j + 1] - prefix_sum[i]

Solution: Always remember that with initial=0, prefix_sum[i] contains the sum of the first i elements (indices 0 to i-1).

3. Binary Search Boundary Update Logic

The code uses mid = (left + right + 1) >> 1 with specific update rules. Using the wrong combination can cause infinite loops.

The Issue: If you use mid = (left + right) // 2 but keep the update logic as left = mid, you'll get an infinite loop when left = right - 1.

Solution: Match your mid calculation with your update logic:

# Option 1: Upper mid with left = mid
mid = (left + right + 1) // 2
if valid:
    left = mid
else:
    right = mid - 1

# Option 2: Lower mid with right = mid
mid = (left + right) // 2
if valid:
    left = mid + 1
else:
    right = mid

4. Not Considering Single-Element Windows

Some implementations forget that a frequency of 1 is always achievable with 0 operations, potentially missing edge cases.

The Issue: Starting binary search with left = 1 instead of left = 0 might seem logical but can cause issues with edge cases or when the result should be 1.

Solution: Always start with left = 0 and let the binary search naturally find the answer, even if it means checking trivial cases.

5. Integer Overflow in Cost Calculations

For large arrays with large values, the cost calculations might overflow in languages with fixed integer sizes.

The Issue: Expressions like left_count * median_value can overflow when both values are large.

Solution (for languages with overflow concerns): Use appropriate data types or check for potential overflow:

# Python handles big integers automatically, but in other languages:
# Use long long in C++ or check for overflow before multiplication
if left_count > 0 and median_value > MAX_VALUE // left_count:
    # Handle overflow case