30. Max Min Height
✅ GFG solution to the Max Min Height problem: maximize minimum flower height after k days of watering using binary search and greedy strategy. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
Given a garden with n flowers planted in a row, represented by an array arr[] where arr[i] denotes the height of the ith flower. You will water them for k days. In one day you can water w continuous flowers. Whenever you water a flower its height increases by 1 unit. You have to maximize the minimum height of all flowers after k days of watering.
📘 Examples
Example 1
Input: arr[] = [2, 3, 4, 5, 1], k = 2, w = 2
Output: 2
Explanation: The minimum height after watering is 2.
Day 1: Water the last two flowers -> arr becomes [2, 3, 4, 6, 2]
Day 2: Water the last two flowers -> arr becomes [2, 3, 4, 7, 3]Example 2
Input: arr[] = [5, 8], k = 5, w = 1
Output: 9
Explanation: The minimum height after watering is 9.
Day 1 - Day 4: Water the first flower -> arr becomes [9, 8]
Day 5: Water the second flower -> arr becomes [9, 9]🔒 Constraints
$1 \le \text{arr.size()} \le 10^5$
$1 \le w \le \text{arr.size()}$
$1 \le k \le 10^5$
$1 \le \text{arr}[i] \le 10^9$
✅ My Approach
The optimal approach uses Binary Search on Answer combined with a Greedy Watering Strategy:
Binary Search + Greedy Validation
Binary Search Setup:
Search space:
[min(arr), min(arr) + k]For each candidate minimum height, check if it's achievable with k days
Greedy Validation Strategy:
Use a sliding window approach to simulate watering effects
Track cumulative water added using a frequency array
When a flower's height is below target, greedily add water to achieve the target
Early termination if we exceed k days
Sliding Window Optimization:
Maintain running sum of water effects within window w
Efficiently calculate current height by adding/removing window effects
Use prefix sum technique for optimal performance
Maximize the Answer:
If current target is achievable, try a higher target
If not achievable, reduce the target
Return the maximum achievable minimum height
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(n log k), where n is the array size and k is the number of days. Binary search takes O(log k) iterations, and each validation takes O(n) time to simulate the watering process.
Expected Auxiliary Space Complexity: O(n), as we use an auxiliary array to track the cumulative watering effects for each position in the garden.
🧑💻 Code (C++)
class Solution {
public:
bool isPossible(vector<int> &arr, int k, int w, int maxHeight) {
int n = arr.size();
vector<int> water(n, 0);
for (int i = 0; i < n; i++) {
if (i > 0) water[i] = water[i - 1];
int currHeight = arr[i] + water[i];
if (i >= w) currHeight -= water[i - w];
if (currHeight < maxHeight) {
int add = maxHeight - currHeight;
water[i] += add;
k -= add;
if (k < 0) return false;
}
}
return true;
}
int maxMinHeight(vector<int> &arr, int k, int w) {
int n = arr.size();
int low = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] < low) low = arr[i];
}
int high = low + k, ans = low;
while (low <= high) {
int mid = low + (high - low) / 2;
if (isPossible(arr, k, w, mid)) {
ans = max(ans, mid);
low = mid + 1;
} else {
high = mid - 1;
}
}
return ans;
}
};🧑💻 Code (Java)
class Solution {
boolean isPossible(int[] arr, int k, int w, int maxHeight) {
int n = arr.length;
int[] water = new int[n];
for (int i = 0; i < n; i++) {
if (i > 0) water[i] = water[i - 1];
int currHeight = arr[i] + water[i];
if (i >= w) currHeight -= water[i - w];
if (currHeight < maxHeight) {
int add = maxHeight - currHeight;
water[i] += add;
k -= add;
if (k < 0) return false;
}
}
return true;
}
public int maxMinHeight(int[] arr, int k, int w) {
int n = arr.length;
int low = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] < low) low = arr[i];
}
int high = low + k, ans = low;
while (low <= high) {
int mid = low + (high - low) / 2;
if (isPossible(arr, k, w, mid)) {
ans = Math.max(ans, mid);
low = mid + 1;
} else {
high = mid - 1;
}
}
return ans;
}
}🐍 Code (Python)
class Solution:
def isPossible(self, arr, k, w, maxHeight):
n = len(arr)
water = [0] * n
for i in range(n):
if i > 0:
water[i] = water[i - 1]
currHeight = arr[i] + water[i]
if i >= w:
currHeight -= water[i - w]
if currHeight < maxHeight:
add = maxHeight - currHeight
water[i] += add
k -= add
if k < 0:
return False
return True
def maxMinHeight(self, arr, k, w):
n = len(arr)
low = min(arr)
high = low + k
ans = low
while low <= high:
mid = low + (high - low) // 2
if self.isPossible(arr, k, w, mid):
ans = max(ans, mid)
low = mid + 1
else:
high = mid - 1
return ans🧠 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