Problem

You are given an integer array nums and two integers, x and k. You can perform the following operation any number of times (including zero):

  • Increase or decrease any element of nums by 1.

Return the minimum number of operations needed to have at least k non-overlapping subarrays of size exactly x in nums, where all elements within each subarray are equal.

Example 1

1
2
3
4
5
6

Input: nums = [5,-2,1,3,7,3,6,4,-1], x = 3, k = 2
Output: 8
Explanation:
* Use 3 operations to add 3 to `nums[1]` and use 2 operations to subtract 2 from `nums[3]`. The resulting array is `[5, 1, 1, 1, 7, 3, 6, 4, -1]`.
* Use 1 operation to add 1 to `nums[5]` and use 2 operations to subtract 2 from `nums[6]`. The resulting array is `[5, 1, 1, 1, 7, 4, 4, 4, -1]`.
* Now, all elements within each subarray `[1, 1, 1]` (from indices 1 to 3) and `[4, 4, 4]` (from indices 5 to 7) are equal. Since 8 total operations were used, 8 is the output.

Example 2

1
2
3
4
5

Input: nums = [9,-2,-2,-2,1,5], x = 2, k = 2
Output: 3
Explanation:
* Use 3 operations to subtract 3 from `nums[4]`. The resulting array is `[9, -2, -2, -2, -2, 5]`.
* Now, all elements within each subarray `[-2, -2]` (from indices 1 to 2) and `[-2, -2]` (from indices 3 to 4) are equal. Since 3 operations were used, 3 is the output.

Constraints

  • 2 <= nums.length <= 10^5
  • -10^6 <= nums[i] <= 10^6
  • 2 <= x <= nums.length
  • 1 <= k <= 15
  • 2 <= k * x <= nums.length

Examples

Solution

Method 1 – Sliding Window & Greedy (Heap)

Intuition

For each subarray of size x, the minimum operations to make all elements equal is to make them all equal to the median of the subarray. We need to select k non-overlapping subarrays with the lowest total cost.

Approach

  1. For every window of size x, calculate the cost to make all elements equal to its median.
  2. Use a heap to keep track of the k lowest costs among non-overlapping windows.
  3. Use dynamic programming to select k non-overlapping windows with minimum total cost.
  4. Edge case: If k * x > n, it’s impossible.

Code

 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

#include <queue>
class Solution {
public:
    int minOperations(vector<int>& nums, int x, int k) {
        int n = nums.size();
        vector<int> costs;
        for (int i = 0; i + x <= n; ++i) {
            vector<int> sub(nums.begin() + i, nums.begin() + i + x);
            sort(sub.begin(), sub.end());
            int med = sub[x/2];
            int cost = 0;
            for (int v : sub) cost += abs(v - med);
            costs.push_back(cost);
        }
        vector<vector<int>> dp(costs.size() + 1, vector<int>(k + 1, 1e9));
        dp[0][0] = 0;
        for (int i = 0; i < costs.size(); ++i) {
            for (int j = 0; j <= k; ++j) {
                dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
                if (j < k && i + x <= costs.size())
                    dp[i+x][j+1] = min(dp[i+x][j+1], dp[i][j] + costs[i]);
            }
        }
        return dp[costs.size()][k];
    }
};
 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

func minOperations(nums []int, x, k int) int {
    n := len(nums)
    costs := []int{}
    for i := 0; i+x <= n; i++ {
        sub := append([]int{}, nums[i:i+x]...)
        sort.Ints(sub)
        med := sub[x/2]
        cost := 0
        for _, v := range sub {
            if v > med { cost += v - med } else { cost += med - v }
        }
        costs = append(costs, cost)
    }
    dp := make([][]int, len(costs)+1)
    for i := range dp {
        dp[i] = make([]int, k+1)
        for j := range dp[i] { dp[i][j] = 1e9 }
    }
    dp[0][0] = 0
    for i := 0; i < len(costs); i++ {
        for j := 0; j <= k; j++ {
            if dp[i][j] < dp[i+1][j] { dp[i+1][j] = dp[i][j] }
            if j < k && i+x <= len(costs) {
                if dp[i][j]+costs[i] < dp[i+x][j+1] {
                    dp[i+x][j+1] = dp[i][j]+costs[i]
                }
            }
        }
    }
    return dp[len(costs)][k]
}
 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

class Solution {
    public int minOperations(int[] nums, int x, int k) {
        int n = nums.length;
        List<Integer> costs = new ArrayList<>();
        for (int i = 0; i + x <= n; i++) {
            int[] sub = Arrays.copyOfRange(nums, i, i + x);
            Arrays.sort(sub);
            int med = sub[x/2];
            int cost = 0;
            for (int v : sub) cost += Math.abs(v - med);
            costs.add(cost);
        }
        int[][] dp = new int[costs.size() + 1][k + 1];
        for (int[] row : dp) Arrays.fill(row, (int)1e9);
        dp[0][0] = 0;
        for (int i = 0; i < costs.size(); i++) {
            for (int j = 0; j <= k; j++) {
                dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j]);
                if (j < k && i + x <= costs.size())
                    dp[i+x][j+1] = Math.min(dp[i+x][j+1], dp[i][j] + costs.get(i));
            }
        }
        return dp[costs.size()][k];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun minOperations(nums: IntArray, x: Int, k: Int): Int {
        val n = nums.size
        val costs = mutableListOf<Int>()
        for (i in 0..n-x) {
            val sub = nums.slice(i until i+x).sorted()
            val med = sub[x/2]
            var cost = 0
            for (v in sub) cost += kotlin.math.abs(v - med)
            costs.add(cost)
        }
        val dp = Array(costs.size+1) { IntArray(k+1) { 1e9.toInt() } }
        dp[0][0] = 0
        for (i in 0 until costs.size) {
            for (j in 0..k) {
                dp[i+1][j] = minOf(dp[i+1][j], dp[i][j])
                if (j < k && i+x <= costs.size)
                    dp[i+x][j+1] = minOf(dp[i+x][j+1], dp[i][j] + costs[i])
            }
        }
        return dp[costs.size][k]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def minOperations(self, nums: list[int], x: int, k: int) -> int:
        n = len(nums)
        costs = []
        for i in range(n - x + 1):
            sub = sorted(nums[i:i+x])
            med = sub[x//2]
            cost = sum(abs(v - med) for v in sub)
            costs.append(cost)
        dp = [[float('inf')] * (k+1) for _ in range(len(costs)+1)]
        dp[0][0] = 0
        for i in range(len(costs)):
            for j in range(k+1):
                dp[i+1][j] = min(dp[i+1][j], dp[i][j])
                if j < k and i + x <= len(costs):
                    dp[i+x][j+1] = min(dp[i+x][j+1], dp[i][j] + costs[i])
        return dp[len(costs)][k]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn min_operations(nums: Vec<i32>, x: i32, k: i32) -> i32 {
        let n = nums.len();
        let mut costs = vec![];
        for i in 0..=n - x as usize {
            let mut sub = nums[i..i + x as usize].to_vec();
            sub.sort();
            let med = sub[x as usize / 2];
            let cost = sub.iter().map(|&v| (v - med).abs()).sum::<i32>();
            costs.push(cost);
        }
        let mut dp = vec![vec![i32::MAX / 2; (k + 1) as usize]; costs.len() + 1];
        dp[0][0] = 0;
        for i in 0..costs.len() {
            for j in 0..=k as usize {
                dp[i + 1][j] = dp[i + 1][j].min(dp[i][j]);
                if j < k as usize && i + x as usize <= costs.len() {
                    dp[i + x as usize][j + 1] = dp[i + x as usize][j + 1].min(dp[i][j] + costs[i]);
                }
            }
        }
        dp[costs.len()][k as usize]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    minOperations(nums: number[], x: number, k: number): number {
        const n = nums.length;
        const costs: number[] = [];
        for (let i = 0; i + x <= n; i++) {
            const sub = nums.slice(i, i + x).sort((a, b) => a - b);
            const med = sub[Math.floor(x / 2)];
            let cost = 0;
            for (const v of sub) cost += Math.abs(v - med);
            costs.push(cost);
        }
        const dp = Array(costs.length + 1).fill(0).map(() => Array(k + 1).fill(Infinity));
        dp[0][0] = 0;
        for (let i = 0; i < costs.length; i++) {
            for (let j = 0; j <= k; j++) {
                dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j]);
                if (j < k && i + x <= costs.length) {
                    dp[i + x][j + 1] = Math.min(dp[i + x][j + 1], dp[i][j] + costs[i]);
                }
            }
        }
        return dp[costs.length][k];
    }
}

Complexity

  • ⏰ Time complexity: O(n * x * k) — For each window, we sort and compute cost, and DP for k subarrays.
  • 🧺 Space complexity: O(n * k) — DP table and costs array.