It is raining in Geek City. The height of the buildings in the city is given in an array. Calculate the amount of water  that can be collected between all the buildings.
 
Example 1:
Input: 
N = 5
Arr[] = {3, 0, 2, 0, 4}
Output: 7
Explanation:
Geek city looks like
We can trap "3 units" of water between
3 and 2, "1 unit" on top of bar 2 and
"3 units" between 2  and 4. 
 
Example 2:
Input: 
N = 12
Arr[] = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation:
The structure is like below
Trap "1 unit" between first 1 and 2,
"4 units" between first 2 and 3 and
"1 unit" between second last 1 and last 2 
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function maxWater() which takes the array of integers arr[] and n as input parameters and returns the amount of water collected.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ Arr[i] ≤ 10^{3}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def maxWater(self, arr, n):

        # code here

Solutions:
class Solution:

	def maxWater(self, arr, n):
		left = 0
		right = n - 1
		maxLeft = maxRight = totalWater = 0
		while left < right:
			if arr[left] <= arr[right]:
				if arr[left] > maxLeft:
					maxLeft = arr[left]
				else:
					totalWater += maxLeft - arr[left]
				left += 1
			else:
				if arr[right] > maxRight:
					maxRight = arr[right]
				else:
					totalWater += maxRight - arr[right]
				right -= 1
		return totalWater


class Solution:

	def maxWater(self, arr, n):
		left = 0
		right = n - 1
		water = 0
		maxleft = 0
		maxright = 0
		while left <= right:
			if arr[left] <= arr[right]:
				if arr[left] > maxleft:
					maxleft = arr[left]
				else:
					water += maxleft - arr[left]
				left += 1
			else:
				if arr[right] >= maxright:
					maxright = arr[right]
				else:
					water += maxright - arr[right]
				right -= 1
		return water


class Solution:

	def maxWater(self, arr, n):
		output = 0
		stack = []
		for item in arr:
			count = 1
			while stack and item > stack[-1][0]:
				(height, width) = stack.pop()
				if not stack:
					count = 1
					break
				count += width
				output += (min(stack[0][0], item) - height) * width
			stack.append((item, count))
		return output


class Solution:

	def maxWater(self, arr, n):
		left = [0] * n
		right = [0] * n
		left[0] = arr[0]
		right[-1] = arr[-1]
		for i in range(1, n):
			left[i] = max(left[i - 1], arr[i])
		for i in range(n - 2, -1, -1):
			right[i] = max(right[i + 1], arr[i])
		ans = 0
		for i in range(1, n - 1):
			ans += max(min(left[i], right[i]) - arr[i], 0)
		return ans


class Solution:

	def maxWater(self, arr, n):
		prv = 0
		ans = 0
		x = 0
		for i in range(1, n):
			if arr[i] >= arr[prv]:
				ans = ans + (i - prv - 1) * arr[prv] - x
				x = 0
				prv = i
			else:
				x = x + arr[i]
		if prv < n - 1:
			prv1 = n - 1
			x = 0
			for i in range(n - 2, prv - 1, -1):
				if arr[i] >= arr[prv1]:
					ans = ans + (prv1 - i - 1) * arr[prv1] - x
					x = 0
					prv1 = i
				else:
					x = x + arr[i]
		return ans


class Solution:

	def maxWater(self, arr, n):
		leftmax = [arr[0]]
		rightmax = [0] * n
		rightmax[-1] = arr[-1]
		for i in range(1, n):
			leftmax.append(max(leftmax[-1], arr[i]))
			rightmax[-(i + 1)] = max(arr[-(i + 1)], rightmax[-i])
		water = 0
		for i in range(n):
			water += min(leftmax[i], rightmax[i]) - arr[i]
		return water


class Solution:

	def maxWater(self, height, n):
		(l, r) = (0, len(height) - 1)
		leftMax = height[l]
		rightMax = height[r]
		res = 0
		while l < r:
			if leftMax < rightMax:
				l += 1
				leftMax = max(leftMax, height[l])
				res += leftMax - height[l]
			else:
				r -= 1
				rightMax = max(rightMax, height[r])
				res += rightMax - height[r]
		return res


class Solution:

	def maxWater(self, arr, n):
		height = arr
		le = len(height)
		left = [height[0]]
		right = [0] * (le - 1)
		right.append(height[le - 1])
		for i in range(1, le):
			left.append(max(left[i - 1], height[i]))
		for i in range(le - 2, -1, -1):
			right[i] = max(right[i + 1], height[i])
		for i in range(le):
			left[i] = min(left[i], right[i]) - height[i]
		return sum(left)


class Solution:

	def maxWater(self, arr, n):
		(l, r) = (0, len(arr) - 1)
		(lmax, rmax) = (arr[l], arr[r])
		res = 0
		while l < r:
			if lmax < rmax:
				l += 1
				lmax = max(lmax, arr[l])
				res += lmax - arr[l]
			else:
				r -= 1
				rmax = max(rmax, arr[r])
				res += rmax - arr[r]
		return res


class Solution:

	def maxWater(self, arr, n):
		(max1, max2) = ([], [])
		(max3, max4, water) = (arr[0], arr[-1], 0)
		for i in range(n):
			if arr[i] > max3:
				max3 = arr[i]
				max1.append(max3)
			else:
				max1.append(max3)
		for i in range(n - 1, -1, -1):
			if arr[i] > max4:
				max4 = arr[i]
				max2.append(max4)
			else:
				max2.append(max4)
		max2.reverse()
		for i in range(n):
			water += min(max1[i], max2[i]) - arr[i]
		return water


class Solution:

	def maxWater(self, arr, n):
		min_height = 0
		max_height = 0
		max_index = 0
		ans = 0
		for i in range(n):
			if max_height < arr[i]:
				max_height = arr[i]
				max_index = i
		for i in range(max_index):
			if min_height > arr[i]:
				ans += min_height - arr[i]
			else:
				min_height = arr[i]
		min_height = 0
		for i in range(n - 1, max_index, -1):
			if min_height > arr[i]:
				ans += min_height - arr[i]
			else:
				min_height = arr[i]
		return ans


class Solution:

	def maxWater(self, arr, n):
		leftMax = [0] * n
		rightMax = [0] * n
		for i in range(1, n):
			leftMax[i] = max(leftMax[i - 1], arr[i - 1])
			rightMax[n - i - 1] = max(rightMax[n - i], arr[n - i])
		ans = 0
		for i in range(1, n - 1):
			water = min(leftMax[i], rightMax[i]) - arr[i]
			if water > 0:
				ans += water
		return ans


class Solution:

	def maxWater(self, arr, n):
		lmax = [arr[0]]
		lmaxi = arr[0]
		rmax = [arr[-1]]
		rmaxi = arr[-1]
		for i in range(1, n):
			if arr[i] > lmaxi:
				lmaxi = arr[i]
			lmax.append(lmaxi)
			if arr[n - 1 - i] > rmaxi:
				rmaxi = arr[n - 1 - i]
			rmax.append(rmaxi)
		rmax = rmax[::-1]
		total = 0
		for i in range(1, n - 1):
			total += min(lmax[i], rmax[i]) - arr[i]
		return total


class Solution:

	def maxWater(self, arr, n):
		l = 0
		r = n - 1
		i = 0
		j = 0
		k = []
		while l <= r:
			if arr[l] <= arr[r]:
				if arr[l] > i:
					i = arr[l]
				else:
					k.append(i - arr[l])
				l += 1
			else:
				if arr[r] >= j:
					j = arr[r]
				else:
					k.append(j - arr[r])
				r -= 1
		return sum(k)


class Solution:

	def maxWater(self, arr, n):
		lf = []
		m = arr[0]
		for x in arr:
			m = max(m, x)
			lf.append(m)
		rf = []
		mr = arr[-1]
		for i in range(n - 1, -1, -1):
			mr = max(mr, arr[i])
			rf.append(mr)
		rf1 = rf[::-1]
		s = 0
		for i in range(n):
			s += min(rf1[i], lf[i]) - arr[i]
		return s


class Solution:

	def maxWater(self, arr, n):
		g = []
		m = -1
		for i in arr:
			if i > m:
				m = i
			g.append(m)
		k = []
		m = -1
		for i in range(n - 1, -1, -1):
			if arr[i] > m:
				m = arr[i]
			k.append(m)
		k = k[::-1]
		s = 0
		for i in range(n):
			s += min(g[i], k[i]) - arr[i]
		return s


class Solution:

	def maxWater(self, arr, n):
		m = 0
		left = []
		right = []
		for i in range(len(arr)):
			if m < arr[i]:
				m = arr[i]
			left.append(m)
		m = 0
		for i in range(len(arr) - 1, -1, -1):
			if m < arr[i]:
				m = arr[i]
			right.append(m)
		right = list(reversed(right))
		s = 0
		for i in range(len(left)):
			s += min(left[i], right[i]) - arr[i]
		return s


class Solution:

	def maxWater(self, arr, n):
		left = 0
		right = n - 1
		l_max = 0
		r_max = 0
		result = 0
		while left <= right:
			if r_max <= l_max:
				result += max(0, r_max - arr[right])
				r_max = max(r_max, arr[right])
				right -= 1
			else:
				result += max(0, l_max - arr[left])
				l_max = max(l_max, arr[left])
				left += 1
		return result


class Solution:

	def maxWater(self, height, n):
		maxL = [-1 for i in range(n)]
		maxL[0] = height[0]
		for i in range(1, n):
			maxL[i] = max(maxL[i - 1], height[i])
		maxR = [-1 for i in range(n)]
		maxR[n - 1] = height[n - 1]
		for i in range(n - 2, -1, -1):
			maxR[i] = max(maxR[i + 1], height[i])
		water = [0 for i in range(n)]
		for i in range(n):
			water[i] = min(maxL[i], maxR[i]) - height[i]
		return sum(water)
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.maxWater(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def maxWater(self, arr, n):
		l = []
		m = arr[0]
		for i in arr:
			if i > m:
				m = i
			l.append(m)
		r = []
		n = arr[-1]
		for i in arr[::-1]:
			if i > n:
				n = i
			r.append(n)
		r = r[::-1]
		count = 0
		for i in range(len(arr)):
			count += min(l[i], r[i]) - arr[i]
		return count


class Solution:

	def maxWater(self, arr, n):
		left = []
		right = []
		ans = []
		left.append(arr[0])
		m = arr[0]
		for i in range(1, n):
			m = max(arr[i], m)
			left.append(m)
		right.append(arr[n - 1])
		m = arr[n - 1]
		for i in range(n - 2, -1, -1):
			m = max(arr[i], m)
			right.append(m)
		right = right[::-1]
		for i in range(0, n):
			z = min(left[i], right[i]) - arr[i]
			ans.append(z)
		return sum(ans)


class Solution:

	def maxWater(self, arr, n):
		left = []
		right = []
		for i in range(n):
			if i == 0:
				left.append(arr[i])
				m = arr[i]
			else:
				m = max(arr[i], m)
				left.append(m)
		for j in range(n - 1, -1, -1):
			if j == n - 1:
				right.append(arr[j])
				m = arr[j]
			else:
				m = max(arr[j], m)
				right.append(m)
		right = right[::-1]
		ans = []
		for i in range(n):
			ans.append(min(left[i], right[i]) - arr[i])
		return sum(ans)


from math import *

class Solution:

	def maxWater(self, arr, n):
		left = [0] * n
		right = [0] * n
		maxi = 0
		unit = 0
		left[0] = arr[0]
		for i in range(1, n):
			left[i] = max(left[i - 1], arr[i])
		right[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			right[i] = max(right[i + 1], arr[i])
		for i in range(n):
			unit += min(left[i], right[i]) - arr[i]
		return unit


class Solution:

	def maxWater(self, a, n):
		left = [0 for i in range(n)]
		right = [0 for i in range(n)]
		left[0] = a[0]
		right[n - 1] = a[n - 1]
		for i in range(1, n):
			left[i] = max(left[i - 1], a[i])
			right[n - 1 - i] = max(right[n - i], a[n - 1 - i])
		w = 0
		for i in range(n):
			w += min(left[i], right[i]) - arr[i]
		return w


class Solution:

	def maxWater(self, arr, n):
		(leftMax, rightMax) = (0, 0)
		(lo, hi) = (0, n - 1)
		ans = 0
		while hi >= lo:
			if arr[lo] < arr[hi]:
				if arr[lo] > leftMax:
					leftMax = arr[lo]
				else:
					ans = ans + (leftMax - arr[lo])
				lo += 1
			else:
				if arr[hi] > rightMax:
					rightMax = arr[hi]
				else:
					ans = ans + (rightMax - arr[hi])
				hi -= 1
		return ans


class Solution:

	def maxWater(self, arr, n):
		arrl = [0] * n
		arrr = [0] * n
		sum = 0
		arrl[0] = arr[0]
		arrr[-1] = arr[-1]
		for i in range(1, n):
			arrl[i] = max(arr[i], arrl[i - 1])
		for i in range(n - 2, -1, -1):
			arrr[i] = max(arr[i], arrr[i + 1])
		for i in range(n):
			sum = sum + min(arrr[i], arrl[i]) - arr[i]
		return sum


class Solution:

	def maxWater(self, arr, n):
		left = []
		right = []
		left.append(arr[0])
		for i in range(1, n):
			left.append(max(arr[i], left[i - 1]))
		right.append(arr[-1])
		for i in range(n - 1, -1, -1):
			right.append(max(arr[i], right[n - i - 1]))
		right.reverse()
		sum = 0
		for i in range(n):
			sum += min(right[i], left[i]) - arr[i]
		return sum


class Solution:

	def maxWater(self, arr, n):
		lmax = [0 for i in range(n)]
		rmax = [0 for i in range(n)]
		ans = 0
		lmax[0] = arr[0]
		for i in range(1, n):
			lmax[i] = max(arr[i], lmax[i - 1])
		rmax[-1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			rmax[i] = max(arr[i], rmax[i + 1])
		for i in range(1, n - 1):
			ans += min(lmax[i], rmax[i]) - arr[i]
		return ans


class Solution:

	def maxWater(self, height, n):
		if not height:
			return 0
		l = 0
		r = len(height) - 1
		res = 0
		(maxL, maxR) = (height[l], height[r])
		while l < r:
			if maxL < maxR:
				l += 1
				maxL = max(maxL, height[l])
				res += maxL - height[l]
			else:
				r -= 1
				maxR = max(maxR, height[r])
				res += maxR - height[r]
		return res


class Solution:

	def maxWater(self, arr, n):
		max_water = 0
		left_pillars = [0] * n
		right_pillars = [0] * n
		left_pillars[0] = arr[0]
		right_pillars[n - 1] = arr[n - 1]
		for i in range(1, n):
			left_pillars[i] = max(left_pillars[i - 1], arr[i])
		for i in range(n - 2, -1, -1):
			right_pillars[i] = max(right_pillars[i + 1], arr[i])
		for i in range(n):
			max_water += min(left_pillars[i], right_pillars[i]) - arr[i]
		return max_water


import sys

class Solution:

	def maxWater(self, arr, n):
		bars = arr
		n = len(bars)
		if n <= 2:
			return 0
		water = 0
		left = [None] * (n - 1)
		left[0] = -sys.maxsize
		for i in range(1, n - 1):
			left[i] = max(left[i - 1], bars[i - 1])
		right = -sys.maxsize
		for i in reversed(range(1, n - 1)):
			right = max(right, bars[i + 1])
			if min(left[i], right) > bars[i]:
				water += min(left[i], right) - bars[i]
		return water


class Solution:

	def maxWater(self, arr, n):
		left = n * [0]
		right = n * [0]
		water = 0
		left[0] = arr[0]
		max_left = arr[0]
		for i in range(0, n):
			if max_left < arr[i]:
				max_left = arr[i]
				left[i] = max_left
			else:
				left[i] = max_left
		max_right = arr[-1]
		for i in range(n - 1, -1, -1):
			if max_right < arr[i]:
				max_right = arr[i]
				right[i] = max_right
			else:
				right[i] = max_right
		for i in range(0, n):
			water += min(left[i], right[i]) - arr[i]
		return water


class Solution:

	def maxWater(self, arr, n):
		l = [arr[0]]
		r = [0] * n
		r[n - 1] = arr[n - 1]
		for i in range(1, n):
			l.append(max(l[i - 1], arr[i]))
		for i in range(n - 2, -1, -1):
			r[i] = max(r[i + 1], arr[i])
		ans = 0
		for i in range(0, n):
			ans += min(l[i], r[i]) - arr[i]
		return ans


class Solution:

	def maxWater(self, height, n):
		n = len(height)
		prefix = [0] * n
		suffix = [0] * n
		prefix[0] = height[0]
		suffix[n - 1] = height[n - 1]
		for i in range(1, n):
			prefix[i] = max(prefix[i - 1], height[i])
		for j in range(n - 2, -1, -1):
			suffix[j] = max(suffix[j + 1], height[j])
		maxi = 0
		for i in range(n):
			maxi += min(prefix[i], suffix[i]) - height[i]
		return maxi


class Solution:

	def maxWater(self, arr, n):
		left = []
		right = []
		k = 1
		lbg = arr[0]
		rbg = arr[n - k]
		for i in range(n):
			if lbg < arr[i]:
				lbg = arr[i]
			left.append(lbg)
			if rbg < arr[n - k]:
				rbg = arr[n - k]
			k += 1
			right.append(rbg)
		right.reverse()
		sm = 0
		for i in range(n):
			r = min(left[i], right[i]) - arr[i]
			sm += r
		return sm


class Solution:

	def maxWater(self, arr, n):
		lg = [arr[0]]
		rg = [arr[-1]]
		for i in range(1, n):
			lg.append(max(lg[-1], arr[i]))
		for i in range(n - 2, -1, -1):
			rg.append(max(rg[-1], arr[i]))
		rg.reverse()
		w = 0
		for i in range(1, n - 1):
			w += max(min(lg[i - 1], rg[i + 1]) - arr[i], 0)
		return w


class Solution:

	def maxWater(self, a, n):
		(l, r) = ([0] * n, [0] * n)
		l[0] = a[0]
		r[n - 1] = a[n - 1]
		for i in range(1, n):
			l[i] = max(l[i - 1], a[i])
		for i in range(n - 2, -1, -1):
			r[i] = max(r[i + 1], a[i])
		s = 0
		for i in range(1, n - 1):
			s += min(l[i], r[i]) - a[i]
		return s


class Solution:

	def maxWater(self, arr, n):
		n = len(arr)
		res = 0
		left = [0] * n
		right = [0] * n
		max_ = -1000000000
		for i in range(n):
			if arr[i] >= max_:
				left[i] = arr[i]
				max_ = arr[i]
			else:
				left[i] = max_
		max_ = -100000000000
		for i in range(n - 1, -1, -1):
			if arr[i] > max_:
				right[i] = arr[i]
				max_ = arr[i]
			else:
				right[i] = max_
		for i in range(1, n - 1):
			if left[i] > arr[i] and right[i] > arr[i]:
				if left[i] > right[i]:
					res += right[i] - arr[i]
				else:
					res += left[i] - arr[i]
		return res


class Solution:

	def maxWater(self, arr, n):
		l_markers = []
		l_top = arr[0]
		for i in range(len(arr)):
			if arr[i] > l_top:
				l_top = arr[i]
				l_markers.append(l_top)
			else:
				l_markers.append(l_top)
		r_markers = []
		r_top = arr[-1]
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] > r_top:
				r_top = arr[i]
				r_markers.append(r_top)
			else:
				r_markers.append(r_top)
		r_markers = r_markers[::-1]
		counter = 0
		for i in range(len(arr)):
			counter += min(l_markers[i], r_markers[i]) - arr[i]
		return counter


class Solution:

	def maxWater(self, arr, n):
		if n <= 2:
			return 0
		left = [0 for _ in range(n)]
		right = [0 for _ in range(n)]
		l = -1
		r = -1
		for i in range(n):
			l = max(l, arr[i])
			j = n - i - 1
			r = max(r, arr[j])
			left[i] = l
			right[j] = r
		total_water_collected = 0
		for i in range(n):
			total_water_collected += min(left[i], right[i]) - arr[i]
		return total_water_collected


class Solution:

	def maxWater(self, arr, n):
		left = [0] * n
		right = [0] * n
		l = 0
		r = 0
		for i in range(n):
			l = max(l, arr[i])
			left[i] = l
			j = n - 1 - i
			r = max(r, arr[j])
			right[j] = r
		s = 0
		for i in range(n):
			s += min(left[i], right[i]) - arr[i]
		return s


class Solution:

	def maxWater(self, arr, n):
		lmax = []
		lmax.append(arr[0])
		for i in range(1, n):
			if arr[i] >= lmax[-1]:
				lmax.append(arr[i])
			else:
				lmax.append(lmax[-1])
		rmax = []
		rmax.append(arr[n - 1])
		for j in range(n - 2, -1, -1):
			if arr[j] >= rmax[-1]:
				rmax.append(arr[j])
			else:
				rmax.append(rmax[-1])
		rmax.reverse()
		ans = 0
		for i in range(n):
			ans += min(lmax[i], rmax[i]) - arr[i]
		return ans


class Solution:

	def maxWater(self, arr, n):
		(i, j) = (0, n - 1)
		(leftmax, rightmax) = (0, 0)
		res = 0
		while i < j:
			if arr[i] <= arr[j]:
				if leftmax < arr[i]:
					leftmax = arr[i]
				else:
					res += leftmax - arr[i]
				i += 1
			else:
				if rightmax < arr[j]:
					rightmax = arr[j]
				else:
					res += rightmax - arr[j]
				j -= 1
		return res


class Solution:

	def maxWater(self, arr, n):
		left = [0 for i in range(n)]
		right = [0 for i in range(n)]
		left[0] = arr[0]
		right[n - 1] = arr[n - 1]
		for i in range(1, n):
			if arr[i] > left[i - 1]:
				left[i] = arr[i]
			else:
				left[i] = left[i - 1]
		for i in range(n - 2, -1, -1):
			if arr[i] > right[i + 1]:
				right[i] = arr[i]
			else:
				right[i] = right[i + 1]
		count = 0
		for i in range(n):
			count += min(left[i], right[i]) - arr[i]
		return count


class Solution:

	def maxWater(self, arr, n):
		res = 0
		left = right = 0
		low = 0
		high = n - 1
		while low <= high:
			if arr[low] < arr[high]:
				if arr[low] > left:
					left = arr[low]
				else:
					res += left - arr[low]
				low += 1
			else:
				if arr[high] > right:
					right = arr[high]
				else:
					res += right - arr[high]
				high -= 1
		return res


class Solution:

	def maxWater(self, arr, n):
		l = 0
		r = n - 1
		lmax = 0
		rmax = 0
		final_sum = 0
		while l <= r:
			if arr[l] <= arr[r]:
				if arr[l] >= lmax:
					lmax = arr[l]
				else:
					final_sum += lmax - arr[l]
				l += 1
			else:
				if arr[r] >= rmax:
					rmax = arr[r]
				else:
					final_sum += rmax - arr[r]
				r -= 1
		return final_sum