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 

	class Solution {
	public int maxArea(int[] height) {
	int left = 0;
	int right = height.length-1;
	int area = 0;
	while (left < right) {
	area = Math.max(area, (right-left) * Math.min(height[right], height[left]));
	if (height[right] > height[left]) {
	left++;
	}else {
	right--;
	}
	}
	return area;
	}
	}

view raw ContainerWithMostWater.java hosted with ❤ by GitHub

Thank you,
AhmedG.