LeetCode Entry

2333. Minimum Sum of Squared Difference

10.10.2026 medium 2026 kotlin rust

Min sum of squared difs after adjusting each array by k

2333. Minimum Sum of Squared Difference medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1508

Problem TLDR

Min sum of squared difs after adjusting each array by k

Intuition

Didn’t solved myself. Binary search solution: find the lowest threshold max diff. Calculate leftover operations and spread them at most one per item if it equal the threshold. Counting solution: decrement the counts taking as much as you can and moving to the count-1 position. Do the final sweep.

Approach

• the leftover ops are guaranteed to spread at most one per item, because of math: (x-2)^2+y^2>(x-1)^2+(y-1)^2, the binary search would move the threshold otherwise

Complexity

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

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

Code

    fun minSumSquareDiff(n1: IntArray, n2: IntArray, k1: Int, k2: Int): Long {
        val c = LongArray(100001); for (i in n1.indices) c[abs(n1[i] - n2[i])]++
        var k = 1L * k1 + k2
        for (i in 100000 downTo 1) { val t = min(k, c[i]); c[i] -= t; c[i - 1] += t; k -= t }
        return c.indices.sumOf { c[it] * it * it }
    }

    pub fn min_sum_square_diff(a: Vec<i32>, b: Vec<i32>, k1: i32, k2: i32) -> i64 {
        let (mut count, mut k) = (vec![0i64; 100001], (k1 + k2) as i64);
        for (x, y) in a.into_iter().zip(b) { count[(x - y).abs() as usize] += 1 }
        for i in (1..=100000).rev() { if count[i] > 0 && k > 0 {
            let take = k.min(count[i]); count[i] -= take; count[i - 1] += take; k -= take
        }}
        (0..).zip(count).map(|(i, c)| c * i * i).sum()
    }