# Trap water Container With Most Water

11. Container With Most Water

Navie solution got TLE.

time complexity is O(n²)

`class Solution:    def maxArea(self, height: List[int]) -> int:        if len(height)<2:return 0        if len(height)==2:return min(height)        N = len(height)        res = -float('inf')        for i in range(N):            for j in range(i+1, N):                w = j-i                h = min(height[i], height[j])                res = max(res, w*h)        return res`

O(n)

This one is based on the idea from here

However, as I am using a deque, the run time is still slow.

`class Solution:    def maxArea(self, height: List[int]) -> int:        if len(height)<2:return 0        if len(height)==2:return min(height)        N = len(height)        res = -float('inf')        Q = collections.deque(height)        while True:            if len(Q)==2:                res = max(min(Q), res)                break            this_res = min(Q, Q[-1])*(len(Q)-1)            res = max(res,this_res)            if Q<Q[-1]:                Q.popleft()            else:                Q.pop()        return res`

The deque is not needed. We can use two pointer to solve this problem.

`class Solution:    def maxArea(self, height: List[int]) -> int:        if len(height)<2:return 0        if len(height)==2:return min(height)        N = len(height)        res = -float('inf')        i, j =0, N-1        while True:            if j-i==1:                res = max(min(height[i:j+1]), res)                break            this_res = min(height[i], height[j])*(j-i)            res = max(res,this_res)            if height[i]<height[j]:                i+=1            else:                j-=1        return res`

More concisely from here

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

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi