LeetCode #11: Container With Most Water

https://leetcode.com/problems/container-with-most-water/

To solve this problem, we can use the two-pointer technique. We start with the two pointers at the beginning and end of the input array. We calculate the area between the two pointers and update the maximum area seen so far. We then move the pointer that is pointing to the smaller height inwards and repeat the process until the two pointers meet.

Steps to solve the problem:

1. Create a function called “maxArea” that takes an array of non-negative integers height as input.
2. Create two pointers, left and right, pointing to the beginning and end of the input array, respectively.
3. Initialize a variable called “max_area” to zero to store the maximum area seen so far.
4. While the two pointers have not crossed each other:
5. Calculate the area between the two pointers by multiplying the minimum of the heights at the two pointers with the distance between them.
6. Update the “max_area” variable with the maximum of the current area and the maximum area seen so far.
7. Move the pointer that is pointing to the smaller height inwards.
8. Return the “max_area” variable.

Python Code: Here’s the Python code to solve the Container With Most Water problem:

class Solution:
    def maxArea(self, height: List[int]) -> int:

        left, right = 0, len(height) - 1
        max_area = 0
        while left < right:
            curr_area = min(height[left], height[right]) * (right - left)
            max_area = max(max_area, curr_area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_area

Time and Space Complexity:

The time complexity of this solution is O(n), where n is the length of the input array. This is because we are using the two-pointer technique to iterate through the input array only once.

The space complexity of this solution is O(1), as we are using constant extra space to store the two pointers and the maximum area seen so far.