📌Problem

Given n non-negative integers $a_1, a_2, ..., a_n$ , where each represents a point at coordinate (i, $a_i$). n vertical lines are drawn such that the two endpoints of the line i is at (i, $a_i$) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Example 1:

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.

Example 2:

Input: height = [1,1]
Output: 1

Example 3:

Input: height = [4,3,2,1,4]
Output: 16

Example 4:

Input: height = [1,2,1]
Output: 2

Constraints:

• n = height.length
• 2 <= n <= $3 * 10^4$
• 0 <= height[i] <= $3 * 10^4$

leetcode 에서 풀기

---

📝Solution

✏️ Brute force

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

• Time complexity : $O(N^2)$

✏️ Two pointer approach(Improved brute force)

class Solution:
    def maxArea(self, height: List[int]) -> int:
        
        left=0
        right=len(height)-1
        max_area=0
        while (right-left>0) :
            max_area=max(max_area,(right-left)*min(height[left],height[right]))
                
            if height[left]>=height[right]: # The right is shorter than left
                right-=1
            else: # The left is shorter than right
                left+=1
            
        return max_area

• Time complexity : $O(N)$
• 1번의 방법을 개선하기 위해서 left ,right two pointer 와 while 문을 통해 양 끝에서 동시 비교 한다.

1. width 가 가장 긴 container 부터 시작하여 height[left],height[right] 중 짧은 height 를 가져온다. 그래야만 container 의 물이 넘치지 않는다.

2. height[left] 와 height[right] 중 더 짧은 포인터 를 옮겨 그 다음을 순회한다. 즉, left라면 left+1 , right 라면 right-1 한다. container는 짧은 height 를 기준으로 물이 담아지기 때문에, 짧은 포인터를 옮겨야 그 다음 container의 크기가 커질 가능성이 있다.