LeetCode Entry

3346. Maximum Frequency of an Element After Performing Operations I

21.10.2025 medium 2025 kotlin

Max frequency after changing +k..-k ops elements window

3346. Maximum Frequency of an Element After Performing Operations I medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1149

Problem TLDR

Max frequency after changing +k..-k ops elements #medium #sliding_window

Intuition

Didn’t solved.

    // 5 6 7 8 10 15 20        k=5
    // maybe binary search? for resulting number in lowest..highest
    //       no rule for bs
    // sliding window
    // how to track how many was changed?
    // group?
    // 0 0 0 0 5 5 10 10 10   k=5 o=2
    // 0 0 0 0 5 5 10 10 10   k=5 o=1
    // 0 0 5 5 5 5            k=5 o=1
    // 0 1 1 1 5 5            k=5 o=1
    // maintain frequency of each element in window, know max frequency,
    //   ans = min(max_frequency_in_window+ops, window_size)
    // for frequencies: running sorted window, keep map num:freq; when add sorted-f[num]+(++f[num])
    // looks complicated, maybe wrong
    // 1: window is 2*k
    // 2: can't just use most frequent
    // 35 minute: let's look for hints
    // try each as candidate (j)
    // how to count number of operations? window-curr_freq is not correct
    // 5 11 20 20 when current freq = 2 of '20'; to do the 2*k range we have to use 2 operations
    // and to do 1*k range we can use 0 operations
    // 1:14 failed on 58 80 5 let's give up

Solve two separate problems:

1. choose every number as baseline, window b-k..b+k
2. no baseline, just 2k window

Approach

• sometimes there is no single algorithm, just separate tasks for different cases

Complexity

• Time complexity: \(O(nlog(n))\)

• Space complexity: \(O(n)\)

Code

// 125ms
    fun maxFrequency(n: IntArray, k: Int, o: Int): Int {
        n.sort(); var res = 0; var l = 0; var r = 0; var f = HashMap<Int,Int>()
        for (x in n) {
            while (r < n.size && n[r] <= x+k) f[n[r]] = 1 + (f[n[r++]] ?: 0)
            while (l < n.size && n[l] < x-k) f[n[l]] = -1 + f[n[l++]]!!
            res = max(res, min(f[x]!!+o, r - l))
        }
        l = 0
        return max(res, n.indices.maxOf { r ->  while (n[r] - n[l] > 2*k) ++l; min(r-l+1, o) })
    }