We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Make Elements Within K Subarrays Equal

Number: 3717

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an integer array nums and two integers x and k, you may increase or decrease any element by 1 per operation. Your goal is to achieve at least k non‑overlapping subarrays (contiguous segments) of exact size x such that within each chosen subarray all elements are identical. Compute the minimum number of operations required to achieve this configuration.

Key Insights

  • For any contiguous subarray of length x, the optimal way (in terms of minimizing total absolute differences) to make all numbers equal is to change every number to the median of the subarray.
  • Precompute the cost for every possible subarray of length x. For each such subarray starting at index i, the cost is the sum of absolute differences between each element in the subarray and its median.
  • Since the problem requires k non‑overlapping subarrays, a dynamic programming approach can be used:
    • Use a DP table where dp[i][j] represents the minimum cost to process the first i elements and have chosen j valid subarrays.
    • Transition by either skipping the current element or by “taking” a subarray starting at the current index (if it is possible to do so).
  • Because k is at most 15 and the number of candidate segments is roughly n, a O(n · k) DP is acceptable.

Space and Time Complexity

Time Complexity: O((n - x + 1) · (x · log(x)) + n · k).

  • The first term comes from precomputing the cost for each subarray (sorting each subarray of length x).
  • The second term is from the DP that iterates over n positions and up to k segments.
    Space Complexity: O(n · k) for the DP table plus O(n) for storing precomputed costs.

Solution

We start by precomputing the cost to convert every contiguous subarray of length x into one where all elements are equal. For a given subarray, the best target is its median (since the sum of absolute differences is minimized at the median). We then build a DP table dp[i][j] where i is the index in the array (from 0 to n) and j is the number of subarrays we have fixed so far. The transitions are:

  • Skip the current element: Update dp[i+1][j] = min(dp[i+1][j], dp[i][j]).
  • If a subarray starting at i exists (i+x ≤ n) and we have not yet chosen k segments: update dp[i+x][j+1] = min(dp[i+x][j+1], dp[i][j] + cost[i]). Finally, the answer is the minimum dp[i][k] over all i.

Key details include:

  • Computing the median efficiently for each window. For clarity in the sample solutions, each window’s cost is computed by sorting the subarray (this is acceptable because although worst-case could be heavy, k is small and in many cases x is much smaller than n, and when x is large the number of windows is small).
  • The fact that segments cannot overlap is enforced by moving the DP pointer i by x when a segment is “taken.”

Code Solutions

# Python solution with line-by-line comments
import math

def minOperations(nums, x, k):
    n = len(nums)
    # Precompute cost for every subarray of length x, for valid start indices 0..n-x
    costs = [0] * (n - x + 1)
    for start in range(n - x + 1):
        # Extract the current subarray of length x
        current_window = nums[start:start + x]
        # Copy and sort the window to get the median easily
        sorted_window = sorted(current_window)
        median = sorted_window[x // 2]
        # Calculate the cost to turn all numbers to the median
        cost = 0
        for num in current_window:
            cost += abs(num - median)
        costs[start] = cost

    # Initialize DP table: dp[i][j] means minimum cost using first i elements with j segments fixed.
    # We have n+1 positions and up to k segments, initialize all with infinity.
    INF = math.inf
    dp = [[INF] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 0

    # Process dp table. i is the current index in nums.
    for i in range(n + 1):
        for seg in range(k + 1):
            if dp[i][seg] == INF:
                continue
            # Option 1: Skip current element (if possible)
            if i < n:
                dp[i + 1][seg] = min(dp[i + 1][seg], dp[i][seg])
            # Option 2: Use a subarray starting at current index, if there is room and we haven't reached k segments
            if seg < k and i <= n - x:
                dp[i + x][seg + 1] = min(dp[i + x][seg + 1], dp[i][seg] + costs[i])
    
    # The answer is the minimum cost among all dp[i][k] for i from 0 to n.
    ans = min(dp[i][k] for i in range(n + 1))
    return ans

# Example usage:
print(minOperations([5,-2,1,3,7,3,6,4,-1], 3, 2))  # Expected output: 8 
print(minOperations([9,-2,-2,-2,1,5], 2, 2))       # Expected output: 3
← Back to All Questions