1838. Frequency of The Most Frequent Element - Explanation

Description

The frequency of an element is the number of times it occurs in an array.

You are given an integer array nums and an integer k. In one operation, you can choose an index of nums and increment the element at that index by 1.

Return the maximum possible frequency of an element after performing at most k operations.

Example 1:

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

Output: 3

Explanation: Increment the first element three times and the second element two times to make nums = [4,4,4].
4 has a frequency of 3.

Example 2:

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

Output: 2

Explanation: There are multiple optimal solutions:

Increment the first element three times to make nums = [4,4,8,13]. 4 has a frequency of 2.
Increment the second element four times to make nums = [1,8,8,13]. 8 has a frequency of 2.
Increment the third element five times to make nums = [1,4,13,13]. 13 has a frequency of 2.

Constraints:

1 <= nums.length <= 100,000
1 <= nums[i], k <= 100,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

We can only increment elements, so the target value for our frequent element must already exist in the array. For each element, we check how many smaller elements we can increment to match it using at most k operations.

Sorting the array helps because the elements closest in value to our target require the fewest increments. We greedily extend leftward from each position, incrementing elements until we run out of operations.

Algorithm

Sort the array in ascending order.
For each index i, treat nums[i] as the target value.
Starting from j = i - 1, work backward and subtract the cost nums[i] - nums[j] from a temporary budget.
Stop when the budget becomes negative.
The count of elements matching nums[i] is i - j.
Track and return the maximum count found in res.

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        res = 1
        for i in range(len(nums)):
            j = i - 1
            tmpK = k
            while j >= 0 and (tmpK - (nums[i] - nums[j])) >= 0:
                tmpK -= (nums[i] - nums[j])
                j -= 1
            res = max(res, i - j)
        return res

Time & Space Complexity

Time complexity: $O(n ^ 2 + n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

2. Prefix Sum + Binary Search

Intuition

Instead of extending leftward one element at a time, we can use binary search to find the optimal left boundary. The cost to make all elements in a range equal to the rightmost element is: (count * target) - sum_of_range. Using prefix sums, we compute range sums in O(1).

For each right boundary i, we binary search for the smallest left boundary m such that the cost is within budget k. The window size i - m + 1 gives us the frequency.

Algorithm

Sort the array and build a prefix sum array.
For each index i:
- Binary search for the leftmost index m where the cost (i - m + 1) * nums[i] - (prefix[i+1] - prefix[m]) is at most k.
- Update res with the window size.
Return the maximum frequency found.

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + nums[i]

        res = 1
        for i in range(n):
            l, r = 0, i
            while l <= r:
                m = (l + r) // 2
                curSum = prefix_sum[i + 1] - prefix_sum[m]
                need = (i - m + 1) * nums[i] - curSum
                if need <= k:
                    r = m - 1
                    res = max(res, i - m + 1)
                else:
                    l = m + 1
        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Sliding Window

Intuition

Since the array is sorted, we can use a sliding window. As we expand the window by moving the right pointer, we add elements and check if the cost to make all elements equal to the rightmost exceeds k. If it does, we shrink from the left.

The cost for a window is target * window_size - window_sum. When this exceeds k, we need a smaller window. The window always represents a valid subarray that can be made uniform within budget.

Algorithm

Sort the array.
Initialize l = 0, total = 0, and res = 0.
For each right index r:
- Add nums[r] to total.
- While nums[r] * (r - l + 1) > total + k:
  - Subtract nums[l] from total and increment l.
- Update res with r - l + 1.
Return res.

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        total = res = 0
        l = 0

        for r in range(len(nums)):
            total += nums[r]
            while nums[r] * (r - l + 1) > total + k:
                total -= nums[l]
                l += 1
            res = max(res, r - l + 1)

        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

4. Advanced Sliding Window

Intuition

We can optimize further by observing that we only care about the maximum window size. Once we find a valid window of size w, we never need a smaller window. So instead of shrinking until valid, we can just slide the window forward, maintaining its size when invalid.

If a new element causes the window to become invalid, we remove exactly one element from the left, keeping the window size the same. The window size only grows when we find a valid configuration.

Algorithm

Sort the array.
Initialize l = 0 and total = 0.
For each right index r:
- Add nums[r] to total.
- If (r - l + 1) * nums[r] > total + k:
  - Subtract nums[l] from total and increment l.
The final window size is n - l which equals the maximum frequency.
Return this value.

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        l = 0
        total = 0

        for r in range(len(nums)):
            total += nums[r]

            if (r - l + 1) * nums[r] > total + k:
                total -= nums[l]
                l += 1

        return len(nums) - l

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.