1838.frequency-of-the-most-frequent-element.md

1838. Frequency of the Most Frequent Element

Key Insights

Because we can only increase the elements, so we can only start from the smallest element. We sort the array first so that we can start from the smallest element and easily calculate the difference between the current element and the target element.

[1, 2, 4, 5], costs, max freq
 | // all becomes 1
 *                0         1   

[1, 2, 4, 5], costs, max freq
 |--| // all becomes 2
+1  *             1         2  

[1, 2, 4, 5], costs, max freq
 |-----| // all becomes 4
+1 +2  *          3         3

[1, 2, 4, 5], costs, max freq
 |--------|
+1 +2 +1  *       4         4

It's optimal to make elements equal to the largest number in a subarray. And we are tracking a sum over the subarray, the constraint is additive and monotinic, we want to maximize the size of a valid subarray. Sliding Window is a good fit.

Sliding Window

We iterate each element as target element, then calculate the cost to make all elements equal to the target element.

• Window: The subarray that we increase all elements to the the largest number in the subarray (nums[right]).

// If we want to make [1, 2, 4] to be [4, 4, 4]
 1, 2, 4, X, X, X, ...
 |-----|
 4  4  4
+3 +2     // Then cost is 5.

We want to find the longest window where all elements in the window can be increased to nums[right] with the cost k.

The cost is (nums[right] * window size) - window sum:

 1, 2, 4, 5, 6, 7, 9, X, X, X
                   R
 |-----------------|
 9  9  9  9  9  9  9
+8 +7 +6 +5 +4 +3 +2

window size = 7
window sum = 1 + 2 + 4 + 5 + 6 + 7 + 9 = 34
cost = (9 * 7) - 34 = 63 - 34 = 29

• If cost <= k: window is valid, we try to expand the window.
• If cost > k: window is invalid, we try to shrink the window.

fun maxFrequency(nums: IntArray, k: Int): Int {
    val k = k.toLong()
    nums.sort()
    var maxFreq = 1
    var left = 0
    var sum = 0L
    var cost = 0L
    for (right in nums.indices) {
        sum += nums[right].toLong()
        cost = nums[right].toLong() * (right - left + 1) - sum
        while (cost > k) {
            sum -= nums[left].toLong()
            left++
            cost = nums[right].toLong() * (right - left + 1) - sum
        }
        maxFreq = maxOf(maxFreq, right - left + 1)
    }
    return maxFreq
}

Binary Search

TODO: Implement this.