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[0], Q[-1])*(len(Q)-1)
            res = max(res,this_res)
            if Q[0]<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