LeetCode Problem #11 Container With Most Water

LeetCode Problem #11 Container With Most Water

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Problem Link

Solution Number One O(n^2) Brute Force :

1. Try all valid combinations 
2. outer loop start from i = 0 to length of array
3. inner loop start from j = i+1 to length of array 
4. compare current area with new area and choose max.
5. return max area.

Solution Number Two O(n) :

Linear Solution greedy algorithm:

1. calculating area it is rectangle 
1. width = rightIndex - leftIndex
2. height = min (height[rightIndex], height[leftIndex])
2. select max area 
3. update leftIndex and rightIndex 
1. if height[rightIndex] > height[leftIndex] this means we should search for another left leftIndex++
2. else we need to search for another right rightIndex-- 
4. return max area 

Thank you,
AhmedG.