DEV Community

Tammy Vo
Tammy Vo

Posted on β€’ Edited on

3 2

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

AWS Q Developer image

Your AI Code Assistant

Generate and update README files, create data-flow diagrams, and keep your project fully documented. Built to handle large projects, Amazon Q Developer works alongside you from idea to production code.

Get started free in your IDE

Top comments (0)

AWS GenAI LIVE image

Real challenges. Real solutions. Real talk.

From technical discussions to philosophical debates, AWS and AWS Partners examine the impact and evolution of gen AI.

Learn more

πŸ‘‹ Kindness is contagious

Please leave a ❀️ or a friendly comment on this post if you found it helpful!

Okay