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

Note: You may not slant the container and n is at least 2.

Difficulty: interview

Starter code:

class Solution:
    def maxArea(self, height: List[int]) -> int:
        

Solutions:
class Solution:
     def maxArea(self, height):
         """
         :type height: List[int]
         :rtype: int
         """
         # l = []
         # maxH = 0
         # for i in range(len(height)-1, -1, -1):
         #     if height[i] > maxH:
         #         maxH = height[i]
         #         l.append((i, maxH))
         # maxArea = 0
         # for i in range(len(height)):
         #     for jl in l:
         #         if i >= jl[0]:
         #             break
         #         area = (jl[0] - i) * min(height[i], jl[1])
         #         if area > maxArea:
         #             maxArea = area
         # return maxArea
         
         left = 0
         right = len(height) - 1
         if height[left] > height[right]:
             minH = height[right]
             minIndex = right
         else:
             minH = height[left]
             minIndex = left
         area = (right - left) * minH
         maxArea = area
         
         while left != right:
             if minIndex == left:
                 while left != right:
                     left += 1
                     if height[left] > minH:
                         if height[left] > height[right]:
                             minH = height[right]
                             minIndex = right
                         else:
                             minH = height[left]
                             minIndex = left
                         break
                 area = (right - left) * minH
             else:
                 while left != right:
                     right -= 1
                     if height[right] > minH:
                         if height[right] > height[left]:
                             minH = height[left]
                             minIndex = left
                         else:
                             minH = height[right]
                             minIndex = right
                         break
                 area = (right - left) * minH
             if area > maxArea:
                 maxArea = area
         return maxArea

class Solution:
     def maxArea(self, height):
         """
         :type height: List[int]
         :rtype: int
         """
         left_index = 0
         right_index = len(height) - 1
         water = 0
         while True:
             if left_index >= right_index:
                 break
             left_height = height[left_index]
             right_height = height[right_index]
             water = max(water, (right_index - left_index) * min(left_height, right_height))
             if left_height < right_height:
                 left_index += 1
             else:
                 right_index -= 1
         return water


class Solution:
     def maxArea(self, height):
         """
         :type height: List[int]
         :rtype: int
         """
         if height == []:
             return 0
         l = len(height)
         p1 = 0
         p2 = l - 1
         area = 0
         while(p1 < p2):
             if(height[p1] <= height[p2]):
                 area = max(area,height[p1] * (p2 - p1))
                 p1 += 1
             else:
                 area = max(area,height[p2] * (p2 - p1))
                 p2 -= 1
         return area


class Solution:
     def maxArea(self, height):
         left, right = 0, len(height) - 1
         area = 0
         
         while left < right:
             if height[left] <= height[right]:
                 h = height[left]
                 tmp = (right - left) * h
                 left += 1
             else:
                 h = height[right]
                 tmp = (right - left) * h
                 right -= 1
             if area < tmp:
                 area = tmp
             
         return area
         """
         :type height: List[int]
         :rtype: int
         """


class Solution:
     def maxArea(self, height):
         """
         :type height: List[int]
         :rtype: int
         """
         area = (len(height)-1)*min([height[0], height[-1]])
         left_idx = 0
         right_idx = len(height)-1
         while left_idx < right_idx:
             if height[left_idx] < height[right_idx]:
                 start = left_idx + 1
                 while start < right_idx:
                     if height[start] > height[left_idx]:
                         left_idx = start
                         area2 = (right_idx - left_idx) * min([height[left_idx], height[right_idx]])
                         if area2 > area:
                             area = area2
                         break
                     start += 1
                 if start != left_idx:
                     break
             elif height[left_idx] > height[right_idx]:
                 start = right_idx - 1
                 while start > left_idx:
                     if height[start] > height[right_idx]:
                         right_idx = start
                         area2 = (right_idx - left_idx) * min([height[left_idx], height[right_idx]])
                         if area2 > area:
                             area = area2
                         break
                     start -= 1
                 if start!= right_idx:
                     break
             else:
                 left_idx += 1
         
         return area


class Solution:
     def maxArea(self, items):
         '''
         Hi Lo Technique
         -----------------------
         Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate 
         (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and 
         (i, 0). Find two lines, which together with x-axis forms a container, such that the container
         contains the most water.
         -----------------------
         (1) Set lo and hi pointer at ends & bring them closer as results compared.
         (2) Get height for lo and hi. Keep the smallest.
         (3) Calcuate the area (smallest height * distance between lo and hi pointers) (height * width)
             If area is larger than currently stored max area, make it the max area.
         (4) Move the smallest pointer in.
         (5) Repeat steps 2-4
         (6) Return the max area
         '''              
         max_area = 0
         lo = 0
         hi = len(items)-1
         
         while(lo < hi):
             
             # get value stored for height. calculate width.
             height_a = items[lo]
             height_b = items[hi]
             width = hi - lo
             height = min(height_a, height_b)
             
             # calculate area (height * width)
             area = height * width
             if area > max_area:
                 max_area = area
             
             # move the smaller pointer in
             if height_a < height_b:
                 lo += 1
             else: 
                 hi -= 1
         
         return(max_area)        

class Solution:
     def maxArea(self, height):
         """
         :type height: List[int]
         :rtype: int
         
         idea:
         Shorter coordinate determines the water size
         """
         
         if len(height) < 2: return False
         if len(height) == 2: return min(height[0], height[1])
         
         current_highest = 0
         i, j = 0, len(height) - 1
         while i < j:
             left = height[i]
             right = height[j]
             current_highest = max(current_highest, min(left, right) * (j - i))
             if right > left:
                 i += 1
             else:
                 j -= 1
         return current_highest

class Solution:
     def maxArea(self, height):
         """
         :type height: List[int]
         :rtype: int
         """
         h = height
         most = 0
         i = 0
         j = len(h) - 1
         while i < j:
             most = max(most, (j - i) * min(h[i], h[j]))
             if h[i] < h[j]:
                 i += 1
             else:
                 j -= 1
         return most

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


class Solution:
 
     # two pointer, O(N) time
     def maxArea(self, height):
         """
         :type height: List[int]
         :rtype: int
         """
 
         left = 0
         right = len(height) -1
         max_area = 0
 
         while left < right:
 
             # area = height * width
             area = min(height[left], height[right]) * (right - left)
 
             if area > max_area:
 
                 max_area = area
 
             if height[left] < height[right]:
 
                 left += 1
 
             else:
 
                 right -= 1
 
         return max_area
 


class Solution:
     def get_ans(self, l, r):
         return (r-l) * min(self.__height[l], self.__height[r])
     
     def rmove(self, l):
         for i in range(l+1, len(self.__height)):
             if self.__height[i] > self.__height[l]:
                 return i
         return 10000000
     
     def lmove(self, r):
         for i in range(r-1, -1, -1):
             if self.__height[i] > self.__height[r]:
                 return i
         return -1
         
     def maxArea(self, height):
         """
         :type height: List[int]
         :rtype: int
         """
         self.__height = height
         ans = 0
         L = 0
         R = len(height) - 1
         while L < R:
             ans = max(ans, self.get_ans(L, R))
             if height[L] <= height[R]:
                 L = self.rmove(L)
             else:
                 R = self.lmove(R)
         # L = 0
         # R = len(height) - 1
         # while L < R:
         #     ans = max(ans, self.get_ans(L, R))
         #     if height[L] < height[R]:
         #         L = self.rmove(L)
         #     else:
         #         R = self.lmove(R)
         return ans