Minimize cost of operation to equalize tower heights

Given the heights of n towers in the array heights[], the task is to make all towers the same height by either adding or removing blocks.
Each addition or removal operation has a different cost for each tower, specified in the array cost[].
The objective is to minimize the total cost required to equalize the heights of all towers.

Examples:

Input: heights[] = [1, 2, 3], cost[] = [10, 100, 1000]
Output: 120
Explanation: We try all possible target heights and calculate the cost to make all towers equal to that height. The minimum cost comes when we raise tower 1 by 2 and tower 2 by 1, totaling 120, which is the lowest among all options.

Input: heights[] = [7, 1, 5], cost[] = [1, 1, 1]
Output: 6
Explanation: 1 * abs(7-5) + 1 * abs(1-5) + 1 * abs(5-5) = 6
(Taking 5 as final height)

Try it on GfG Practice

Table of Content

[Naive Approach] Check All Possibilities – O(n^2) Time and O(1) Space
[Expected Approach] Binary Search – O(n × log2(max(heights[i]) - min(heights[i])) Time and O(1) Space
[Alternate Approach] Ternary Search

[Naive Approach] Check All Possibilities – O(n^2) Time and O(1) Space

The idea is to iterate through each tower, and find the total cost of making heights of all towers to current tower. If total cost is less than current result, update the result.

C++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int minCost(vector<int> &heights, vector<int> &cost) {
    int n = heights.size();

    int ans = INT_MAX;
    // Set heights of all towers to heights[i]
    for (int i = 0; i < n; i++) {

        int total = 0;

        // Calculate cost to equalize current
        // tower height to heights[i];
        for (int j = 0; j < n; j++) {
            total += cost[j] * abs(heights[j] - heights[i]);
        }
        if (total >= 0)
            ans = min(ans, total);
    }

    return ans;
}

int main() {
    vector<int> heights = {1, 2, 3};
    vector<int> cost = {10, 100, 1000};
    cout << minCost(heights, cost);
    return 0;
}

Java

class GfG{
    static int minCost(int[] heights,
                                       int[] cost) {
        int n = heights.length;

        int ans = Integer.MAX_VALUE;

        // Set heights of all towers to heights[i]
        for (int i = 0; i < n; i++) {

            int total = 0;

            // Calculate cost to equalize current
            // tower height to heights[i];
            for (int j = 0; j < n; j++) {
                total += 
                    cost[j] * Math.abs(heights[j] - heights[i]);
            }
            if (total >= 0)
                ans = Math.min(ans, total);
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] heights = { 1, 2, 3 };
        int[] cost = { 10, 100, 1000 };
        System.out.println(
            minCost(heights, cost));
    }
}

Python

def minCost(heights, cost):
    n = len(heights)

    ans = float('inf')

    # Set heights of all towers to heights[i]
    for i in range(n):

        total = 0

        # Calculate cost to equalize current
        # tower height to heights[i];
        for j in range(n):
            total += cost[j] * abs(heights[j] - heights[i])
        if total >= 0:
            ans = min(ans, total)

    return ans


if __name__ == "__main__":
    heights = [1, 2, 3]
    cost = [10, 100, 1000]
    print(minCost(heights, cost))

using System;
class GfG {
    static int minCost(int[] heights,
                                       int[] cost) {
        int n = heights.Length;
        int ans = int.MaxValue;

        // Set heights of all towers to heights[i]
        for (int i = 0; i < n; i++) {

            int total = 0;

            // Calculate cost to equalize current
            // tower height to heights[i];
            for (int j = 0; j < n; j++) {
                total
                    += cost[j]
                       * Math.Abs(heights[j] - heights[i]);
            }
            if (total >= 0)
                ans = Math.Min(ans, total);
        }

        return ans;
    }

    static void Main() {
        int[] heights = { 1, 2, 3 };
        int[] cost = { 10, 100, 1000 };
        Console.WriteLine(
            minCost(heights, cost));
    }
}

JavaScript

function minCost(heights, cost) {
    let n = heights.length;

    let ans = Number.MAX_SAFE_INTEGER;

    // Set heights of all towers to heights[i]
    for (let i = 0; i < n; i++) {

        let total = 0;
        // Calculate cost to equalize current
        // tower height to heights[i];
        for (let j = 0; j < n; j++) {
            total += cost[j]
                     * Math.abs(heights[j] - heights[i]);
        }
        if (total >= 0)
            ans = Math.min(ans, total);
    }

    return ans;
}

// Driver Code
const heights = [ 1, 2, 3 ];
const cost = [ 10, 100, 1000 ];
console.log(minCost(heights, cost));

Output

[Expected Approach] Binary Search – O(n × log₂(max(heights[i]) - min(heights[i])) Time and O(1) Space

At minimum or maximum heights, the cost increases due to many changes in heights. As we move toward a balanced height, the cost drops, reaches a minimum, then rises again — forming a V-shape. We use binary search by checking mid - 1, mid, and mid + 1 to move toward the side with lower cost and find the minimum cost efficiently.

Step by step approach:

Find the minimum and maximum height in the heights[] array and use them as the initial range for binary search.
Apply binary search on this range. For each mid-point mid, calculate the total cost of making all towers of height: mid - 1, mid, mid + 1
Check these cases:
=> If findCost(mid) ≤ findCost(mid - 1) and findCost(mid) ≤ findCost(mid + 1),
→ mid gives the minimum cost, return it.
=> If findCost(mid) ≤ findCost(mid - 1) and findCost(mid + 1) < findCost(mid),
→ Move right: set low = mid + 1 (we are in the decreasing part of the cost curve).
=> If findCost(mid - 1) < findCost(mid),
→ Move left: set high = mid - 1 (we are in the increasing part of the cost curve).
Repeat until the minimum cost is found.

C++

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

// calculate total cost to make all towers height h
int findCost(vector<int> &heights, vector<int> &cost, int h) {
    int res = 0;
    int n = heights.size();
    for (int i = 0; i < n; i++) {
        res += cost[i] * abs(heights[i] - h);
    }
    return res;
}

// return minimum cost to make all towers same height
int minCost(vector<int> &heights, vector<int> &cost) {
    int n = heights.size();

    // find min and max height
    int mini = INT_MAX, maxi = INT_MIN;
    for (auto val : heights) {
        mini = min(mini, val);
        maxi = max(maxi, val);
    }

    int low = mini, high = maxi;
    int ans;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        int val1 = findCost(heights, cost, mid - 1);
        int val2 = findCost(heights, cost, mid);
        int val3 = findCost(heights, cost, mid + 1);

        // if mid gives lowest cost
        if (val2 <= val1 && val2 <= val3) {
            ans = val2;
            break;
        }
        // if decreasing side gives less cost
        else if (val1 >= val2 && val2 >= val3) {
            low = mid + 1;
        }
        // if increasing side gives less cost
        else if (val2 >= val1 && val3 >= val2) {
            high = mid - 1;
        }
    }

    return ans;
}

int main() {
    vector<int> heights = {1, 2, 3};
    vector<int> cost = {10, 100, 1000};
    cout << minCost(heights, cost);
    return 0;
}

Java

class GfG {
    // calculate total cost to make all towers height h
    static int findCost(int[] heights, int[] cost, int h)   {
        int res = 0;
        int n = heights.length;
        for (int i = 0; i < n; i++) {
            res += cost[i] * Math.abs(heights[i] - h);
        }
        return res;
    }

    // return minimum cost to make all towers same height   
    static int minCost(int[] heights,
                                       int[] cost) {
        int n = heights.length;

        // Find the binary search range
        int mini = Integer.MAX_VALUE, maxi
                                      = Integer.MIN_VALUE;
        for (int val : heights) {
            mini = Math.min(mini, val);
            maxi = Math.max(maxi, val);
        }

        int low = mini, high = maxi;
        int ans = 0;

        while (low <= high) {

            int mid = low + (high - low) / 2;

            int val1 = findCost(heights, cost, mid - 1);
            int val2 = findCost(heights, cost, mid);
            int val3 = findCost(heights, cost, mid + 1);

            // If mid is the bottom most value.
            if (val2 <= val1 && val2 <= val3) {
                ans = val2;
                break;
            }

            // If mid falls in the first segment
            else if (val1 >= val2 && val2 >= val3) {
                low = mid + 1;
            }

            // If mid falls in the second segment
            else if (val2 >= val1 && val3 >= val2) {
                high = mid - 1;
            }
        }

        return ans;
    }

    public static void main(String[] args)
    {
        int[] heights = { 1, 2, 3 };
        int[] cost = { 10, 100, 1000 };
        System.out.println(
            minCost(heights, cost));
    }
}

Python

# calculate total cost to make all towers height h
def findCost(heights, cost, h):
    res = 0
    n = len(heights)
    for i in range(n):
        res += cost[i] * abs(heights[i] - h)
    return res

# return minimum cost to make all towers same height
def minCost(heights, cost):
    n = len(heights)

    # Find the binary search range
    mini = min(heights)
    maxi = max(heights)

    low = mini
    high = maxi
    ans = 0

    while low <= high:

        mid = low + (high - low) // 2

        val1 = findCost(heights, cost, mid - 1)
        val2 = findCost(heights, cost, mid)
        val3 = findCost(heights, cost, mid + 1)

        # If mid is the bottom most value.
        if val2 <= val1 and val2 <= val3:
            ans = val2
            break

        # If mid falls in the first segment
        elif val1 >= val2 and val2 >= val3:
            low = mid + 1

        # If mid falls in the second segment
        elif val2 >= val1 and val3 >= val2:
            high = mid - 1

    return ans


if __name__ == "__main__":
    heights = [1, 2, 3]
    cost = [10, 100, 1000]
    print(minCost(heights, cost))

using System;
class GfG {

    // calculate total cost to make all towers height h
    static int FindCost(int[] heights, int[] cost, int h) {
        int res = 0;
        int n = heights.Length;
        for (int i = 0; i < n; i++) {
            res += cost[i] * Math.Abs(heights[i] - h);
        }
        return res;
    }

    // return minimum cost to make all towers same height
    static int minCost(int[] heights,
                                       int[] cost)
    {
        int n = heights.Length;

        // Find the binary search range
        int mini = int.MaxValue, maxi = int.MinValue;
        foreach(int val in heights)
        {
            mini = Math.Min(mini, val);
            maxi = Math.Max(maxi, val);
        }

        int low = mini, high = maxi;
        int ans = 0;

        while (low <= high) {

            int mid = low + (high - low) / 2;

            int val1 = FindCost(heights, cost, mid - 1);
            int val2 = FindCost(heights, cost, mid);
            int val3 = FindCost(heights, cost, mid + 1);

            // If mid is the bottom most value.
            if (val2 <= val1 && val2 <= val3) {
                ans = val2;
                break;
            }

            // If mid falls in the first segment
            else if (val1 >= val2 && val2 >= val3) {
                low = mid + 1;
            }

            // If mid falls in the second segment
            else if (val2 >= val1 && val3 >= val2) {
                high = mid - 1;
            }
        }

        return ans;
    }

    static void Main()
    {
        int[] heights = { 1, 2, 3 };
        int[] cost = { 10, 100, 1000 };
        Console.WriteLine(
            minCost(heights, cost));
    }
}

JavaScript

// calculate total cost to make all towers height h
function findCost(heights, cost, h) {
    let res = 0;
    let n = heights.length;
    for (let i = 0; i < n; i++) {
        res += cost[i] * Math.abs(heights[i] - h);
    }
    return res;
}

// return minimum cost to make all towers same height
function minCost(heights, cost) {
    let n = heights.length;

    // Find the binary search range
    let mini = Math.min(...heights);
    let maxi = Math.max(...heights);

    let low = mini, high = maxi;
    let ans = 0;

    while (low <= high) {

        let mid = Math.floor(low + (high - low) / 2);

        let val1 = findCost(heights, cost, mid - 1);
        let val2 = findCost(heights, cost, mid);
        let val3 = findCost(heights, cost, mid + 1);

        // If mid is the bottom most value.
        if (val2 <= val1 && val2 <= val3) {
            ans = val2;
            break;
        }

        // If mid falls in the first segment
        else if (val1 >= val2 && val2 >= val3) {
            low = mid + 1;
        }

        // If mid falls in the second segment
        else if (val2 >= val1 && val3 >= val2) {
            high = mid - 1;
        }
    }

    return ans;
}

// Driver Code
const heights = [ 1, 2, 3 ];
const cost = [ 10, 100, 1000 ];
console.log(minCost(heights, cost));

Output

[Alternate Approach] Ternary Search

At low or high heights, the cost increases due to excessive changes in heights. As we move toward an optimal height, the cost decreases, reaches a minimum, then increases again — forming a V-shape (unimodal pattern). This allows us to use Ternary search to efficiently find the minimum cost.

Step by step approach:

Each tower must be adjusted to a target height with cost: abs(height - target) * cost.
The target height will always lie between the minimum and maximum of the given tower heights.
The total cost function is unimodal, it decreases, reaches a minimum, then increases.
Therefore, ternary search is used to efficiently find the minimum cost.
In each step, two midpoints are chosen, and total cost is calculated at both.
If both costs are equal, shrink both ends of the range.
If the left cost is smaller, discard the right part.
If the right cost is smaller, discard the left part.
After the search ends, the minimum cost found is the final answer.

C++

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

// helper function to calculate the cost of making all towers
// equal to a specific target height
int costOfOperation(vector<int>& heights, vector<int>& cost,
                                                    int target) {
                                                        
    int totalCost = 0;
    int n = heights.size();
    for (int i = 0; i < n; i++) {
        // Cost is the absolute height difference 
        // multiplied by the cost factor
        totalCost += abs(heights[i] - target) * cost[i];
    }
    return totalCost;
    
}

// ternary Search function to find the height
// that minimizes the total cost
int minCost(vector<int>& heights, vector<int>& cost) {
    // set the search space between the minimum and
    // maximum tower height
    int low = *min_element(heights.begin(), heights.end());
    int high = *max_element(heights.begin(), heights.end());
    int minimumCost = INT_MAX;

    // perform ternary Search within the height range
    while (low <= high) {
        int mid1 = low + (high - low) / 3;
        int mid2 = high - (high - low) / 3;

        // calculate cost at mid1 and mid2
        int cost1 = costOfOperation(heights, cost, mid1);
        int cost2 = costOfOperation(heights, cost, mid2);

        // track the minimum cost found so far
        minimumCost = min({minimumCost, cost1, cost2});

        // narrow the search space based on comparison
        if (cost1 == cost2) {
            
            // If costs are equal, we shrink both sides
            low = mid1 + 1;
            high = mid2 - 1;
        }
        else if (cost1 < cost2) {
            // optimal cost is towards the left half
            high = mid2 - 1;
        }
        else {
            // optimal cost is towards the right half
            low = mid1 + 1;
        }
    }

    return minimumCost;
}

int main() {
    vector<int> heights = {1, 2, 3};
    vector<int> cost = {10, 100, 1000};
    cout << minCost(heights, cost);
    return 0;
}

Java

import java.util.ArrayList;
import java.util.Arrays;

class GfG {
    // helper function to calculate the cost of making all
    // towers equal to a specific target height
    static int costOfOperation(int[] heights, int[] cost, int target){
        int totalCost = 0;
        int n = heights.length;
        for (int i = 0; i < n; i++) {
            // cost is the absolute height difference multiplied by 
            // the cost factor
            totalCost += Math.abs(heights[i] - target) * cost[i];
        }
        return totalCost;
    }

    // ternaray Search function to find the height that
    // minimizes the total cost
    static int minCost(int[] heights, int[] cost) {
        
        // set the search space between the minimum and maximum 
        // tower height
        int low = Arrays.stream(heights).min().getAsInt();
        int high = Arrays.stream(heights).max().getAsInt();
        int minimumCost = Integer.MAX_VALUE;

        // perform Ternary Search within the height range
        while (low <= high) {
            int mid1 = low + (high - low) / 3;
            int mid2 = high - (high - low) / 3;

            // calculate cost at mid1 and mid2
            int cost1 = costOfOperation(heights, cost, mid1);
            int cost2 = costOfOperation(heights, cost, mid2);

            // track the minimum cost found so far
            minimumCost = Math.min(minimumCost, 
                                    Math.min(cost1, cost2));

            // narrow the search space based on comparison
            if (cost1 == cost2) {
                // if costs are equal, we shrink both sides
                low = mid1 + 1;
                high = mid2 - 1;
            } else if (cost1 < cost2) {
                // Optimal cost is towards the left half
                high = mid2 - 1;
            } else {
                // Optimal cost is towards the right half
                low = mid1 + 1;
            }
        }

        return minimumCost;
    }

    public static void main(String[] args) {
        int[] heights = {1, 2, 3};
        int[] cost = {10, 100, 1000};
        System.out.println(minCost(heights, cost));
    }
}

Python

# helper function to calculate the cost of making all towers 
# equal to a specific target height
def costOfOperation(heights, cost, target):
    totalCost = 0
    for h, c in zip(heights, cost):
        # cost is the absolute height difference multiplied
        # by the cost factor
        totalCost += abs(h - target) * c
    return totalCost

# ternary Search function to find the height that
# minimizes the total cost
def minCost(heights, cost):
    low = min(heights)
    high = max(heights)
    minimumCost = float('inf')

    while low <= high:
        mid1 = low + (high - low) // 3
        mid2 = high - (high - low) // 3

        cost1 = costOfOperation(heights, cost, mid1)
        cost2 = costOfOperation(heights, cost, mid2)

        minimumCost = min(minimumCost, cost1, cost2)

        if cost1 == cost2:
            low = mid1 + 1
            high = mid2 - 1
        elif cost1 < cost2:
            high = mid2 - 1
        else:
            low = mid1 + 1

    return minimumCost

if __name__ == "__main__":
    heights = [1, 2, 3]
    cost = [10, 100, 1000]
    print(minCost(heights, cost))

using System;

class GfG {
    // helper function to calculate the cost of making all towers
    // equal to a specific target height
    static int CostOfOperation(int[] heights, int[] cost, int target) {
        int totalCost = 0;
        for (int i = 0; i < heights.Length; i++) {
            // cost is the absolute height difference multiplied
            // by the cost factor
            totalCost += Math.Abs(heights[i] - target) * cost[i];
        }
        return totalCost;
    }

    // ternary search function to find the height that
    // minimizes the total cost
    public static int minCost(int[] heights, int[] cost) {
        int low = int.MaxValue;
        int high = int.MinValue;

        // find the min and max values from heights array
        foreach (int h in heights) {
            if (h < low) low = h;
            if (h > high) high = h;
        }

        int minimumCost = int.MaxValue;

        while (low <= high) {
            int mid1 = low + (high - low) / 3;
            int mid2 = high - (high - low) / 3;

            int cost1 = CostOfOperation(heights, cost, mid1);
            int cost2 = CostOfOperation(heights, cost, mid2);

            // track the minimum cost found so far
            minimumCost = Math.Min(minimumCost, Math.Min(cost1, cost2));

            // narrow the search space based on comparison
            if (cost1 == cost2) {
                // if costs are equal, we shrink both sides
                low = mid1 + 1;
                high = mid2 - 1;
            } else if (cost1 < cost2) {
                // optimal cost is towards the left half
                high = mid2 - 1;
            } else {
                // optimal cost is towards the right half
                low = mid1 + 1;
            }
        }

        return minimumCost;
    }

    static void Main() {
        int[] heights = { 1, 2, 3 };
        int[] cost = { 10, 100, 1000 };
        Console.WriteLine(minCost(heights, cost));
    }
}

JavaScript

// helper function to calculate the cost of making all towers 
// equal to a specific target height
function costOfOperation(heights, cost, target) {
    let totalCost = 0;
    for (let i = 0; i < heights.length; i++) {
        // Cost is the absolute height difference multiplied 
        /// by the cost factor
        totalCost += Math.abs(heights[i] - target) * cost[i];
    }
    return totalCost;
}

// ternary Search function to find the height that 
// minimizes the total cost
function minCost(heights, cost) {
    let low = Math.min(...heights);
    let high = Math.max(...heights);
    let minimumCost = Number.MAX_SAFE_INTEGER;

    while (low <= high) {
        let mid1 = Math.floor(low + (high - low) / 3);
        let mid2 = Math.floor(high - (high - low) / 3);

        let cost1 = costOfOperation(heights, cost, mid1);
        let cost2 = costOfOperation(heights, cost, mid2);

        minimumCost = Math.min(minimumCost, cost1, cost2);

        if (cost1 === cost2) {
            low = mid1 + 1;
            high = mid2 - 1;
        } else if (cost1 < cost2) {
            high = mid2 - 1;
        } else {
            low = mid1 + 1;
        }
    }

    return Math.min(minimumCost, 
                costOfOperation(heights, cost, low));
}

let heights = [1, 2, 3];
let cost = [10, 100, 1000];
console.log(minCost(heights, cost));

Output

Time Complexity: O(n × log₃(max(heights[i]) - min(heights[i]))), ternary search is applied over the range from the minimum to the maximum tower height. In each step, calculating the total cost takes O(n) time, and the number of steps is logarithmic in the height difference.
Auxiliary Space: O(1), the algorithm uses only a constant amount of extra variables for computation, regardless of the number of towers.

Minimize cost of operation to equalize tower heights

[Naive Approach] Check All Possibilities – O(n^2) Time and O(1) Space

[Expected Approach] Binary Search – O(n × log2(max(heights[i]) - min(heights[i])) Time and O(1) Space

[Alternate Approach] Ternary Search

Explore

[Expected Approach] Binary Search – O(n × log₂(max(heights[i]) - min(heights[i])) Time and O(1) Space