Skip to main content
Talentd

Minimum Operations to Make Subarray Elements Equal - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableMathSliding Window9 min read
Practice this problem

Problem Statement

You are given an integer array nums and an integer k. You can perform the following operation any number of times:

  • Increase or decrease any element of nums by 1.

Return the minimum number of operations required to ensure that at least one subarray of size k in nums has all elements equal.

 

Example 1:

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

Output: 5

Explanation:

  • Use 4 operations to add 4 to nums[1]. The resulting array is [4, 1, 2, 1, -4, 6].
  • Use 1 operation to subtract 1 from nums[2]. The resulting array is [4, 1, 1, 1, -4, 6].
  • The array now contains a subarray [1, 1, 1] of size k = 3 with all elements equal. Hence, the answer is 5.

Example 2:

Input: nums = [-2,-2,3,1,4], k = 2

Output: 0

Explanation:

  • The subarray [-2, -2] of size k = 2 already contains all equal elements, so no operations are needed. Hence, the answer is 0.

 

Constraints:

  • 2 <= nums.length <= 105
  • -106 <= nums[i] <= 106
  • 2 <= k <= nums.length

Approach Overview

Problem Overview: You are given an integer array and a fixed window size k. For every subarray of length k, compute the minimum number of operations required to make all elements equal, where one operation increments or decrements a value by 1. The goal is to return the minimum cost among all possible windows.

Approach 1: Sort Every Window (Brute Force) (Time: O(n * k log k), Space: O(k))

Iterate over every contiguous subarray of length k. Copy the window, sort it, and pick the median element as the target value because the median minimizes the sum of absolute differences. Compute the cost by summing |nums[i] - median| for each element in the window. This method is straightforward but inefficient since sorting happens for every window. It works for small constraints but becomes too slow when n or k grows.

Approach 2: Sliding Window with Ordered Set / Two Heaps (Time: O(n log k), Space: O(k))

Use a sliding window of size k and maintain the median dynamically using two balanced structures. A common implementation uses two heaps (max‑heap for the left half and min‑heap for the right half) or an ordered multiset. The median stays at the top of the left heap. Track the sum of elements in both halves so the total cost can be computed in constant time using the formula derived from median distance.

When the window expands, insert the new value into the appropriate heap and rebalance to keep sizes valid. When the window slides forward, remove the outgoing element and rebalance again. Using maintained sums, compute the cost as the distance from the median to all elements on both sides. Each insert or remove operation costs O(log k), giving an overall complexity of O(n log k). This pattern frequently appears in problems involving median maintenance with heap or ordered structures over an array.

Recommended for interviews: Start by explaining why the median minimizes the sum of absolute differences in a window. Mention the brute force approach to show baseline understanding, then move to the sliding window with heaps or ordered set. Interviewers expect the O(n log k) solution because it demonstrates strong control over window maintenance, median tracking, and efficient data structures.

Solution

According to the problem description, we need to find a subarray of length k and make all elements in the subarray equal with the minimum number of operations. That is, we need to find a subarray of length k such that the minimum number of operations required to make all elements in the subarray equal to the median of these k elements is minimized.

We can use two ordered sets l and r to maintain the left and right parts of the k elements, respectively. l is used to store the smaller part of the k elements, and r is used to store the larger part of the k elements. The number of elements in l is either equal to the number of elements in r or one less than the number of elements in r, so the minimum value in r is the median of the k elements.

The time complexity is O(n times log k), and the space complexity is O(k). Here, n is the length of the array nums.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sort Every Window (Brute Force)O(n * k log k)O(k)Small inputs or when demonstrating the median insight first
Sliding Window with Ordered Set / Two HeapsO(n log k)O(k)General optimal solution when the window moves across the array

Frequently Asked Questions

Is Minimum Operations to Make Subarray Elements Equal easy or hard?
Minimum Operations to Make Subarray Elements Equal is considered a Medium difficulty problem. The challenge comes from combining sliding window mechanics with dynamic median maintenance and efficient cost calculation.
Minimum Operations to Make Subarray Elements Equal Python/Java solution
In Python, the solution typically uses two heaps with lazy deletion or a balanced structure like SortedList. In Java and C++, developers often use priority queues or ordered multisets to maintain the two halves of the window and compute costs efficiently.
How to solve Minimum Operations to Make Subarray Elements Equal in O(n log k)?
Maintain a sliding window of length k and keep the median using two heaps (max heap for the lower half and min heap for the upper half). Track the sum of elements in both halves so the cost relative to the median can be computed quickly. When the window moves, insert the new element, remove the outgoing element, rebalance the heaps, and recompute the cost.
What is the best approach for Minimum Operations to Make Subarray Elements Equal?
The best approach uses a sliding window of size k combined with median maintenance using two heaps or an ordered multiset. The median minimizes the total absolute difference required to make all elements equal. By maintaining the median while the window slides, you can compute the cost in O(log k) per step, resulting in O(n log k) total time.
Is Minimum Operations to Make Subarray Elements Equal asked at Google/Amazon/Meta?
Problems involving sliding window medians and minimizing absolute differences appear frequently in interviews at companies like Google, Amazon, and Meta. Variants include maintaining a running median or minimizing operations using the median property.
What data structure is used in Minimum Operations to Make Subarray Elements Equal?
The optimal implementation uses two heaps (a max heap and a min heap) or an ordered multiset. These structures allow efficient median tracking and O(log k) insertion and deletion as the sliding window moves.
What is the time complexity of Minimum Operations to Make Subarray Elements Equal?
The optimal solution runs in O(n log k) time and O(k) space. Each sliding window update inserts and removes one element from a balanced structure such as heaps or an ordered set, both of which require O(log k) time.

Ready to solve this problem?

Practice Minimum Operations to Make Subarray Elements Equal with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Median from Data Stream

Next

Minimum Moves to Equal Array Elements II