Equalize All Prefix Sums

Time: O(n)

Space: O(n)

Problem Overview

For each prefix arr[0..i], the optimal target to minimize total adjustment cost is the middle element arr[j] where j = floor(i/2).

Intuition

For each prefix arr[0..i], the optimal target to minimize total adjustment cost is the middle element arr[j] where j = floor(i/2). Split the prefix into a left segment [0..j] and right segment [j+1..i]. The cost to make every element equal to arr[j] is the sum of absolute differences on both sides, computed in O(1) with running prefix sums.

Algorithm

1Maintain sumUpToI (prefix sum through index i) and sumUpToHalf (prefix sum through j = i/2).
2When i is even, extend sumUpToHalf by arr[i/2] and set j = i/2.
3Let midEle = arr[j], leftSize = j + 1, rightSize = i - j.
4leftCost = |midEle * leftSize - sumUpToHalf|.
5rightCost = |(sumUpToI - sumUpToHalf) - midEle * rightSize|.
6Append leftCost + rightCost to the answer for this prefix.

Example Walkthrough

Input: arr = [2, 4, 6]

1. i = 0: j = 0, single element → cost 0.
2. i = 1: j = 0, left [2] cost 0, right [4] needs |4 − 2| = 2 → total 2.
3. i = 2: j = 1, left [2,4] with target 4 costs |6 − 8| = 2, right [6] costs |6 − 4| = 2 → total 4.

Output: [0, 2, 4]

Common Pitfalls

• Extend sumUpToHalf only on even i — j stays floor(i/2) on odd indices.
• rightWindowSum = sumUpToI − sumUpToHalf, not a separate loop.
• Use long if values are large enough to overflow int products.

Equalize All Prefix Sums.java

Java

// Approach: For each prefix ending at index i, pick the middle index j = i / 2 and use arr[j] as the target value.
// Minimum cost to make every element in the prefix equal to arr[j] is the sum of absolute differences on the left [0..j] and right [j+1..i] segments.
// Maintain prefix sums so left and right segment sums are O(1) per index; extend the left sum when i is even.
// Time: O(n) Space: O(n) for the result list
import java.util.*;

class Solution {

    public ArrayList<Integer> optimalArray(int[] arr) {
        int sum_up_to_i = 0;
        int sum_up_to_half_i = 0;

        int n = arr.length;
        int j = 0;

        ArrayList<Integer> result = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (i % 2 == 0 && i / 2 >= 0) {
                sum_up_to_half_i += arr[i / 2];
                j = i / 2;
            }
            sum_up_to_i += arr[i];

            int midEle = arr[i / 2];

            int rightWindowSize = (i - j);
            int leftWindowSize = j + 1;

            int rightWindowSum = sum_up_to_i - sum_up_to_half_i;
            int leftWindowSum = sum_up_to_half_i;

            int rightWindowCost = Math.abs(rightWindowSum - midEle * rightWindowSize);
            int leftWindowcost = Math.abs(midEle * leftWindowSize - leftWindowSum);

            int totalOperationCost = rightWindowCost + leftWindowcost;

            result.add(totalOperationCost);

        }
        return result;
    }
}

Was this solution helpful?