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)
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.
- Sort the indices by
(value, index)to give each element a unique rank, so the heaps can hold plain integers. - Keep two heaps:
lo(max-heap) with the lower half andhi(min-heap) with the upper half. Track how many live elements each has and their sums, and holdlotoceil(x / 2)elements, so its top is the median. - Removal is lazy.
side[i]records which heap elementiis 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. - With
mas the median,cost = m * |lo| - sum(lo) + sum(hi) - m * |hi|.
Choosing windows.
dp[j][i]= minimum cost ofjwindows inside the firstielements.dp[0][i] = 0, anddp[j][i]is infinite wheni < j * x.- 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]). - 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 choicex == n,k == 1: a single windowx == 2: the two-element median is either element, and the cost is their difference- Even
x:loholds 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 useslongfor sums anddp, 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]import java.util.*;
/**
* 3505. Minimum Operations to Make Elements Within K Subarrays Equal
* Time: O(n log n + n * k)
* Space: O(n)
*/
class Solution {
private int[] order;
private PriorityQueue<Integer> lo, hi;
private int left;
public long minOperations(int[] nums, int x, int k) {
int n = nums.length;
// Unique ranks: order[r] is the index with rank r, so the heaps hold
// plain ints and equal values stay distinguishable.
long[] keyed = new long[n];
for (int i = 0; i < n; i++) {
keyed[i] = ((long) nums[i] << 17) | i;
}
Arrays.sort(keyed);
order = new int[n];
int[] rank = new int[n];
for (int r = 0; r < n; r++) {
order[r] = (int) (keyed[r] & ((1 << 17) - 1));
rank[order[r]] = r;
}
// Sliding median. lo is a max-heap 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 = new PriorityQueue<>(Comparator.reverseOrder());
hi = new PriorityQueue<>();
int loSize = 0, hiSize = 0;
long loSum = 0, hiSum = 0;
boolean[] inHi = new boolean[n];
left = 0;
long[] cost = new long[n - x + 1];
for (int i = 0; i < n; i++) {
// Add nums[i] to the half it belongs in.
clean();
if (!lo.isEmpty() && rank[i] < lo.peek()) {
lo.add(rank[i]);
inHi[i] = false;
loSize++;
loSum += nums[i];
} else {
hi.add(rank[i]);
inHi[i] = true;
hiSize++;
hiSum += nums[i];
}
// Drop the element leaving the window.
if (i >= x) {
int out = i - x;
left = out + 1;
if (inHi[out]) {
hiSize--;
hiSum -= nums[out];
} else {
loSize--;
loSum -= nums[out];
}
}
// Rebalance so lo holds ceil(size / 2) live elements.
clean();
while (loSize > hiSize + 1) {
int r = lo.poll(), j = order[r];
hi.add(r);
inHi[j] = true;
loSize--;
loSum -= nums[j];
hiSize++;
hiSum += nums[j];
clean();
}
while (loSize < hiSize) {
int r = hi.poll(), j = order[r];
lo.add(r);
inHi[j] = false;
hiSize--;
hiSum -= nums[j];
loSize++;
loSum += nums[j];
clean();
}
if (i >= x - 1) {
long m = nums[order[lo.peek()]];
cost[i - x + 1] = m * loSize - loSum + hiSum - m * hiSize;
}
}
// dp[i] = cheapest way to fit the current number of windows in the
// first i elements.
long inf = Long.MAX_VALUE / 2;
long[] dp = new long[n + 1];
for (int j = 1; j <= k; j++) {
long[] next = new long[n + 1];
Arrays.fill(next, inf);
for (int i = j * x; i <= n; i++) {
next[i] = Math.min(next[i - 1], dp[i - x] + cost[i - x]);
}
dp = next;
}
return dp[n];
}
private void clean() {
while (!lo.isEmpty() && order[lo.peek()] < left) {
lo.poll();
}
while (!hi.isEmpty() && order[hi.peek()] < left) {
hi.poll();
}
}
}