16. Equalize the Towers
✅ GFG solution to the Equalize the Towers problem: find minimum cost to make all towers same height using binary search optimization. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
You are given an array heights[]
representing the heights of towers and another array cost[]
where each element represents the cost of modifying the height of respective tower.
The goal is to make all towers of same height by either adding or removing blocks from each tower. Modifying the height of tower 'i' by 1 unit costs cost[i]
.
Return the minimum cost to equalize the heights of all towers.
📘 Examples
Example 1
Input: heights[] = [1, 2, 3], cost[] = [10, 100, 1000]
Output: 120
Explanation: The heights can be equalized by either "Removing one block from 3 and adding one in 1" or "Adding two blocks in 1 and adding one in 2". Since the cost of operation in tower 3 is 1000, the first process would yield 1010 while the second one yields 120.
Example 2
Input: heights[] = [7, 1, 5], cost[] = [1, 1, 1]
Output: 6
Explanation: The minimum cost to equalize the towers is 6, achieved by setting all towers to height 5.
🔒 Constraints
$1 \le \text{heights.size()} = \text{cost.size()} \le 10^5$
$1 \le \text{heights}[i] \le 10^4$
$1 \le \text{cost}[i] \le 10^3$
✅ My Approach
The optimal approach uses Binary Search on Answer to find the target height that minimizes the total cost:
Binary Search on Target Height
Search Space Setup:
The optimal target height lies between 0 and maximum height in the array.
We need to find the height that minimizes the total cost function.
Cost Function Analysis:
For any target height
h
, cost = Σ|heights[i] - h| × cost[i]This creates a unimodal function (convex) with a single minimum.
Binary Search Implementation:
Compare costs at adjacent heights
m
andm+1
.If cost at
m
≤ cost atm+1
, optimal height is in left half (including m).Otherwise, optimal height is in right half.
Final Calculation:
Once we find the optimal height, calculate the actual minimum cost.
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(n × log(max_height)), where n is the number of towers and max_height is the maximum height in the array. Binary search takes O(log(max_height)) iterations, and each iteration requires O(n) time to calculate the cost.
Expected Auxiliary Space Complexity: O(1), as we only use constant extra space for variables and calculations (excluding the input arrays).
🧑💻 Code (C++)
class Solution {
public:
int minCost(vector<int>& heights, vector<int>& cost) {
int l = 0, h = *max_element(heights.begin(), heights.end());
while (l < h) {
int m = l + (h - l) / 2;
long long c1 = 0, c2 = 0;
for (int i = 0; i < heights.size(); ++i) {
c1 += (long long)abs(heights[i] - m) * cost[i];
c2 += (long long)abs(heights[i] - m - 1) * cost[i];
}
c1 <= c2 ? h = m : l = m + 1;
}
long long ans = 0;
for (int i = 0; i < heights.size(); ++i)
ans += (long long)abs(heights[i] - l) * cost[i];
return ans;
}
};
🧑💻 Code (Java)
class Solution {
public int minCost(int[] heights, int[] cost) {
int l = 0, h = Arrays.stream(heights).max().getAsInt();
while (l < h) {
int m = l + (h - l) / 2;
long c1 = 0, c2 = 0;
for (int i = 0; i < heights.length; ++i) {
c1 += (long)Math.abs(heights[i] - m) * cost[i];
c2 += (long)Math.abs(heights[i] - m - 1) * cost[i];
}
if (c1 <= c2) h = m;
else l = m + 1;
}
long ans = 0;
for (int i = 0; i < heights.length; ++i)
ans += (long)Math.abs(heights[i] - l) * cost[i];
return (int)ans;
}
}
🐍 Code (Python)
class Solution:
def minCost(self, heights, cost):
l, h = 0, max(heights)
while l < h:
m = l + (h - l) // 2
c1 = sum(abs(heights[i] - m) * cost[i] for i in range(len(heights)))
c2 = sum(abs(heights[i] - m - 1) * cost[i] for i in range(len(heights)))
if c1 <= c2:
h = m
else:
l = m + 1
return sum(abs(heights[i] - l) * cost[i] for i in range(len(heights)))
🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated