LeetCode Entry

3318. Find X-Sum of All K-Long Subarrays I

04.11.2025 easy 2025 kotlin rust

Sums of x most frequent from k-windows

3318. Find X-Sum of All K-Long Subarrays I easy blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1163

Problem TLDR

Sums of x most frequent from k-windows #easy

Intuition

Not actually easy. Brute-force: solve for each window, count frequency map, sort, take x.

Approach

• only 50 numbers; use an array instead of a HashMap

Complexity

• Time complexity: \(O(nklogk)\)

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

Code

// 62ms
    fun findXSum(n: IntArray, k: Int, x: Int) =
    (0..n.size-k).map { val g = n.slice(it..<it+k).groupBy {it}
        g.keys.sortedWith(compareBy({-(g[it]!!).size},{-it}))
         .take(x).map { it * g[it]!!.size }.sum()
    }

// 1ms
    pub fn find_x_sum(n: Vec<i32>, k: i32, x: i32) -> Vec<i32> {
        n.windows(k as usize).map(|w| {
            let mut f = [0;51]; for &v in w.iter() { f[v as usize] += 1 }
            (0..51).map(|v|(-f[v],-(v as i32))).sorted().into_iter()
            .take(x as usize).map(|(f,v)|v*f).sum()
        }).collect()
    }