How do you solve Frequency of the Most Frequent Element?

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.

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).

Q: 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.

Medium Sliding Window

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

Preview

Sorting the array reveals that increments are only needed to raise smaller elements to the rightmost element in a subarray…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Sort the array. Use two pointers (left and right) to maintain a sliding window…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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.

Pattern Spotlight

Sliding Window (Variable Size with Sum Tracking)

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.

Solution

Python

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

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.

Expand Sliding Window and Accumulate Window Sum

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

Shrink Window to Maintain Feasibility Under Increment Budget

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

Track Maximum Frequency Achieved by Valid Windows

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

Return the Maximum Frequency Found

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

4 more steps with full analysis available on Pro.

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.

Full line-by-line criticality + rationale for all 11 lines available on Pro.

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?

See the answer with Pro.

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`