Spread the love

Problem

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.

Problem Description

Given an array of heights, find the two lines that form a container, such that the container contains the most water. The two lines are defined by their start and end points (i, 0) and (i, height[i]). The goal is to find the maximum amount of water that can be stored in this container.

Solution

Finding the container with most water or two lines that can hold the most water can be achieved through a simple algorithm, called the two-pointer approach. This algorithm involves keeping two pointers, one at the beginning of the array and the other at the end of the array, and moving them towards each other. The idea behind this approach is that a higher line will always contain more water than a shorter one, so if the height of the line at the start is shorter than the height of the line at the end, we move the start pointer to the right until we find a taller line. On the other hand, if the height of the line at the end is shorter, we move the end pointer to the left until we find a taller line.

Algorithm

  1. Initialize two pointers, one at the start of the array and the other at the end.
  2. Calculate the area between the two lines by multiplying the minimum of the heights of the two lines by the distance between the pointers.
  3. If the height of the line at the start is less than the height of the line at the end, move the start pointer to the right.
  4. If the height of the line at the end is less than the height of the line at the start, move the end pointer to the left.
  5. Repeat steps 2 to 4 until the two pointers meet.
  6. Return the maximum area calculated in step 2.

C#

public int MaxArea(int[] height) {
    int start = 0;
    int end = height.Length - 1;
    int maxArea = 0;
    
    while (start < end) {
        int area = Math.Min(height[start], height[end]) * (end - start);
        maxArea = Math.Max(maxArea, area);
        
        if (height[start] < height[end]) {
            start++;
        } else {
            end--;
        }
    }
    
    return maxArea;
}

Java

class Solution {
    public int maxArea(int[] height) {
        int start = 0;
        int end = height.length - 1;
        int maxArea = 0;
        
        while (start < end) {
            int area = Math.min(height[start], height[end]) * (end - start);
            maxArea = Math.max(maxArea, area);
            
            if (height[start] < height[end]) {
                start++;
            } else {
                end--;
            }
        }
        
        return maxArea;
    }
}

C++

class Solution {
public:
    int maxArea(vector<int>& height) {
        int start = 0;
        int end = height.size() - 1;
        int maxArea = 0;
        
        while (start < end) {
            int area = min(height[start], height[end]) * (end - start);
            maxArea = max(maxArea, area);
            
            if (height[start] < height[end]) {
                start++;
            } else {
                end--;
            }
        }
        
        return maxArea;
    }
};

Javascript

var maxArea = function(height) {
    let start = 0;
    let end = height.length - 1;
    let maxArea = 0;
    
    while (start < end) {
        let area = Math.min(height[start], height[end]) * (end - start);
        maxArea = Math.max(maxArea, area);
        
        if (height[start] < height[end]) {
            start++;
        } else {
            end--;
        }
    }
    
    return maxArea;
};

Python

class Solution:
    def maxArea(self, height: List[int]) -> int:
        start = 0
        end = len(height) - 1
        maxArea = 0
        
        while start < end:
            area = min(height[start], height[end]) * (end - start)
            maxArea = max(maxArea, area)
            
            if height[start] < height[end]:
                start += 1
            else:
                end -= 1
        
        return maxArea

Time and space complexity:

The time complexity of this algorithm is O(n), as we traverse the array only once, and

The space complexity is O(1), as we only need to store the two pointers and the maximum area.

Conclusion

In conclusion, finding the two lines that can hold the most water can be achieved through the two-pointer approach, which has a time complexity of O(n) and a space complexity of O(1). This approach involves moving the two pointers towards each other, calculating the area between the lines at each step, and returning the maximum area found.


0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *