3505. Minimum Operations to Make Elements Within K Subarrays Equal

  • Array
  • Hash Table
  • Math
  • Dynamic Programming
  • Sliding Window
  • Heap (Priority Queue)
TIME
O(n log n + n * k)
SPACE
O(n)
problem on leetcode ↗source on github ↗

Intuition

The problem splits into two independent parts.

Making one window of x elements equal costs the sum of distances to its median, because the median minimises sum(|a - t|). So every window start s has a fixed price cost[s], and a sliding median gives all of them.

After that the values no longer matter. It's a selection problem: pick k non-overlapping intervals of length x with the smallest total price. Since k <= 15, a DP indexed by (windows used, prefix length) is small enough. Prices are never negative, so "at least k" and "exactly k" have the same answer.

Approach

Window costs.

  1. Sort the indices by (value, index) to give each element a unique rank, so the heaps can hold plain integers.
  2. Keep two heaps: lo (max-heap) with the lower half and hi (min-heap) with the upper half. Track how many live elements each has and their sums, and hold lo to ceil(x / 2) elements, so its top is the median.
  3. Removal is lazy. side[i] records which heap element i is in, so removing it only updates that heap's count and sum. Its entry is discarded when it reaches the top of a heap, recognised by its index being left of the window.
  4. With m as the median, cost = m * |lo| - sum(lo) + sum(hi) - m * |hi|.

Choosing windows.

  1. dp[j][i] = minimum cost of j windows inside the first i elements. dp[0][i] = 0, and dp[j][i] is infinite when i < j * x.
  2. Either no chosen window ends at i, or one does: dp[j][i] = min(dp[j][i-1], dp[j-1][i-x] + cost[i-x]).
  3. Only the previous row is needed. The answer is dp[k][n].

Complexity

  • Time: O(n log n + n * k): the sort and heap work are O(n log n) in total, since each slide moves at most a couple of elements between heaps and every stale entry is popped once, and the DP is O(n * k)
  • Space: O(n)

Edge Cases

  • k * x == n: the windows must fill the whole array, so there is exactly one choice
  • x == n, k == 1: a single window
  • x == 2: the two-element median is either element, and the cost is their difference
  • Even x: lo holds the lower middle, and any value between the two middles costs the same
  • Duplicate values: unique ranks stop equal elements from being confused during lazy removal
  • All windows already equal: answer 0
  • Negative values: only distances matter, and m * |lo| handles the sign correctly
  • A window can cost about 2 * 10^11, so Java uses long for sums and dp, and the infinity value must leave room for adding a cost without overflowing

Code

from typing import List
import heapq


class Solution:
    def minOperations(self, nums: List[int], x: int, k: int) -> int:
        """
        3505. Minimum Operations to Make Elements Within K Subarrays Equal
        Time: O(n log n + n * k)
        Space: O(n)
        """
        n = len(nums)

        # Unique ranks: order[r] is the index with rank r, so the heaps hold
        # plain ints and equal values stay distinguishable.
        order = sorted(range(n), key=lambda i: (nums[i], i))
        rank = [0] * n
        for r, i in enumerate(order):
            rank[i] = r

        # Sliding median. lo is a max-heap (negated ranks) of the lower half,
        # hi a min-heap of the upper half. Counts and sums cover live elements
        # only; an entry left of the window is dropped when it reaches a top.
        lo, hi = [], []
        lo_size = hi_size = lo_sum = hi_sum = 0
        side = [0] * n  # 0 = in lo, 1 = in hi
        left = 0

        def clean() -> None:
            while lo and order[-lo[0]] < left:
                heapq.heappop(lo)
            while hi and order[hi[0]] < left:
                heapq.heappop(hi)

        cost = [0] * (n - x + 1)
        for i in range(n):
            # Add nums[i] to the half it belongs in.
            clean()
            r = rank[i]
            if lo and r < -lo[0]:
                heapq.heappush(lo, -r)
                side[i] = 0
                lo_size += 1
                lo_sum += nums[i]
            else:
                heapq.heappush(hi, r)
                side[i] = 1
                hi_size += 1
                hi_sum += nums[i]

            # Drop the element leaving the window.
            if i >= x:
                out = i - x
                left = out + 1
                if side[out] == 0:
                    lo_size -= 1
                    lo_sum -= nums[out]
                else:
                    hi_size -= 1
                    hi_sum -= nums[out]

            # Rebalance so lo holds ceil(size / 2) live elements.
            clean()
            while lo_size > hi_size + 1:
                j = order[-heapq.heappop(lo)]
                heapq.heappush(hi, rank[j])
                side[j] = 1
                lo_size -= 1
                lo_sum -= nums[j]
                hi_size += 1
                hi_sum += nums[j]
                clean()
            while lo_size < hi_size:
                j = order[heapq.heappop(hi)]
                heapq.heappush(lo, -rank[j])
                side[j] = 0
                hi_size -= 1
                hi_sum -= nums[j]
                lo_size += 1
                lo_sum += nums[j]
                clean()

            if i >= x - 1:
                m = nums[order[-lo[0]]]
                cost[i - x + 1] = m * lo_size - lo_sum + hi_sum - m * hi_size

        # dp[i] = cheapest way to fit the current number of windows in the
        # first i elements.
        INF = float("inf")
        dp = [0] * (n + 1)
        for j in range(1, k + 1):
            ndp = [INF] * (n + 1)
            for i in range(j * x, n + 1):
                ndp[i] = min(ndp[i - 1], dp[i - x] + cost[i - x])
            dp = ndp

        return dp[n]