Container With Most Water

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:

1. Set a left and right pointer. left pointer = 0, right pointer = array.length - 1.
2. Create a maxArea variable to keep track of maximum area between left and right pointers.
3. Create a width variable to keep track of the width between left and right pointers.
4. Calculate the for the max area, get the shorter pointer and multiple it by the width.
5. If left < right pointer then increment left pointer and decrement width.
6. 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;
    }
}