LeetCode 1838 - Frequency of the Most Frequent Element

LeetCode Problem 1838

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Greedy, Sliding Window, Sorting, Prefix Sum

Solution

Problem Understanding

This problem asks us to determine the maximum frequency of an element in an integer array nums after performing at most k increment operations. Each operation allows you to choose an element and increase it by 1. The frequency of an element is the number of times it occurs in the array.

In other words, given the ability to "level up" numbers in the array, we want to maximize the number of identical elements. The input is an array of integers and a single integer k, which represents the total number of increments we can distribute among elements. The output is a single integer, representing the largest possible frequency of any number after these operations.

The constraints are significant: nums can be up to 100,000 elements long, and both nums[i] and k can be as large as 100,000. This indicates that brute-force solutions checking all possibilities would be too slow. Edge cases to consider include arrays with one element, arrays where all elements are equal, arrays that already contain repeated numbers, and scenarios where k is very small or very large relative to the differences between elements.

Approaches

A brute-force approach would involve iterating over every element and attempting to increase smaller elements to match it, keeping track of the number of operations used. For each target element, we could count how many elements can be incremented to reach it within k operations. While this is correct, it has time complexity O(n^2) and would be too slow for large arrays.

The key insight for an optimal solution is that we can sort the array and focus on sliding windows. By sorting, we know that if we want to make a subset of elements equal to the largest element in that subset, it is always optimal to increase the smaller elements in that window to match the largest one. We can then maintain a window [left, right] representing elements we are trying to make equal to nums[right]. The total cost to increase all elements in the window to nums[right] can be efficiently maintained using a running sum.

The optimal solution is therefore a sliding window with prefix sum approach, where the window expands greedily until the total increments needed exceed k, at which point we shrink from the left.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Increment each element individually and count frequency
Optimal	O(n log n)	O(1)	Sort + sliding window to maintain sum of increments

Algorithm Walkthrough

1. Sort the array. This allows us to consider consecutive sequences of numbers where the smallest can be incremented to match the largest.
2. Initialize two pointers, left = 0 and iterate right over the array.
3. Maintain a running sum representing the total of elements in the current window.
4. For each new right, calculate the total cost to increase all elements in the window [left, right] to nums[right] using the formula cost = nums[right] * window_size - window_sum.
5. If the cost exceeds k, increment left to shrink the window and adjust the window sum accordingly.
6. Update the maximum frequency as right - left + 1 after each step.
7. Return the maximum frequency found.

Why it works: The invariant maintained is that all elements in the window [left, right] can be incremented to nums[right] without exceeding k operations. By expanding the window greedily and shrinking when necessary, we ensure that at every step we consider the largest possible valid frequency.

Python Solution

from typing import List

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

Implementation Walkthrough: First, we sort nums so that we can process elements in increasing order. We maintain a sliding window [left, right] and a running sum total of elements in that window. For each right, we calculate the operations needed to make all elements equal to nums[right]. If this exceeds k, we shrink the window from the left. After processing each element, we update max_freq to track the largest valid window.

Go Solution

import "sort"

func maxFrequency(nums []int, k int) int {
    sort.Ints(nums)
    left := 0
    total := 0
    maxFreq := 0

    for right := 0; right < len(nums); right++ {
        total += nums[right]
        for nums[right]*(right-left+1)-total > k {
            total -= nums[left]
            left++
        }
        if right-left+1 > maxFreq {
            maxFreq = right - left + 1
        }
    }

    return maxFreq
}

Go-specific notes: Sorting is done using sort.Ints. We carefully use integer arithmetic, and since total is an int, it can hold sums up to 10^10 without overflow in Go. The logic mirrors the Python solution using a sliding window and running sum.

Worked Examples

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

After sorting: [1,2,4]

Window expands:

left	right	window_sum	cost	max_freq
0	0	1	0	1
0	1	3	1*2 -3=1? wait let's calculate	2
0	2	7	4*3 - 7 = 5	3

All elements can be incremented to 4 with total cost 5 ≤ k. Output: 3.

Example 2: nums = [1,4,8,13], k = 5

After sorting: [1,4,8,13]

Window calculations:

• Right=0: max_freq=1
• Right=1: cost = 4*2 - (1+4)=8-5=3 ≤ 5 → max_freq=2
• Right=2: cost = 8_3 - (1+4+8)=24-13=11 > 5 → shrink left → left=1 → cost=8_2-(4+8)=16-12=4 ≤5 → max_freq=2
• Right=3: cost=13_3-(4+8+13)=39-25=14>5 → shrink left → left=2 → cost=13_2-(8+13)=26-21=5 → max_freq=2

Output: 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting takes O(n log n), sliding window is O(n)
Space	O(1)	Only pointers and running sum are used

Sorting dominates time complexity. The sliding window ensures we only traverse each element once for left and right pointers.

Test Cases

# Provided examples
assert Solution().maxFrequency([1,2,4], 5) == 3  # all become 4
assert Solution().maxFrequency([1,4,8,13], 5) == 2
assert Solution().maxFrequency([3,9,6], 2) == 1

# Edge cases
assert Solution().maxFrequency([1], 100) == 1  # single element
assert Solution().maxFrequency([1,1,1], 0) == 3  # already equal
assert Solution().maxFrequency([1,2,3,4,5], 10) == 5  # enough k to make all equal
assert Solution().maxFrequency([1,1,2,2,3,3], 3) == 4  # partial increments
assert Solution().maxFrequency([5,1,1,1], 2) == 3  # max frequency in middle

# Stress case
assert Solution().maxFrequency(list(range(1, 100001)), 100000) == 2  # incremental only possible for neighbors

Test	Why
[1,2,4], k=5	Basic functionality with moderate k
[1,4,8,13], k=5	Multiple optimal paths
[3,9,6], k=2	Insufficient k
[1], k=100	Single element edge
[1,1,1], k=0	Already equal elements
[1,2,3,4,5], k=10	Enough k to equalize all
[1,1,2,2,3,3], k=3	Partial increment scenario
[5,1,1,1], k=2	Middle window increments

Edge Cases

Single element array: Arrays of length 1 should return 1 regardless of k, as