Understanding the Median-Based Optimization
Introduction
When solving array transformation problems, a common challenge is minimizing the number of operations required to make elements equal. This problem asks us to determine, for every prefix of a sorted array, the minimum number of increment or decrement operations needed to make all elements in that prefix equal.
At first glance, the problem may seem like a brute-force optimization task. However, a key mathematical observation allows us to solve it efficiently in linear time.
Consider the array:
[1, 6, 9, 12]
For every index i, we examine the prefix from 0 to i.
For i = 2, the prefix becomes:
[1, 6, 9]
We need to make all elements equal while minimizing the total number of operations.
An operation consists of either increasing or decreasing an element by 1.
If we choose a target value of 6:
|1 - 6| + |6 - 6| + |9 - 6|
= 5 + 0 + 3
= 8
The total cost is 8.
The question is: how do we know that 6 is the best value to choose?
The answer comes from an important mathematical property.
For a set of numbers, the value that minimizes the sum of absolute differences is the median.
For example:
[1, 6, 9]
Median = 6
Cost at 6:
5 + 0 + 3 = 8
Cost at 5:
4 + 1 + 4 = 9
Cost at 7:
6 + 1 + 2 = 9
The median produces the minimum possible cost.
Since the given array is already sorted, finding the median of any prefix becomes extremely easy.
For a prefix ending at index i:
mid = i / 2
The median is simply:
arr[mid]
A beginner might now think that we can compute the answer by iterating through every element in every prefix and calculating distances from the median.
While correct, that approach would require:
O(1 + 2 + 3 + ... + n)
= O(n²)
With n = 100000, this would be far too slow.
We need a faster way.
Breaking Down the Cost
Let's examine how the cost is formed.
Assume:
Prefix = [1, 6, 9, 12]
Median = 6
The total cost is:
(6 - 1) + (6 - 6) + (9 - 6) + (12 - 6)
Since the array is sorted, all elements before the median are less than or equal to the median.
Similarly, all elements after the median are greater than or equal to the median.
This allows us to split the cost into two parts.
Left Side Contribution
Median * CountLeft - SumLeft
Right Side Contribution
SumRight - Median * CountRight
Combining them gives:

Join the conversation! Your thoughts help the community grow.