20 Sep 2023, 3:56 PM
20 Sep 2023, 3:56 PM

11. Container With Most Water

#leetcode/11

You are given an integer array height 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 lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

Solution

Solution in C++ using two pointers

Since we want the container to contains the most water possible, we can use two pointers, one at the beginning of the array called start, and the other on the last element, called end. In turn, we move start forward if height[start] < height[end], otherwise we move end backwards.

int maxArea(vector<int>& height) {
	int start = 0, end = height.size() - 1;
	int maxSoFar = 0, maxHere = 0;
	while(start < end) {
		//compute the amount of water the container can store
		maxHere = min(height[start], height[end]) * (end - start);
		//if it's the largest seen so far, update
		maxSoFar = max(maxSoFar, maxHere);
		//move the smallest height forward (or backwards)
		height[start] < height[end] ? start++ : end--;
	}
	return maxSoFar;
}

Now, think about this example:

Input: height = [8, 1, 2, 3, 4, 4, 3, 2, 1, 8]

Is it really necessary to compute at each iteration the amount of water the container can store, even if its height is lower? The answer is no, because if the following heights are lower, the container will store less water!

int maxArea(vector<int>& height) {
	int start = 0, end = height.size() - 1;
	int maxSoFar = 0, minHeight = 0;
	while(start < end) {
		minHeight = min(height[start], height[end]);
		//compute the amount of water the container can store
		maxHere = minHeight * (end - start);
		//if it's the largest seen so far, update
		maxSoFar = max(maxSoFar, maxHere);
		//if the following heights are lower, the container will store less water, skip them!
		while(height[start] <= minHeight && start < end) start++;
		while(height[end] <= minHeight && start < end) end--;
	}
	return maxSoFar;
}