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

Data Scientist/MLE/SWE @takemobi