11. Container With Most Water

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

Python

Brute Force (Timelimit Exceed)

• Time: O(NlogN)
• Space: O(1)

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_amount = 0
        for i in range(len(height)):
            amount = 0
            for j in range(i, len(height)):
                amount = (j-i) * min(height[i], height[j])
                max_amount = max(max_amount, amount)
        return max_amount

Two Pointer

• Time: O(N)
• Space: O(1)

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_amount = 0
        l, r = 0, len(height)-1

        while l < r:
            amount = min(height[l], height[r]) * (r-l)
            max_amount = max(max_amount, amount)

            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return max_amount