Solving Leetcode 11: Container With Most Water

Problem:

From Leetcode

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.

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.

From the start we can tell that this is an array question. When it comes to this question it seems that we will be comparing elements with each other. One of the first approach to this problem is to use a double for loop. Unfortunately we know that a double for loop runs in O(N^2) time, which is very inefficient.

2-Pointer Solution

The ideal solution would be to have two pointers, we could call them start and end. The start pointer will start at the beginning of the array (index 0) and the end pointer will start at the end. (height.length -1). Note that we want the index of the array start and end, NOT the element.

Next we know that by starting at each end we can check whether or not the previous or next element is higher or or not. If so we set the new pointer to higher element and update the area.

  1. Keep two index, start= 0 and end = n-1 and a value area that stores the maximum area.
  2. Run a while loop until first is less than the last.
  3. Update the area with maximum of area and min(array[first] , array[last])*(last-first)
  4. if the value at array[first] is greater the array[last] then update last as last – 1 else update first as first + 1
  5. Print the maximum area.

Code Here:

class Solution {
    public int maxArea(int[] height) {

        int area = 0;

        int start = 0;

        int end = height.length - 1;

        while(start < end){
            int top = Math.min(height[start], height[end]);

            int newArea = top*(end-start);
            area = Math.max(area, newArea);

            if(height[start]< height[end]){
                start++;
            }
            else{
                end--;
            }
        }
     return area;   
    }
}

We can find the maximum area under a histogram using two pointers. The pointers start at the beginning and end of the histogram, and we move them inward until they meet. At each step, we calculate the area of the rectangle formed by the two pointers and the current height of the histogram. The maximum area is the largest area we calculate.

This algorithm is simple to implement and has a time complexity of O(n). It is a good choice for finding the maximum area under a histogram when the histogram is large.

Related

How to 10x Your LLM Prompting With DSPy

Tired of spending countless hours tweaking prompts for large...

Google Announces A Cost Effective Gemini Flash

At Google's I/O event, the company unveiled Gemini Flash,...

WordPress vs Strapi: Choosing the Right CMS for Your Needs

With the growing popularity of headless CMS solutions, developers...

JPA vs. JDBC: Comparing the two DB APIs

Introduction The eternal battle rages on between two warring database...

Meta Introduces V-JEPA

The V-JEPA model, proposed by Yann LeCun, is a...

Subscribe to our AI newsletter. Get the latest on news, models, open source and trends.
Don't worry, we won't spam. 😎

You have successfully subscribed to the newsletter

There was an error while trying to send your request. Please try again.

Lusera will use the information you provide on this form to be in touch with you and to provide updates and marketing.