Leetcode Problem: Container With Most Water
Objective:
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.
Pattern: Two Pointer Technique
Approach:
- Set a left and right pointer. left pointer = 0, right pointer = array.length - 1.
- Create a maxArea variable to keep track of maximum area between left and right pointers.
- Create a width variable to keep track of the width between left and right pointers.
- Calculate the for the max area, get the shorter pointer and multiple it by the width.
- If left < right pointer then increment left pointer and decrement width.
- If left > right pointer then decrement right pointer and decrement width.
Big-O Notation:
Time Complexity: O(n)
We have iterate n times for each element.
Space Complexity: O(1)
We do not use any additional data structures for storage.
Code:
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = Integer.MIN_VALUE;
int width = height.length - 1;
while(left < right){
int less = Math.min(height[left], height[right]);
maxArea = Math.max(maxArea, less * width);
if(height[left] <= height[right]){
left++;
} else if (height[left] > height[right]) {
right--;
}
width--;
}
return maxArea;
}
}
Top comments (0)