Given an integer array representing the heights of N buildings, the task is to delete N-2 buildings such that the water that can be trapped between the remaining two building is maximum.
Here’s an algorithm for the maxWater
method:
- Start by initializing two pointers i and j to the first and last element of the input array respectively.
- Initialize a variable maxwater to 0.
- While i is less than j:
a. Calculate the amount of water that can be stored between the walls represented by the current values of i and j using the formula:
Math.min(height[i], height[j]) * (j – i – 1)
b. Update maxwater to be the maximum value between its current value and the value calculated in the previous step.
c. If height[i] is less than height[j], increment i, otherwise decrement j. - Return maxwater as the maximum amount of water that can be stored between the given set of walls.
Maximum Water Between Two Buildings
class Solution { //Function to return the maximum water that can be stored. static int maxWater(int height[], int n) { //Your code here int i=0; int j=n-1; int maxwater=0; while(i<j){ maxwater=Math.max(maxwater, Math.min(height[i],height[j])*(j-i-1)); if(height[i]<height[j]) i++; else j--; } return maxwater; } }
This Java code defines a class named Solution
that contains a static method named maxWater
. This method takes two arguments: an array of integers height
representing the height of walls, and an integer n
representing the number of walls. The method returns an integer representing the maximum amount of water that can be stored between the walls.
The implementation of the maxWater
method follows the two-pointer approach. Two pointers i
and j
are initialized at the start and end of the array respectively. The variable maxwater
is initialized to 0, which will be used to store the maximum amount of water.
The method uses a while loop that continues until the two pointers meet. In each iteration of the loop, the maximum amount of water that can be stored between the walls represented by the current values of the two pointers is calculated using the formula Math.min(height[i],height[j])*(j-i-1)
and is compared with the previous maximum value stored in the maxwater
variable.
The Math.min
function is used to find the minimum height between the two walls since the amount of water that can be stored is limited by the shorter wall. The (j-i-1)
term represents the distance between the two walls.
If the height of the wall at position i
is less than the height of the wall at position j
, the pointer i
is incremented, otherwise, the pointer j
is decremented. This process continues until the two pointers meet, and the maximum amount of water that can be stored between the walls is returned.
Overall, the maxWater
method implements an efficient approach to solve the classic problem of finding the maximum amount of water that can be stored between a given set of walls.
Disclaimer: This problem (Maximum Water Between Two Buildings) is originally created by GeeksforGeeks. Codesagar only provides a solution for it. This solution is only for Educational and learning purposes.