Suppose we are given an array of non-negative integers a1, a2, a3, a4, … an, where each point represents a coordinate (i, ai). We can draw vertical lines taking each integer from the array such that each line coordinates will be (i,0) and (i, ai).
Credits for the image go to Placewit.
According to the problem we need to find the two lines which form a container and can store the maximum amount of water in both the vertical lines.
In the above figure we can store the maximum amount of water between vertical lines present at two (with length eight) and nine (with length seven). There will exist no other combination of vertical lines in which water can be stored more than forty-nine units (7*7).
Examples
Array : [ 2, 5, 4, 3, 1]
Output : 6 units
The maximum water can be stored between (5,3) vertical Lines.
Output= 6 =min(5,3)*(distance between both vertical lines (2)).
Let’s take another example.
Array : [3, 1, 2, 4, 5, 1]
Output : 12 units
Maximum water can be held between (3,5) vertical lines.
Output= 12 =min(3,5)*( distance between both Vertical lines (4)).
In the naive approach we will find the maximum water that can be contained using brute force. We will try each and every pair of vertical lines and then pick the pair which gives us the maximum capacity container.
Declare
maxCap=0 //to store max capacity
a,b //to store both vertical lines
Step 1: Outer loop will run i from 0 to n(last index)
Step 2: The inner loop will run j from i+1 to n(last index)
Step 3: Find capacity= min(i,j)*(distance between both vertical lines).
Check if the calculated capacity is more than maxCap;
if yes, then update maxCap and update a,b.
Step 4: Return maxCap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.io.*;
class Solution {
public static int maxCapacity(int[] arr) {
int capacity = 0;
for (int x = 0; x < arr.length; x++) {
for (int k = x + 1; x < arr.length; k++) {
capacity = Math.max(
capacity, Math.min(arr[x], arr[k]) * (k - x));
}
}
return capacity;
}
// main Method
public static void main(String[] args) {
int arr1[] = {
1,
5,
4,
3,
1
};
int arr2[] = {
3,
1,
2,
4,
5,
1
};
System.out.println("\nMaxCapacity: " + maxCapacity(arr1));
System.out.println("\n\nMaxCapacity: " + maxCapacity(arr2));
}
}
Time complexity : O (N*N)
The array is getting traversed by outer and inner loop.
Space complexity: O(1)
No extra space is used so the complexity is constant.
Code Snippet
In order to use an efficient solution to find the maximum water we can store in a container, we will start with two vertical lines, first and last, and check how much water can be stored. So now our first and second index is pointing to the first and last vertical lines respectively. We will check if there are any other combinations of vertical lines in which we can store water more than what we have already calculated. If the value of the vertical line at which the first is pointing is lesser than the value of the second, then increment the first or decrement the second. This way we can find the maximum capacity that can be stored.
Declaration
first =0, second = arr.length-1, maxCapacity=0
Step 1: Loop until first is lesser than second
Step 2: Find the maxCapacity=min(first, second)*(distance between both vertical lines and update maxCapacity.
Step 3 : If first is lesser than second then first++ else second–
Step 4: If first <= second go to step one or else exit and print maxCapacity.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.*;
class Solution {
public static int maxCapacity(int arr[]) {
int len = arr.length;
int first = 0;
int second = len - 1;
int maxCap = 0;
while (first < second) {
// Calculating maxCapacity
maxCap = Math.max(maxCap,
Math.min(arr[first], arr[second]) * (second - first));
if (arr[first] < arr[second])
first++;
else
second--;
}
return maxCap;
}
public static void main(String[] args) {
int arr1[] = {
1,
5,
4,
3,
1
};
int arr2[] = {
3,
1,
2,
4,
5,
1
};
System.out.println("\n\nComplexity O(N)\n");
System.out.println("\nMaxCapacity: " + maxCapacity(arr1));
System.out.println("\n\nMaxCapacity: " + maxCapacity(arr2));
}
}
Time complexity: O(N)
Array is traversed only once
Space complexity: O(1)
No extra space is used so the complexity is constant
Code Snippet