Hi, Welcome to tech-maze, In today's article, we are going to explore a program which is really hard to understand and quite popular among product based companies, i have tried my level best to reduce the complexity as much as possible.
Lets have a look to the question and its solution
Problem :-
You are given an integer array vertical lines of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two vertical lines together with the x-axis, which form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
above question is quite vague and doesn't actually explain much so i am going to break this down to understand what actually it refers to and then we go for the solution
So as per the question we have vertical lines which are placed based on x-y axis, following picture shows how these lines has placed based on the number given in the array.
Representing Array : [1,8,6,2,5,4,8,3,7]
after placing all the vertical lines in the diagram, lets see what exactly we have to do here, now we have to find out a container which can form by using two verticals lines , that can hold maximum water.
we have to form a container in such a way that it can hold the maximum water, while finding the maximum water we have to consider following three points
1. choose higher vertical lines
2. distance between selected vertical line must not be very less.
3. consider vertical lines in such a way that, pouring water must not spill out, hence have to consider minimum vertical line out of selected two and multiply that with the distance between them.
Lets put this consideration in one of the input array to understand these hypothesis.
Array :- [1,8,6,2,5,4,8,3,7]
The algorithm we use for basic approach involves the following steps:
Step 1 : first take care the negative scenario to avoid any unpleasant exception.
Step 2 : Now create two loops, fix the first loop and traverse through all the element in second loop to check every possible combination of two vertical lines.
Step 3 : First loop runs from 0 to arraysize-1 and second loop runs from first-loop-index + 1 to arraysize-1.
Step 4 : For each iteration of the first loop we will get a pair of vertical lines, now will check if the water level formed by these vertical lines is greater than the max water level.
If yes update the result, else continue to check the next pair.
This process will continue until we get the maximum water level, in this case, the maximum water level a container can hold will be 49
This is brute force approach, the time complexity and space complexity of this solution is O (n^2) and O(1)
Code for this approach :-
public static int findMaxWater(int[] arr) {
int maxval = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = i+1; j < arr.length; j++) {
int minval = min(arr[i], arr[j])*(j-i);
maxval = max(maxval, minval);
}
}
return maxval;
}
Here min and max are the functions which simply return minimum of two and maximum of two number
Now lets see how we can solve the same problem with better time complexity, before going for the next solution, lets point out what we can avoid in order to drop the complexity to the level of O(n)
Explanation :-
For the given array, if we start with the combination of first and second vertical lines and move inwards i.e. (1,8), (1,6), (1,2) and so on, we can see that we get no benefit by using combinations (1,8), (1,6), (1,2) so on so forth to calculate water level, as the minimum water level obtained by using any of these combinations remains same. The reason being because in all cases 2nd vertical line is greater than the 1st vertical line (first vertical line has height 1, which is same for all the pairs),
and since we take the minimum of 1st and 2nd vertical lines while calculating the water level, we always end up with 1 multiply by distance between the vertical lines as the result for all the above combinations. This is true for all such cases where for a set of combinations one of the vertical lines is same and it is smaller than the other vertical line in all pairs. Also the width keeps decreasing as we move inwards, for (1,7) width is 8, for (1,3) width is 7 and so on. Therefore the max water level will also decrease.
We can use this to our advantage to solve this problem in linear time.
This approach involves the following steps:
Step 1 :-
We need to start our algorithm with two pointers, one pointer points to first vertical line (0th index in the array) and second pointer points to last index of the array.
Step 2 :- We calculate the water level using the left and right vertical lines using the previous formula (minimum of two multiplied by distance between them).
Step 3 :-
After this we need to retain maximum of left and right pointers and move the pointer.
For example if our (left, right) = (1,7), after calculating the water level, we check which of (left vertical line, right vertical line) is greater. In this case, right vertical line i.e. 7 is the greater of the two. So, we keep the right pointer at the same position and increment the left pointer by 1.
Step 4 :-
Similarly if the left element is greater of two as in (8,7) then we keep the left pointer at the same index and decrement the right pointer after calculating the max water level for (8, 7). We can do this because we know, we do not get any benefit (in terms of water level obtained) by retaining the smaller vertical line, and thus this would have no impact on the output.
This process will continue until left pointer is less than right pointer, once process over return the maximum water level obtained as result.
This algorithm goes through each array element only once to find the result, so the time complexity is O(n).
Now lets see how we can derive all these scenarios in program.
Code for this approach :-
public static int findMaxWaterwithNTImeComplexity(int[] arr) {
int maxval = 0;
int i = 0;
int j = arr.length-1;
while(i<j) {
int minval = min(arr[i], arr[j])*(j-i);
maxval = max(maxval, minval);
if(arr[i]<arr[j]) {
i++;
}else {
j--;
}
}
return maxval;
}
Here min and max are the functions which simply return minimum of two and maximum of two number
Please let me know what you guys think about the solution, feel free to share this article and share your suggestion/thoughts/solutions in comment section.
For complete code please have a look in the below GitHub project
Git location : https://github.com/rohitmodi07/Programs
File Name : FindMaxWaterLevel
That's all folks in this article, keep visiting tech-maze for more of Data Structure and System Design related topics
A Big thank you for checking out my article, this really encourage me to come up with more topics.
Comments