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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Amortized analysis

Greedy algorithms

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

Solutions:
class Solution:

	def maxArea(self, height):
		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):
		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):
		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


class Solution:

	def maxArea(self, height):
		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):
		max_area = 0
		lo = 0
		hi = len(items) - 1
		while lo < hi:
			height_a = items[lo]
			height_b = items[hi]
			width = hi - lo
			height = min(height_a, height_b)
			area = height * width
			if area > max_area:
				max_area = area
			if height_a < height_b:
				lo += 1
			else:
				hi -= 1
		return max_area


class Solution:

	def maxArea(self, height):
		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):
		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):
		left = 0
		right = len(height) - 1
		max_area = 0
		while left < right:
			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):
		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)
		return ans