# Minimum Operations to Make Elements Within K Subarrays Equal
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-operations-to-make-elements-within-k-subarrays-equal)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-elements-within-k-subarrays-equal
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Hash Table, Heap (Priority Queue)
---
## 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:**

**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:**

**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 <= 105`
* `-106 <= nums[i] <= 106`
* `2 <= x <= nums.length`
* `1 <= k <= 15`
* `2 <= k * x <= nums.length`

# Approaches
## Dynamic Programming with Naive Cost Calculation
This approach involves two main stages. First, it pre-calculates the minimum operations (cost) required to make each possible subarray of size `x` have all equal elements. This is done naively by sorting each subarray to find its median and then summing the absolute differences. Second, it uses dynamic programming to determine the minimum total cost to select `k` non-overlapping subarrays from the calculated costs.
**Time:** O(n * x * log(x) + n * k) - The cost calculation step dominates. There are `O(n)` windows, and for each, we sort `x` elements, taking `O(x log x)`. The DP part takes `O(n*k)`. · **Space:** O(n*k) - We need `O(n)` space for the `costs` array and `O(n*k)` for the DP table.
**Pros:** The logic is straightforward and easy to understand.; It correctly separates the problem into two distinct subproblems: cost calculation and optimal selection.
**Cons:** The naive cost calculation is very slow, with a time complexity of `O(n * x * log(x))`, which will result in a 'Time Limit Exceeded' verdict for large `x`.
### Explanation
### Detailed Steps:

1.  **Pre-calculate Subarray Costs:**
    We create a `costs` array to store the cost for each potential subarray. For every starting index `i` from `0` to `n-x`, we consider the subarray `nums[i...i+x-1]`. The minimum operations to make all elements in this subarray equal is to change them all to the subarray's median. We find the median by sorting a copy of the subarray. The cost is the sum of absolute differences between each element and the median. This process is repeated for all `n-x+1` possible subarrays.

    ```java
    private long calculateCost(int[] nums, int start, int x) {
        int[] sub = new int[x];
        System.arraycopy(nums, start, sub, 0, x);
        Arrays.sort(sub);
        long median = sub[(x - 1) / 2];
        long cost = 0;
        for (int val : sub) {
            cost += Math.abs(val - median);
        }
        return cost;
    }
    ```

2.  **Dynamic Programming:**
    After computing all individual subarray costs, the problem reduces to selecting `k` non-overlapping entries from the `costs` array with minimum sum. Let `dp[i][j]` be the minimum cost to select `j` non-overlapping subarrays from the first `i` possible starting positions (`costs[0...i-1]`).

    The recurrence relation is:
    `dp[i][j] = min(dp[i-1][j], costs[i-1] + dp[i-x][j-1])`

    *   `dp[i-1][j]`: This corresponds to the case where we *do not* select the subarray starting at `i-1`.
    *   `costs[i-1] + dp[i-x][j-1]`: This corresponds to selecting the subarray starting at `i-1`. If we do, the previous `j-1` subarrays must be chosen from starting positions up to `i-1-x` to ensure they are non-overlapping.

    The final answer is the value in `dp[n-x+1][k]`.

    ```java
    // Part of the main function
    int m = n - x + 1;
    long[] costs = new long[m];
    for (int i = 0; i < m; i++) {
        costs[i] = calculateCost(nums, i, x);
    }

    long[][] dp = new long[m + 1][k + 1];
    long INF = Long.MAX_VALUE / 2;
    for (long[] row : dp) {
        Arrays.fill(row, INF);
    }
    for (int i = 0; i <= m; i++) {
        dp[i][0] = 0;
    }

    for (int j = 1; j <= k; j++) {
        for (int i = 1; i <= m; i++) {
            // Option 1: Don't take subarray starting at i-1
            long option1 = dp[i - 1][j];
            
            // Option 2: Take subarray starting at i-1
            long option2 = INF;
            if (i - x >= 0) {
                if (dp[i - x][j - 1] != INF) {
                    option2 = costs[i - 1] + dp[i - x][j - 1];
                }
            } else { // This can only be the first subarray chosen
                if (j == 1) {
                    option2 = costs[i - 1];
                }
            }
            dp[i][j] = Math.min(option1, option2);
        }
    }
    return dp[m][k];
    ```
### Algorithm
*   **Step 1: Pre-calculate Subarray Costs (Naively)**
    1.  Create a `costs` array of size `n - x + 1`.
    2.  Iterate from `i = 0` to `n - x`.
    3.  For each `i`, extract the subarray `nums[i...i+x-1]`.
    4.  Sort the subarray to find its median (element at index `(x-1)/2`).
    5.  Calculate the sum of absolute differences of each element from the median. This is `costs[i]`.
*   **Step 2: Dynamic Programming**
    1.  Create a 2D DP table `dp` of size `(n - x + 2) x (k + 1)`, initialized to a large value.
    2.  Set the base case: `dp[i][0] = 0` for all `i` (cost of 0 subarrays is 0).
    3.  Iterate `j` from `1` to `k` (number of subarrays).
    4.  Iterate `i` from `1` to `n - x + 1` (number of possible starting positions).
    5.  Calculate `dp[i][j]` using the recurrence: `dp[i][j] = min(dp[i-1][j], costs[i-1] + dp[i-x][j-1])`.
        *   `dp[i-1][j]` represents not selecting the subarray starting at `i-1`.
        *   `costs[i-1] + dp[i-x][j-1]` represents selecting the subarray at `i-1`. This is only possible if `i-x >= 0`.
    6.  The final answer is `dp[n-x+1][k]`.

## Dynamic Programming with Sliding Window Median
This approach significantly optimizes the bottleneck of the previous method. Instead of naively recalculating the cost for each subarray, it uses a sliding window approach with two heaps to find the median and cost in `O(log x)` time per slide. The dynamic programming part to select the `k` best subarrays remains the same but now operates on the efficiently pre-computed costs.
**Time:** O(n * log(x) + n * k) - `O(n log x)` for calculating all costs with the sliding window median and `O(n*k)` for the DP. · **Space:** O(n*k) - `O(x)` for the heaps, `O(n)` for the `costs` array, and `O(n*k)` for the DP table.
**Pros:** Highly efficient time complexity that passes the given constraints.; Effectively tackles the performance bottleneck of the naive approach.
**Cons:** Requires a more complex data structure (two heaps) for the sliding window median.; The DP table still consumes a large amount of memory, `O(n*k)`.
### Explanation
### Detailed Steps:

1.  **Efficient Cost Calculation with Sliding Window Median:**
    The main improvement is in calculating the `costs` array. We slide a window of size `x` across the `nums` array. To find the median of the elements in the window at each step efficiently, we use two heaps:
    *   A **max-heap** (`small`) to store the smaller half of the window's elements.
    *   A **min-heap** (`large`) to store the larger half.

    We keep the heaps balanced so that their sizes differ by at most 1. The median is always `large.peek()`. We also maintain the sum of elements in each heap to calculate the cost in `O(1)`. When the window slides, we remove one element and add another. These heap operations take `O(log x)` time. This reduces the total time for cost pre-calculation to `O(n log x)`.

    ```java
    // Note: In Java, PriorityQueue.remove(Object) is O(N). A true O(log N) removal
    // requires a more complex implementation (e.g., with a HashMap for lazy removal)
    // or using a balanced binary search tree (TreeMap).
    // The following snippet illustrates the idea but has O(x) removal time.
    private long[] calculateAllCosts(int[] nums, int x) {
        int n = nums.length;
        int m = n - x + 1;
        long[] costs = new long[m];
        
        // Two heaps for sliding window median
        PriorityQueue<Integer> small = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> large = new PriorityQueue<>();
        long smallSum = 0, largeSum = 0;

        // Helper to balance heaps
        Runnable balance = () -> {
            while (small.size() > large.size()) {
                int val = small.poll(); smallSum -= val;
                large.add(val); largeSum += val;
            }
            while (large.size() > small.size() + 1) {
                int val = large.poll(); largeSum -= val;
                small.add(val); smallSum += val;
            }
        };

        // Initial window
        for (int i = 0; i < x; i++) {
            small.add(nums[i]);
            smallSum += nums[i];
        }
        balance.run();

        // Sliding the window
        for (int i = 0; i < m; i++) {
            // Calculate cost for current window
            long median = large.peek();
            costs[i] = (median * small.size() - smallSum) + (largeSum - median * large.size());

            // Slide to next window
            if (i + x < n) {
                int toRemove = nums[i];
                int toAdd = nums[i + x];

                if (small.remove(toRemove)) smallSum -= toRemove;
                else if (large.remove(toRemove)) largeSum -= toRemove;

                if (!large.isEmpty() && toAdd >= large.peek()) {
                    large.add(toAdd); largeSum += toAdd;
                } else {
                    small.add(toAdd); smallSum += toAdd;
                }
                balance.run();
            }
        }
        return costs;
    }
    ```

2.  **Dynamic Programming:**
    This part is identical to Approach 1. We use the `costs` array generated above and fill the `dp[m+1][k+1]` table to find the minimum total cost. The time complexity for this part remains `O(n*k)`.
### Algorithm
*   **Step 1: Pre-calculate Subarray Costs (Efficiently)**
    1.  Create a `costs` array of size `n - x + 1`.
    2.  Use a sliding window of size `x` over `nums`.
    3.  Maintain two heaps (a max-heap for the smaller half, a min-heap for the larger half) to track elements in the window.
    4.  For the first window, populate the heaps and calculate `costs[0]`.
    5.  For subsequent windows, slide the window by removing the old element and adding the new one. Update the heaps in `O(log x)` time.
    6.  Calculate the cost for each window using the heaps' state and store it in the `costs` array.
*   **Step 2: Dynamic Programming**
    1.  This step is identical to the previous approach. Use the efficiently calculated `costs` array to fill the `O(n*k)` DP table.
    2.  The recurrence `dp[i][j] = min(dp[i-1][j], costs[i-1] + dp[i-x][j-1])` is used.
    3.  The final answer is `dp[n-x+1][k]`.

## Space-Optimized DP with Sliding Window Median
This is the most optimal solution, building upon the previous approach by optimizing its space complexity. It uses the same efficient `O(n log x)` sliding window median technique for cost calculation. However, it improves the dynamic programming stage by reducing the space from `O(n*k)` to `O(n)`. This is achieved by noticing that to compute the costs for `j` subarrays, we only need the results for `j-1` subarrays, not all `j-2, j-3, ...`.
**Time:** O(n * log(x) + n * k) - The time complexity is the same as the non-space-optimized version, as the logic remains identical. · **Space:** O(n + x) - `O(x)` for heaps, `O(n)` for the `costs` array, and `O(n)` for the two DP arrays.
**Pros:** Optimal time complexity for the given constraints.; Optimal space complexity, using `O(n)` space instead of `O(n*k)`.
**Cons:** The implementation is the most complex of the three approaches.; The logic for space-optimized DP requires careful state management.
### Explanation
### Detailed Steps:

1.  **Efficient Cost Calculation:**
    This step is identical to Approach 2. We generate the `costs` array in `O(n log x)` time using the sliding window median technique.

2.  **Space-Optimized Dynamic Programming:**
    The key insight is that the DP state `dp[i][j]` only depends on `dp[i-1][j]` and `dp[i-x][j-1]`. This means we only need to store the DP results for the current number of subarrays (`j`) and the previous one (`j-1`).

    We use two 1D arrays, `dp_prev` and `dp_curr`, of size `m+1` (where `m = n-x+1`).
    *   `dp_prev` stores the minimum costs for selecting `j-1` subarrays.
    *   `dp_curr` is used to compute the minimum costs for selecting `j` subarrays.

    The outer loop runs from `j = 1` to `k`. In each iteration, we compute `dp_curr` using `dp_prev`. At the end of the iteration, the content of `dp_curr` is copied to `dp_prev` to be used in the next iteration.

    ```java
    public long minOperations(int[] nums, int x, int k) {
        int n = nums.length;
        int m = n - x + 1;
        // Assume costs array is calculated efficiently as in Approach 2
        long[] costs = calculateAllCosts(nums, x); 

        long[] dpPrev = new long[m + 1]; // for j-1 subarrays
        long[] dpCurr = new long[m + 1]; // for j subarrays
        long INF = Long.MAX_VALUE / 2;

        // dpPrev is implicitly all 0s, for the base case j=0.

        for (int j = 1; j <= k; j++) {
            Arrays.fill(dpCurr, INF);
            for (int i = 1; i <= m; i++) {
                // Option 1: Don't take subarray starting at i-1
                long option1 = dpCurr[i - 1];
                
                // Option 2: Take subarray starting at i-1
                long option2 = INF;
                if (i - x >= 0) {
                    if (dpPrev[i - x] != INF) {
                        option2 = costs[i - 1] + dpPrev[i - x];
                    }
                } else { // This can only be the first subarray chosen
                    if (j == 1) {
                        option2 = costs[i - 1];
                    }
                }
                dpCurr[i] = Math.min(option1, option2);
            }
            // Prepare for next iteration: current becomes previous
            System.arraycopy(dpCurr, 0, dpPrev, 0, m + 1);
        }

        return dpPrev[m];
    }
    // calculateAllCosts function from Approach 2 would be needed here.
    ```
### Algorithm
*   **Step 1: Pre-calculate Subarray Costs (Efficiently)**
    1.  This step is identical to Approach 2. Use the sliding window with two heaps to compute the `costs` array in `O(n log x)` time.
*   **Step 2: Space-Optimized Dynamic Programming**
    1.  Observe that `dp[i][j]` only depends on `dp` values from column `j` and `j-1`.
    2.  Instead of a 2D DP table, use two 1D arrays: `dp_prev` (for `j-1` subarrays) and `dp_curr` (for `j` subarrays), each of size `n-x+2`.
    3.  Iterate `j` from `1` to `k`.
    4.  In each iteration, compute `dp_curr` using values from `dp_prev` and the already computed values of `dp_curr`.
        `dp_curr[i] = min(dp_curr[i-1], costs[i-1] + dp_prev[i-x])`.
    5.  After the inner loop over `i` completes, `dp_curr` becomes the new `dp_prev` for the next `j`.
    6.  The final answer is the last element of the DP array after `k` iterations.