Given N non-negative integers a_{1},a_{2},....a_{n} where each represents a point at coordinate (i, a_{i}). N vertical lines are drawn such that the two endpoints of line i is at (i, a_{i}) and (i,0). Find two lines, which together with x-axis forms a container, such that it contains the most water. 
Note : In Case of single verticle line it will not be able to hold water.
Example 1:
Input:
N = 4
a[] = {1,5,4,3}
Output: 6
Explanation: 5 and 3 are distance 2 apart.
So the size of the base = 2. Height of
container = min(5, 3) = 3. So total area
= 3 * 2 = 6.
Example 2:
Input:
N = 5
a[] = {3,1,2,4,5}
Output: 12
Explanation: 5 and 3 are distance 4 apart.
So the size of the base = 4. Height of
container = min(5, 3) = 3. So total area
= 4 * 3 = 12.
Your Task :
You only need to implement the given function maxArea. Do not read input, instead use the arguments given in the function and return the desired output. 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1<=N<=10^{5}
1<=A[i]<=10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Mathematics

Ad-hoc

Starter code: #User function Template for python3







def maxArea(A,le):

    #code here

Solutions:
def maxArea(A, le):
	max_area = 0
	l = 0
	r = len(A) - 1
	while l < r:
		max_area = max(max_area, (r - l) * min(A[r], A[l]))
		if A[l] <= A[r]:
			l += 1
		else:
			r -= 1
	return max_area


def maxArea(height, le):
	lo = 0
	hi = len(height) - 1
	area = hi * min(height[lo], height[hi])
	while lo < hi:
		if height[lo] <= height[hi]:
			lo += 1
		elif height[lo] > height[hi]:
			hi -= 1
		area = max(area, (hi - lo) * min(height[lo], height[hi]))
	return area


def maxArea(arr, n):
	i = 0
	j = n - 1
	area = 0
	while i < j:
		area = max(area, min(arr[i], arr[j]) * (j - i))
		if arr[i] < arr[j]:
			i = i + 1
		else:
			j = j - 1
	return area


def maxArea(A, le):
	maxArea = 0
	start = 0
	end = le - 1
	while end > start:
		area = (end - start) * min(A[end], A[start])
		maxArea = max(area, maxArea)
		if A[end] > A[start]:
			start += 1
		else:
			end -= 1
	return maxArea


def maxArea(arr, le):
	i = 0
	j = n - 1
	maxi = 0
	while i <= j:
		water = min(arr[i], arr[j]) * (j - i)
		maxi = max(maxi, water)
		if arr[i] > arr[j]:
			j -= 1
		else:
			i += 1
	return maxi


def maxArea(a, le):
	start = 0
	end = le - 1
	res = 0
	while start < end:
		area = (end - start) * min(a[start], a[end])
		res = max(res, area)
		if a[start] < a[end]:
			start += 1
		else:
			end -= 1
	return res


def maxArea(A, le):
	i = 0
	j = le - 1
	max_area = 0
	while i < j:
		curr_area = min(A[i], A[j]) * (j - i)
		max_area = max(curr_area, max_area)
		if A[j] <= A[i]:
			j -= 1
		else:
			i += 1
	return max_area


def maxArea(A, le):
	Max = 0
	(l, r) = (0, len(A) - 1)
	while l <= r:
		if A[r] < A[l]:
			Max = max(Max, A[r] * (r - l))
			r -= 1
		else:
			Max = max(Max, A[l] * (r - l))
			l += 1
	return Max


def maxArea(A, le):
	result = 0
	i = 0
	j = n - 1
	while i < j:
		volume = min(A[i], A[j]) * abs(i - j)
		result = max(result, volume)
		if A[i] < A[j]:
			i += 1
		else:
			j -= 1
	return result


def maxArea(array, n):
	result = 0
	left = 0
	right = n - 1
	while left < right:
		if array[left] <= array[right]:
			new = array[left] * (right - left)
			left += 1
		else:
			new = array[right] * (right - left)
			right -= 1
		result = max(result, new)
	return result


def maxArea(A, le):
	(l, r) = (0, le - 1)
	max_area = 0
	while l < r:
		h = min(A[l], A[r])
		cur_area = h * (r - l)
		max_area = max(cur_area, max_area)
		if A[l] < A[r]:
			l += 1
		else:
			r -= 1
	return max_area


def maxArea(height, le):
	maxx = 0
	l = 0
	r = len(height) - 1
	while l < r:
		if height[l] <= height[r]:
			pick = height[l]
			area = pick * (r - l)
			l = l + 1
		else:
			pick = height[r]
			area = pick * (r - l)
			r = r - 1
		maxx = max(maxx, area)
	return maxx


def maxArea(arr, n):
	water = 0
	i = 0
	j = n - 1
	while i < j:
		water = max(min(arr[i], arr[j]) * (j - i), water)
		if arr[i] <= arr[j]:
			i += 1
		elif arr[j] < arr[i]:
			j -= 1
	return water


def maxArea(A, le):
	l = 0
	r = n - 1
	area = 0
	while l <= r:
		w = r - l
		h = min(A[l], A[r])
		area = max(area, w * h)
		if A[l] < A[r]:
			l += 1
		else:
			r -= 1
	return area


def maxArea(A, le):
	i = 0
	j = le - 1
	ans = 0
	while i < j:
		if A[i] < A[j]:
			ans = max(ans, min(A[i], A[j]) * (j - i))
			i += 1
		else:
			ans = max(ans, min(A[i], A[j]) * (j - i))
			j -= 1
	return ans


def maxArea(A, le):
	(left, right) = (0, len(A) - 1)
	res = 0
	while left < right:
		area = (right - left) * min(A[left], A[right])
		res = max(res, area)
		if A[left] < A[right]:
			left += 1
		else:
			right -= 1
	return res


def maxArea(arr, n):
	start = 0
	end = n - 1
	ans = 0
	while start < end:
		ans = max(min(arr[start], arr[end]) * (end - start), ans)
		if arr[start] < arr[end]:
			start += 1
		else:
			end -= 1
	return ans


def maxArea(A, le):
	maxWater = 0
	(i, j) = (0, le - 1)
	while i < j:
		water = (j - i) * min(A[i], A[j])
		maxWater = max(water, maxWater)
		if A[i] < A[j]:
			i += 1
		else:
			j -= 1
	return maxWater


def maxArea(A, le):
	mx = 0
	i = 0
	j = le - 1
	while i < j:
		mi = min(A[i], A[j])
		base = j - i
		area = mi * base
		mx = max(mx, area)
		if A[i] < A[j]:
			i += 1
		else:
			j -= 1
	return mx


def maxArea(arr, n):
	if n == 1:
		return 0
	l = 0
	h = n - 1
	maxi = float('-inf')
	while l < h:
		height = min(arr[l], arr[h])
		width = h - l
		maxi = max(maxi, height * width)
		if arr[l] < arr[h]:
			l += 1
		else:
			h -= 1
	return maxi


def maxArea(a, le):
	l = 0
	r = len(a) - 1
	ans = 0
	while l < r:
		if a[l] < a[r]:
			ans = max(ans, (r - l) * a[l])
			l += 1
		else:
			ans = max(ans, (r - l) * a[r])
			r -= 1
	return ans


def maxArea(A, le):
	maxarea = 0
	start = 0
	end = le - 1
	while start < le - 1 and start < end:
		height = min(A[start], A[end])
		base = end - start
		area = base * height
		if area > maxarea:
			maxarea = area
		if A[start] < A[end]:
			start += 1
		else:
			end -= 1
	return maxarea


def maxArea(height, le):
	n = len(height)
	l = 0
	r = n - 1
	res = 0
	while l < r:
		res = max(res, min(height[l], height[r]) * (r - l))
		if height[l] <= height[r]:
			l += 1
		else:
			r -= 1
	return res


def maxArea(A, le):
	i = 0
	j = le - 1
	area1 = 0
	while i < j:
		area = (j - i) * min(A[i], A[j])
		if area > area1:
			area1 = area
		if A[i] > A[j]:
			j = j - 1
		else:
			i = i + 1
	return area1


def maxArea(A, le):
	i = 0
	j = le - 1
	maxarea = 0
	currmax = 0
	while i < j:
		currmax = min(A[i], A[j]) * (j - i)
		maxarea = max(currmax, maxarea)
		if A[i] > A[j]:
			j = j - 1
		else:
			i = i + 1
	return maxarea


def maxArea(A, le):
	max_val = 0
	(l, r) = (0, len(A) - 1)
	while l < r:
		area = min(A[l], A[r]) * (r - l)
		max_val = max(area, max_val)
		if A[l] < A[r]:
			l += 1
		else:
			r -= 1
	return max_val


def maxArea(A, le):
	(l, r, ans) = (0, le - 1, 0)
	while l <= r:
		area = min(A[r], A[l]) * (r - l)
		ans = max(ans, area)
		if A[r] > A[l] and l < r:
			l += 1
		else:
			r -= 1
	return ans


def maxArea(A, le):
	left = 0
	right = le - 1
	ma = 0
	while left < right:
		area = min(A[left], A[right]) * (right - left)
		ma = max(ma, area)
		if A[left] < A[right]:
			left += 1
		else:
			right -= 1
	return ma


import sys

def maxArea(a, n):
	l = 0
	r = n - 1
	max_area = float('-inf')
	while l <= r:
		max_area = max(max_area, min(a[l], a[r]) * (r - l))
		if a[l] <= a[r]:
			l += 1
		else:
			r -= 1
	return max_area


def maxArea(A, le):
	left = 0
	right = le - 1
	max_area = 0
	while left < right:
		w = right - left
		h = min(A[left], A[right])
		max_area = max(max_area, w * h)
		if A[left] <= A[right]:
			left += 1
		else:
			right -= 1
	return max_area


def maxArea(A, le):
	(leftMax, rightMax) = (A[0], A[-1])
	(l, r) = (0, len(A) - 1)
	res = 0
	while l < r:
		if A[l] <= A[r]:
			leftMax = max(leftMax, A[l])
			res = max(res, (r - l) * leftMax)
			l += 1
		else:
			rightMax = max(rightMax, A[r])
			res = max(res, (r - l) * rightMax)
			r -= 1
	return res


def maxArea(A, le):
	n = len(A)
	max_area = 0
	l = 0
	r = n - 1
	while l < r:
		x = r - l
		area = 0
		if A[l] <= A[r]:
			area = x * A[l]
			l += 1
		else:
			area = x * A[r]
			r -= 1
		max_area = max(max_area, area)
	return max_area


def maxArea(A, N):
	ans = 0
	(l, r) = (0, N - 1)
	for i in range(N):
		minimum = min(A[l], A[r]) * (r - l)
		ans = max(ans, minimum)
		if A[l] < A[r]:
			l += 1
		else:
			r -= 1
	return ans


def maxArea(A, le):
	if not A:
		return 0
	(l, r) = (0, len(A) - 1)
	ans = 0
	while l < r:
		area = min(A[l], A[r]) * (r - l)
		ans = max(ans, area)
		if A[l] < A[r]:
			l += 1
		else:
			r -= 1
	return ans


def maxArea(height, le):
	left = 0
	right = len(height) - 1
	maxArea = 0
	while left < right:
		area = min(height[left], height[right]) * (right - left)
		maxArea = max(maxArea, area)
		if height[left] < height[right]:
			left += 1
		else:
			right -= 1
	return maxArea


def maxArea(A, le):
	max_area = 0
	(l, r) = (0, le - 1)
	while l <= r:
		area = (r - l) * min(A[l], A[r])
		if area > max_area:
			max_area = area
		if A[l] < A[r]:
			l += 1
		else:
			r -= 1
	return max_area


def maxArea(A, le):
	(low, hi, maxArea) = (0, le - 1, 0)
	while low < hi:
		currArea = min(A[low], A[hi]) * (hi - low)
		maxArea = max(maxArea, currArea)
		if A[low] > A[hi]:
			hi -= 1
		else:
			low += 1
	return maxArea


def maxArea(A, n):
	if n == 1:
		return 0
	start = 0
	end = n - 1
	area = 0
	while start < end:
		base = end - start
		height = min(A[start], A[end])
		area = max(area, base * height)
		if A[start] < A[end]:
			start += 1
		else:
			end -= 1
	return area


def maxArea(A, le):
	ans = 0
	left = 0
	right = len(A) - 1
	while left <= right:
		cur = min(A[left], A[right]) * (right - left)
		ans = max(ans, cur)
		if A[left] < A[right]:
			left += 1
		else:
			right -= 1
	return ans


def maxArea(A, le):
	res = 0
	(l, r) = (0, le - 1)
	while l < r:
		area = (r - l) * min(A[l], A[r])
		res = max(res, area)
		if A[l] < A[r]:
			l += 1
		else:
			r -= 1
	return res


def maxArea(A, le):
	height = A
	i = 0
	j = len(height) - 1
	prev = 0
	while i <= j:
		if min(height[i], height[j]) * (j - i) > prev:
			prev = min(height[i], height[j]) * (j - i)
			if height[i] < height[j]:
				i += 1
			else:
				j -= 1
		elif height[i] < height[j]:
			i += 1
		else:
			j -= 1
	return prev


def maxArea(height, n):
	pre_area = 0
	(i, j) = (0, n - 1)
	while i < j:
		h = min(height[i], height[j])
		w = j - i
		area = h * w
		max_area = max(pre_area, area)
		pre_area = max_area
		if height[i] > height[j]:
			j -= 1
		else:
			i += 1
	return pre_area


def maxArea(A, le):
	i = 0
	j = le - 1
	max1 = 0
	while i < j:
		if A[i] > A[j]:
			max1 = max(max1, (j - i) * A[j])
			j -= 1
		else:
			max1 = max(max1, (j - i) * A[i])
			i += 1
	return max1


def maxArea(height, le):
	n = len(height)
	l = 0
	r = n - 1
	val = 0
	maxi = 0
	while l < r:
		val = max(val, (r - l) * min(height[r], height[l]))
		if height[l] < height[r]:
			l += 1
		else:
			r -= 1
	return val


def maxArea(height, le):
	i = 0
	j = len(height) - 1
	maxAmt = 0
	while j > i:
		iH = height[i]
		jH = height[j]
		if iH > jH:
			cal = jH * (j - i)
			j -= 1
		else:
			cal = iH * (j - i)
			i += 1
		if cal > maxAmt:
			maxAmt = cal
	return maxAmt


def maxArea(A, le):
	start = 0
	end = le - 1
	ans = 0
	while start < end:
		res = min(A[start], A[end]) * (end - start)
		ans = max(ans, res)
		if A[start] < A[end]:
			start += 1
		elif A[end] < A[start]:
			end -= 1
		elif A[start] == A[end]:
			start += 1
	return ans


def maxArea(h, n):
	l = 0
	r = n - 1
	ans = 0
	while l < r:
		curr_h = min(h[l], h[r]) * (r - l)
		ans = max(ans, curr_h)
		if h[l] < h[r]:
			l += 1
		else:
			r -= 1
	return ans


def maxArea(height, le):
	lp = 0
	rp = le - 1
	maxArea = 0
	while lp < rp:
		maxArea = max(maxArea, min(height[lp], height[rp]) * (rp - lp))
		if height[lp] > height[rp]:
			rp -= 1
		else:
			lp += 1
	return maxArea


def maxArea(a, le):
	Max = 0
	i = 0
	j = len(a) - 1
	while i < j:
		res = min(a[i], a[j]) * (j - i)
		Max = max(Max, res)
		if a[i] < a[j]:
			i += 1
		else:
			j -= 1
	return Max


def maxArea(A, le):
	max_water = 0
	l = 0
	r = len(A) - 1
	while l < r:
		(hl, hr) = (A[l], A[r])
		curr_water = min(hl, hr) * (r - l)
		if curr_water > max_water:
			max_water = curr_water
		if hl <= hr:
			l += 1
		if hr <= hl:
			r -= 1
	return max_water


def maxArea(a, n):
	l = 0
	r = n - 1
	ans = 0
	while l < r:
		temp = min(a[l], a[r]) * (r - l)
		ans = max(ans, temp)
		if a[l] < a[r]:
			l += 1
		else:
			r -= 1
	return ans


def maxArea(A, le):

	def getArea(startIndex, endIndex):
		return endIndex - startIndex
	maxArea = 0
	leftCont = 0
	rightCont = le - 1
	while leftCont < rightCont:
		if A[leftCont] <= A[rightCont]:
			maxArea = max(maxArea, getArea(leftCont, rightCont) * A[leftCont])
			leftCont += 1
		else:
			maxArea = max(maxArea, getArea(leftCont, rightCont) * A[rightCont])
			rightCont -= 1
	return maxArea


def maxArea(arr, n):
	(p1, p2, ans) = (0, n - 1, 0)
	while p1 <= p2:
		ans = max(ans, min(arr[p1], arr[p2]) * (p2 - p1))
		if arr[p1] <= arr[p2]:
			p1 += 1
		else:
			p2 -= 1
	return ans


def maxArea(A, le):
	height = A
	m = 0
	i = 0
	j = len(height) - 1
	while i < j:
		width = abs(i - j)
		area = width * min(height[i], height[j])
		m = max(area, m)
		if height[i] > height[j]:
			j -= 1
		else:
			i += 1
	return m


def maxArea(a, le):
	maxi = 0
	i = 0
	j = le - 1
	while i < j:
		h = min(a[i], a[j])
		val = (j - i) * h
		maxi = max(maxi, val)
		if a[i] < a[j]:
			i += 1
		else:
			j -= 1
	return maxi


def maxArea(arr, n):
	i = 0
	j = len(arr) - 1
	maxi = 0
	while i < j:
		h = min(arr[i], arr[j])
		area = (j - i) * h
		maxi = max(maxi, area)
		if arr[i] <= arr[j]:
			i += 1
		else:
			j -= 1
	return maxi


def maxArea(A, le):
	r = le - 1
	l = 0
	a = 0
	while l < r:
		a = max(a, min(A[l], A[r]) * (r - l))
		if A[l] < A[r]:
			l += 1
		else:
			r -= 1
	return a


def maxArea(A, le):
	low = 0
	high = le - 1
	area = 0
	ans = 0
	while low < high:
		area = min(A[low], A[high]) * (high - low)
		if A[low] < A[high]:
			low += 1
		else:
			high -= 1
		ans = max(ans, area)
	return ans


def maxArea(A, n):
	l = 0
	r = n - 1
	area = 0
	while l < r:
		area = max(area, min(A[l], A[r]) * (r - l))
		if A[l] < A[r]:
			l += 1
		else:
			r -= 1
	return area


def maxArea(A, le):
	n = len(A)
	l = 0
	r = n - 1
	water = 0
	while l < r:
		water = max(water, min(A[l], A[r]) * (r - l))
		if A[l] < A[r]:
			l += 1
		else:
			r -= 1
	return water


def maxArea(a, le):
	i = 0
	j = len(a) - 1
	maxi = 0
	while i < j:
		h = min(a[i], a[j])
		res = (j - i) * h
		maxi = max(maxi, res)
		if a[i] <= a[j]:
			i += 1
		else:
			j -= 1
	return maxi


def maxArea(arr, le):
	(l, r) = (0, le - 1)
	ans = 0
	area = 0
	while l < r:
		h = min(arr[l], arr[r])
		w = r - l
		area = h * w
		ans = max(ans, area)
		if arr[l] < arr[r]:
			l += 1
		else:
			r -= 1
	return ans


def maxArea(A, le):
	a = A
	left = 0
	right = len(a) - 1
	ans = 0
	while left < right:
		if a[left] < a[right]:
			ans = max(ans, (right - left) * a[left])
			left += 1
		else:
			ans = max(ans, (right - left) * a[right])
			right -= 1
	return ans


def maxArea(A, le):
	i = 0
	j = len(A) - 1
	l = []
	while i < j:
		l.append((j - i) * min(A[i], A[j]))
		if A[i] < A[j]:
			i += 1
		else:
			j -= 1
	if len(l) == 0:
		return 0
	return max(l)


def maxArea(A, le):
	(i, j) = (0, le - 1)
	mx = 0
	while i < j:
		h = min(A[i], A[j])
		mx = max(mx, h * (j - i))
		if A[i] < A[j]:
			i += 1
		elif A[i] > A[j]:
			j -= 1
		else:
			i += 1
			j -= 1
	return mx


def maxArea(nums, n):
	maxCtnr = 0
	(l, r) = (0, n - 1)
	while l < r:
		size = (r - l) * min(nums[l], nums[r])
		if size > maxCtnr:
			maxCtnr = size
		if nums[r] > nums[l]:
			l += 1
		else:
			r -= 1
	return maxCtnr


def maxArea(arr, le):
	(start, end) = (0, le - 1)
	res = 0
	while start < end:
		height = min(arr[start], arr[end])
		width = end - start
		res = max(res, height * width)
		if arr[start] < arr[end]:
			start += 1
		else:
			end -= 1
	return res