What pattern does Frequency of the Most Frequent Element use?

The Pattern: Sliding Window (Variable Size with Sum Tracking) The Heuristic: When maximizing frequency or length under a cost constraint, sorting the input and using a sliding window to maintain a feasible range allows efficient pruning by expanding and contracting the window based on the cost condition.

Frequency of the Most Frequent Element

Q: What is the time complexity of Frequency of the Most Frequent Element?

O(n log n). Sorting the array takes O(n log n). The sliding window traversal is O(n) since each element is visited at most twice (once when right pointer moves forward and once when left pointer moves forward).

Problem

Given an integer array nums and an integer k, return the maximum possible frequency of an element after performing at most k increments on elements of the array.

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ 10¹⁰

Example

Input: nums = [1,2,4], k = 5

Output: 3

Sorting nums gives [1,2,4]. The algorithm tries to make a subarray of elements equal by incrementing smaller elements. Starting with the full array, it calculates the total increments needed to raise all elements to 4 (the largest in the window). The increments needed are (3 * 4) - (1 + 2 + 4) = 12 - 7 = 5, which equals k. Thus, all three elements can be made equal to 4, achieving a frequency of 3. The critical insight is that by sorting, the problem reduces to finding the longest subarray where the increments needed to equalize to the rightmost element do not exceed k.

Approach

Straightforward Solution

A brute-force approach would consider every subarray and calculate the increments needed to equalize all elements to the maximum in that subarray. This approach is O(n^2) and infeasible for large inputs.

Core Observation

To maximize the frequency of an element after increments, the best strategy is to increment smaller elements up to the value of a larger element. Sorting the array allows us to consider subarrays where all elements can be made equal to the largest element in that subarray.

Path to Optimal

Sorting the array reveals that increments are only needed to raise smaller elements to the rightmost element in a subarray. Using a sliding window, we can efficiently track the sum of elements in the current window and check if the increments needed to equalize to the rightmost element exceed k. If they do, we shrink the window from the left. This approach reduces the complexity to O(n log n) due to sorting and O(n) for the sliding window traversal.

Optimal Approach

Sort the array. Use two pointers (left and right) to maintain a sliding window. Keep track of the sum of elements in the window. For each right pointer increment, add nums[right] to the sum. While the increments needed to equalize all elements to nums[right] exceed k, move left pointer forward and subtract nums[left] from the sum. Update the best frequency as the maximum window size encountered. Return the best frequency after processing all elements.

Time

O(n log n)

Sorting the array takes O(n log n). The sliding window traversal is O(n) since each element is visited at most twice (once when right pointer moves forward and once when left pointer moves forward).

Space

O(1)

The algorithm uses a fixed number of variables for pointers and sums, and sorts the input in place, resulting in O(1) auxiliary space excluding the input array.

Solution

1class Solution:
  def maxFrequency(self, nums: list[int], k: int) -> int:
      nums.sort()
      left = 0
      total = 0
      best = 1
7
      for right in range(len(nums)):
          total += nums[right]
10
          while (right - left + 1) * nums[right] - total > k:
              total -= nums[left]
              left += 1
14
          best = max(best, right - left + 1)
16
      return best

Step-by-Step Solution

1

Sort the Array to Enable Monotonic Increment Strategy

3	`nums.sort()`

Objective

To arrange the elements in non-decreasing order so that increments only need to raise smaller elements to match larger ones.

Key Insight

Sorting transforms the problem into a linear structure where the largest element in any subarray is at the right end. This allows the increments needed to equalize the subarray to be computed efficiently as a function of the window size and sum, enabling a sliding window approach.

Interview Quick-Check

Core Logic

Sorting ensures that increments only raise elements up to the rightmost element in the window, simplifying the cost calculation.

Common Pitfalls & Bugs

Failing to sort leads to incorrect assumptions about which elements need increments and complicates the cost calculation.

2

Expand Sliding Window and Accumulate Window Sum

8for right in range(len(nums)):
9    total += nums[right]

Objective

To iterate through the array with a right pointer, adding elements to the current window and updating the total sum.

Key Insight

By maintaining the sum of the current window, the algorithm can quickly compute the increments needed to equalize all elements to the rightmost element without recomputing sums repeatedly. This incremental update is critical for efficiency.

Interview Quick-Check

Core Logic

Adding nums[right] to the total sum allows constant-time calculation of increments needed for the current window.

State & Boundaries

The right pointer moves forward through the array, expanding the window to consider larger subarrays.

3

Shrink Window to Maintain Feasibility Under Increment Budget

11while (right - left + 1) * nums[right] - total > k:
12    total -= nums[left]
13    left += 1

Objective

To move the left pointer forward when the increments needed exceed k, removing elements from the window and adjusting the sum accordingly.

Key Insight

The condition (window_size * nums[right] - total) > k precisely measures if the increments needed to equalize the window exceed the allowed budget. Shrinking the window from the left removes the smallest elements, reducing the increments needed and restoring feasibility.

Interview Quick-Check

Core Logic

The while loop ensures the window only contains elements that can be equalized within k increments by adjusting the left pointer.

Common Pitfalls & Bugs

Not updating the total sum when moving the left pointer leads to incorrect cost calculations and invalid windows.

State & Boundaries

The loop continues until the window satisfies the increment constraint, ensuring correctness.

4

Track Maximum Frequency Achieved by Valid Windows

15	`best = max(best, right - left + 1)`

Objective

To update the best frequency as the maximum window size found that satisfies the increment constraint.

Key Insight

The window size represents the number of elements that can be made equal with at most k increments. By tracking the maximum window size, the algorithm finds the highest achievable frequency.

Interview Quick-Check

Core Logic

Updating best with max(best, window_size) ensures the algorithm returns the largest feasible frequency.

Complexity

This update is O(1) per iteration, maintaining overall linear time complexity.

5

Return the Maximum Frequency Found

17	`return best`

Objective

To output the maximum frequency of an element achievable with at most k increments.

Key Insight

After processing all elements, best holds the size of the largest window where increments needed do not exceed k, which corresponds to the maximum frequency achievable.

Interview Quick-Check

Core Logic

Returning best completes the algorithm by providing the final answer.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 11 Critical

while (right - left + 1) * nums[right] - total > k:

Check if increments needed to equalize window exceed k.

This condition precisely measures feasibility: if the increments needed to raise all elements to nums[right] exceed k, the window must shrink to restore feasibility.

Line 3 Critical

nums.sort()

Sort the input array in non-decreasing order.

Sorting is essential because it allows the algorithm to consider subarrays where increments only need to raise smaller elements to the rightmost element, enabling efficient cost calculation and sliding window usage.

Line 9 Core

total += nums[right]

Add the current right element to the total sum of the window.

Incrementally updating the sum avoids recomputing the sum from scratch for each window, maintaining O(n) time complexity.

Line 12 Core

total -= nums[left]

Subtract the leftmost element from the total sum as the window shrinks.

Removing nums[left] from the sum maintains an accurate total for the current window after moving the left pointer.

Line 15 Core

best = max(best, right - left + 1)

Update the best frequency with the current window size if larger.

Tracking the maximum window size ensures the algorithm returns the largest feasible frequency achievable with k increments.

Line 5 Core

total = 0

Initialize total sum of elements in the current window to 0.

Tracking the sum of the window elements allows constant-time calculation of increments needed to equalize all elements to the rightmost element.

Line 13 Core

left += 1

Move the left pointer forward to shrink the window.

Advancing left discards elements that cause the increment cost to exceed k, restoring the window's feasibility.

Line 8 Standard

for right in range(len(nums)):

Iterate through the array with the right pointer expanding the window.

The right pointer explores all possible window end positions, enabling the algorithm to consider all subarrays in a single pass.

Line 17 Standard

return best

Return the maximum frequency found after processing all elements.

This final return provides the solution to the problem, representing the largest number of elements that can be made equal within the increment budget.

Line 4 Standard

left = 0

Initialize the left pointer of the sliding window to 0.

The left pointer marks the start of the current window, which will expand and contract to maintain feasibility under the increment budget.

Line 6 Standard

best = 1

Initialize best frequency found so far to 1.

At minimum, any single element can be considered a frequency of 1, serving as the baseline for comparison.

Test Your Understanding

Why does the sliding window condition check (window_size * max_element - sum_of_window) <= k guarantee the feasibility of equalizing all elements in the window?

Because the increments needed to make all elements equal to the maximum element in the window is exactly the difference between the total desired sum (window_size * max_element) and the current sum of elements. If this difference is within k, it means we can increment the smaller elements sufficiently without exceeding the allowed increments.

Don't just read it. Drill it.

Reconstruct Frequency of the Most Frequent Element from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Frequency of the Most Frequent Element drill

or drill a free problem

1	`class Solution:`
2	`def maxFrequency(self, nums: list[int], k: int) -> int:`
3	`nums.sort()`
4	`left = 0`
5	`total = 0`
6	`best = 1`
7
8	`for right in range(len(nums)):`
9	`total += nums[right]`
10
11	`while (right - left + 1) * nums[right] - total > k:`
12	`total -= nums[left]`
13	`left += 1`
14
15	`best = max(best, right - left + 1)`
16
17	`return best`

Problem

Example

Approach

Solution

Step-by-Step Solution

Sort the Array to Enable Monotonic Increment Strategy

Expand Sliding Window and Accumulate Window Sum

Shrink Window to Maintain Feasibility Under Increment Budget

Track Maximum Frequency Achieved by Valid Windows

Return the Maximum Frequency Found

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.