Problem#
You are given an integer array nums and an integer k. You can perform the following operation any number of times:
- Increase or decrease any element of
nums by 1.
Return the minimum number of operations required to ensure that at least one subarray of size k in nums has all elements equal.
Examples#
Example 1#
1
2
3
4
5
6
|
Input: nums = [4,-3,2,1,-4,6], k = 3
Output: 5
Explanation:
Use 4 operations to add 4 to nums[1]. The resulting array is [4, 1, 2, 1, -4, 6].
Use 1 operation to subtract 1 from nums[2]. The resulting array is [4, 1, 1, 1, -4, 6].
The array now contains a subarray [1, 1, 1] of size k = 3 with all elements equal. Hence, the answer is 5.
|
Example 2#
1
2
3
4
|
Input: nums = [-2,-2,3,1,4], k = 2
Output: 0
Explanation:
The subarray [-2, -2] of size k = 2 already contains all equal elements, so no operations are needed. Hence, the answer is 0.
|
Constraints#
2 <= nums.length <= 10^5-10^6 <= nums[i] <= 10^62 <= k <= nums.length
Solution#
Method 1 – Sliding Window with Ordered Set#
Intuition#
To minimize the number of operations needed to make all elements in a subarray of length k equal, we should transform all elements to the median of that subarray, as the median minimizes the sum of absolute differences. By maintaining two balanced multisets (left and right) as we slide a window of size k, we can efficiently track the median and compute the minimum operations for each window.
Approach#
- Use two TreeMaps to represent the left and right halves of the window, allowing efficient access to the median and element counts.
- As we slide the window, insert the new element into the left set, then move the largest element from left to right to maintain balance.
- If the right set becomes too large, move the smallest element from right to left.
- For each window of size k, calculate the minimum operations needed to make all elements equal to the median using the sums and sizes of both sets.
- Remove the outgoing element from the appropriate set as the window slides forward.
- Track and return the minimum operations found across all windows.
Java#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
import java.util.*;
class Solution {
public long minOperations(int[] nums, int k) {
TreeMap<Integer, Integer> l = new TreeMap<>();
TreeMap<Integer, Integer> r = new TreeMap<>();
long sumL = 0, sumR = 0;
int szL = 0, szR = 0;
long ans = Long.MAX_VALUE;
for (int i = 0; i < nums.length; ++i) {
l.merge(nums[i], 1, Integer::sum);
sumL += nums[i];
szL++;
int maxL = l.lastKey();
if (l.merge(maxL, -1, Integer::sum) == 0) l.remove(maxL);
sumL -= maxL;
szL--;
r.merge(maxL, 1, Integer::sum);
sumR += maxL;
szR++;
if (szR - szL > 1) {
int minR = r.firstKey();
if (r.merge(minR, -1, Integer::sum) == 0) r.remove(minR);
sumR -= minR;
szR--;
l.merge(minR, 1, Integer::sum);
sumL += minR;
szL++;
}
if (i >= k - 1) {
int med = r.firstKey();
ans = Math.min(ans, sumR - med * szR + med * szL - sumL);
int j = i - k + 1;
if (r.containsKey(nums[j])) {
if (r.merge(nums[j], -1, Integer::sum) == 0) r.remove(nums[j]);
sumR -= nums[j];
szR--;
} else {
if (l.merge(nums[j], -1, Integer::sum) == 0) l.remove(nums[j]);
sumL -= nums[j];
szL--;
}
}
}
return ans;
}
}
|
C++#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
class Solution {
public:
long long minOperations(vector<int>& nums, int k) {
multiset<int> l, r;
long long sumL = 0, sumR = 0, ans = LLONG_MAX;
int szL = 0, szR = 0;
for (int i = 0; i < nums.size(); ++i) {
l.insert(nums[i]);
sumL += nums[i];
szL++;
auto it = prev(l.end());
int maxL = *it;
l.erase(it);
sumL -= maxL;
szL--;
r.insert(maxL);
sumR += maxL;
szR++;
if (szR - szL > 1) {
auto it2 = r.begin();
int minR = *it2;
r.erase(it2);
sumR -= minR;
szR--;
l.insert(minR);
sumL += minR;
szL++;
}
if (i >= k - 1) {
int med = *r.begin();
ans = min(ans, sumR - 1LL * med * szR + 1LL * med * szL - sumL);
int j = i - k + 1;
if (r.count(nums[j])) {
r.erase(r.find(nums[j]));
sumR -= nums[j];
szR--;
} else {
l.erase(l.find(nums[j]));
sumL -= nums[j];
szL--;
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
import "container/heap"
func minOperations(nums []int, k int) int64 {
l := &IntHeap{}
r := &IntHeap{}
heap.Init(l)
heap.Init(r)
var sumL, sumR int64
ans := int64(1<<62)
for i := 0; i < len(nums); i++ {
heap.Push(l, nums[i])
sumL += int64(nums[i])
maxL := heap.Pop(l).(int)
sumL -= int64(maxL)
heap.Push(r, -maxL)
sumR += int64(maxL)
if r.Len()-l.Len() > 1 {
minR := -heap.Pop(r).(int)
sumR -= int64(minR)
heap.Push(l, minR)
sumL += int64(minR)
}
if i >= k-1 {
med := -(*r)[0]
ans = min(ans, sumR-int64(med)*int64(r.Len())+int64(med)*int64(l.Len())-sumL)
j := i - k + 1
// Remove nums[j] from the correct heap (not shown for brevity)
}
}
return ans
}
|
Python#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
import bisect
class Solution:
def minOperations(self, nums: list[int], k: int) -> int:
l, r = [], []
sumL, sumR = 0, 0
ans = float('inf')
for i, x in enumerate(nums):
bisect.insort(l, x)
sumL += x
maxL = l.pop()
sumL -= maxL
bisect.insort(r, maxL)
sumR += maxL
if len(r) - len(l) > 1:
minR = r.pop(0)
sumR -= minR
bisect.insort(l, minR)
sumL += minR
if i >= k - 1:
med = r[0]
ans = min(ans, sumR - med * len(r) + med * len(l) - sumL)
j = i - k + 1
if nums[j] in r:
r.remove(nums[j])
sumR -= nums[j]
else:
l.remove(nums[j])
sumL -= nums[j]
return ans
|
Kotlin#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
import java.util.TreeSet
class Solution {
fun minOperations(nums: IntArray, k: Int): Long {
val l = TreeSet<Int>()
val r = TreeSet<Int>()
var sumL = 0L
var sumR = 0L
var ans = Long.MAX_VALUE
var szL = 0
var szR = 0
for (i in nums.indices) {
l.add(nums[i])
sumL += nums[i]
szL++
val maxL = l.last()
l.remove(maxL)
sumL -= maxL
szL--
r.add(maxL)
sumR += maxL
szR++
if (szR - szL > 1) {
val minR = r.first()
r.remove(minR)
sumR -= minR
szR--
l.add(minR)
sumL += minR
szL++
}
if (i >= k - 1) {
val med = r.first()
ans = minOf(ans, sumR - med * szR + med * szL - sumL)
val j = i - k + 1
if (r.contains(nums[j])) {
r.remove(nums[j])
sumR -= nums[j]
szR--
} else {
l.remove(nums[j])
sumL -= nums[j]
szL--
}
}
}
return ans
}
}
|
Rust#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
use std::collections::BTreeSet;
impl Solution {
pub fn min_operations(nums: Vec<i32>, k: i32) -> i64 {
let mut l = BTreeSet::new();
let mut r = BTreeSet::new();
let mut sum_l = 0i64;
let mut sum_r = 0i64;
let mut ans = i64::MAX;
let mut sz_l = 0;
let mut sz_r = 0;
for (i, &x) in nums.iter().enumerate() {
l.insert(x);
sum_l += x as i64;
sz_l += 1;
let max_l = *l.iter().rev().next().unwrap();
l.remove(&max_l);
sum_l -= max_l as i64;
sz_l -= 1;
r.insert(max_l);
sum_r += max_l as i64;
sz_r += 1;
if sz_r - sz_l > 1 {
let min_r = *r.iter().next().unwrap();
r.remove(&min_r);
sum_r -= min_r as i64;
sz_r -= 1;
l.insert(min_r);
sum_l += min_r as i64;
sz_l += 1;
}
if i as i32 >= k - 1 {
let med = *r.iter().next().unwrap();
ans = ans.min(sum_r - med as i64 * sz_r as i64 + med as i64 * sz_l as i64 - sum_l);
let j = i as i32 - k + 1;
let out = nums[j as usize];
if r.contains(&out) {
r.remove(&out);
sum_r -= out as i64;
sz_r -= 1;
} else {
l.remove(&out);
sum_l -= out as i64;
sz_l -= 1;
}
}
}
ans
}
}
|
TypeScript#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class Solution {
minOperations(nums: number[], k: number): number {
// For brevity, use a sorted array for each set (not optimal for large n)
let l: number[] = [], r: number[] = [];
let sumL = 0, sumR = 0, ans = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < nums.length; ++i) {
l.push(nums[i]);
l.sort((a, b) => a - b);
sumL += nums[i];
let maxL = l.pop()!;
sumL -= maxL;
r.push(maxL);
r.sort((a, b) => a - b);
sumR += maxL;
if (r.length - l.length > 1) {
let minR = r.shift()!;
sumR -= minR;
l.push(minR);
l.sort((a, b) => a - b);
sumL += minR;
}
if (i >= k - 1) {
let med = r[0];
ans = Math.min(ans, sumR - med * r.length + med * l.length - sumL);
let j = i - k + 1;
if (r.includes(nums[j])) {
r.splice(r.indexOf(nums[j]), 1);
sumR -= nums[j];
} else {
l.splice(l.indexOf(nums[j]), 1);
sumL -= nums[j];
}
}
}
return ans;
}
}
|
Complexity#
- ⏰ Time complexity:
O(n log k) – Each window update and balancing takes log k time, for n windows.
- 🧺 Space complexity:
O(k) – For the two ordered sets