Container With Most Water
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 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: 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
.
Example 2:
Input: height = [1,1]
Output: 1
Constraints:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
Solution
We will implement this question using opposite two-pointers with the following steps.
- Initialize
left
andright
pointer to0
andlen(height)-1
. Initializemax_area = 0
. - Perform two pointers selections (steps 3-4) while
left < right
. - The
max_area
is the maximum of the currentmax_area
and(right - left) * min(height[left], height[right])
- Update
left += 1
ifheight[left] < height[right]
, elseright -= 1
. - Return the final
max_area
.
The logic behind this two pointers algorithm is that we start from the two ends and work our way into the middle.
Given two vertical lines, the area of that container is (right - left) * min(height[left], height[right])
.
So the only way we can hold more water when the horizontal distance between two pointers decrease, is to increase the vertical distance min(height[left], height[right])
.
We wish to keep the taller line from height[left], height[right]
and continue searching for another line that's taller than the lower line, which potentially forms a larger container.
Implementation
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
max_area = 0
while left < right:
max_area = max(max_area, (right - left) * min(height[left], height[right]))
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorGiven a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!