3505. Minimum Operations to Make Elements Within K Subarrays Equal

HardView on LeetCode

Array Dynamic Programming Sliding Window Binary Indexed Tree

Time: O(n log n + n * k)

Space: O(n)

Problem Overview

Each chosen block has fixed length x, the blocks cannot overlap, and every value inside a block must finish equal.

Intuition

Each chosen block has fixed length x, the blocks cannot overlap, and every value inside a block must finish equal. The cheapest target for one block is its median, so the cost of a window is the total absolute gap from that median. Sliding windows of length x share almost the same multiset, so the costs are built once while the window moves. Values are compressed to ranks. Two Fenwick trees store how many window values sit at each rank and what those values sum to. Binary lifting on the count tree finds the rank of the ((x + 1) / 2) th element, which is the median used for that window. The cost formula splits the window into the values below that rank and the rest, including ties on the median itself. After every start index has a cost, choosing k non overlapping windows is a short DP because k is at most 15. One row holds the best score with the previous window count, and the next row either skips the current end or places a window that ends there.

Algorithm

1Sort a copy of the array and keep each distinct value once. Map every original element to its 1 based rank.
2Load the first window of length x into the count and sum Fenwick trees, and keep the window total.
3For each window start, lift on the count tree to the median rank, score the absolute gaps, then slide the window one step.
4Run a DP with k layers. At end index i, either keep the previous best for the same window count or add the cost of the window that ends at i.
5Return the best score that uses exactly k windows on the full array.

Example Walkthrough

Input: nums = [5, -2, 1, 3, 7, 3, 6, 4, -1], x = 3, k = 2

1.Each length 3 window is scored by its distance to its median.
2.Two non overlapping windows are chosen from those starts.
3.The cheapest pair of windows costs 8 operations in total.

Output: 8

Common Pitfalls

•The median rank is ((x + 1) / 2), which matches a lower half that is never smaller than the upper half.
•Equal values share one rank. Values equal to the median still contribute 0 to the absolute gap formula.
•Products of a median and a count must use 64 bit arithmetic.
•The DP rows must be swapped after each window count. Reusing one row in place mixes the previous count with the current count.

3505.cs

// Approach: The cheapest way to equalize a window of length x is to move
// every value to its median. Values are ranked, and two Fenwick trees track
// the count and the sum at each rank inside the sliding window. Binary
// lifting on the count tree finds the median rank, so each window cost is
// a logarithmic update. Two rolling rows then choose k non overlapping
// windows. Products that build a cost stay in 64 bit integers.
// Time: O(n log n + n * k) Space: O(n)

public class Solution
{
    private const long Inf = long.MaxValue / 4;

    public long MinOperations(int[] nums, int x, int k)
    {
        int n = nums.Length;
        int[] values = (int[])nums.Clone();
        Array.Sort(values);
        int unique = 0;
        for (int i = 0; i < n; i++)
        {
            if (unique == 0 || values[i] != values[unique - 1])
                values[unique++] = values[i];
        }

        int[] ranks = new int[n];
        for (int i = 0; i < n; i++)
            ranks[i] = Array.BinarySearch(values, 0, unique, nums[i]) + 1;

        int[] counts = new int[unique + 1];
        long[] sums = new long[unique + 1];
        long total = 0;
        for (int i = 0; i < x; i++)
        {
            Add(counts, sums, ranks[i], nums[i], 1);
            total += nums[i];
        }

        int jump = 1;
        while ((jump << 1) <= unique)
            jump <<= 1;

        int windowCount = n - x + 1;
        long[] costs = new long[windowCount];
        for (int left = 0; left < windowCount; left++)
        {
            int rank = FindMedian(counts, sums, (x + 1) >> 1, jump, out int belowCount, out long belowSum);
            long median = values[rank - 1];
            int rightCount = x - belowCount;
            long rightSum = total - belowSum;
            costs[left] = median * belowCount - belowSum + rightSum - median * rightCount;

            if (left + 1 < windowCount)
            {
                Add(counts, sums, ranks[left], nums[left], -1);
                Add(counts, sums, ranks[left + x], nums[left + x], 1);
                total += (long)nums[left + x] - nums[left];
            }
        }

        long[] prev = new long[n + 1];
        long[] curr = new long[n + 1];
        for (int group = 1; group <= k; group++)
        {
            curr[0] = Inf;
            for (int i = 1; i <= n; i++)
            {
                long best = curr[i - 1];
                if (i >= x)
                    best = Math.Min(best, prev[i - x] + costs[i - x]);
                curr[i] = best;
            }
            (prev, curr) = (curr, prev);
        }
        return prev[n];
    }

    private static void Add(int[] counts, long[] sums, int index, int value, int delta)
    {
        while (index < counts.Length)
        {
            counts[index] += delta;
            sums[index] += (long)value * delta;
            index += index & -index;
        }
    }

    private static int FindMedian(int[] counts, long[] sums, int target, int jump, out int belowCount, out long belowSum)
    {
        int index = 0;
        belowCount = 0;
        belowSum = 0;
        while (jump > 0)
        {
            int next = index + jump;
            if (next < counts.Length && belowCount + counts[next] < target)
            {
                index = next;
                belowCount += counts[next];
                belowSum += sums[next];
            }
            jump >>= 1;
        }
        return index + 1;
    }
}

Was this solution helpful?