Given an array arr[] of N non-negative integers representing the height of blocks. If width of each block is 1, compute how much water can be trapped between the blocks during the rainy season. 
 
Example 1:
Input:
N = 6
arr[] = {3,0,0,2,0,4}
Output:
10
Explanation: 
Example 2:
Input:
N = 4
arr[] = {7,4,0,9}
Output:
10
Explanation:
Water trapped by above 
block of height 4 is 3 units and above 
block of height 0 is 7 units. So, the 
total unit of water trapped is 10 units.
Example 3:
Input:
N = 3
arr[] = {6,9,9}
Output:
0
Explanation:
No water will be trapped.
Your Task:
You don't need to read input or print anything. The task is to complete the function trappingWater() which takes arr[] and N as input parameters and returns the total amount of water that can be trapped.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
3 < N < 10^{6}
0 < A_{i} < 10^{8}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: 
class Solution:
    def trappingWater(self, arr,n):
        #Code here

Solutions:
class Solution:

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


class Solution:

	def trappingWater(self, arr, n):
		left = 0
		right = n - 1
		left_max = 0
		right_max = 0
		water_trapped = 0
		while left <= right:
			if arr[left] <= arr[right]:
				left_max = max(left_max, arr[left])
				water_trapped += max(0, left_max - arr[left])
				left += 1
			else:
				right_max = max(right_max, arr[right])
				water_trapped += max(0, right_max - arr[right])
				right -= 1
		return water_trapped


class Solution:

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


class Solution:

	def trappingWater(self, arr, n):
		left_max = 0
		right_max = 0
		l = 0
		r = n - 1
		water = 0
		while l < r:
			if arr[l] <= arr[r]:
				if left_max >= arr[l]:
					water += left_max - arr[l]
				else:
					left_max = arr[l]
				l += 1
			else:
				if right_max >= arr[r]:
					water += right_max - arr[r]
				else:
					right_max = arr[r]
				r -= 1
		return water


class Solution:

	def trappingWater(self, arr, n):
		prefix_max = [0] * n
		suffix_max = [0] * n
		for i in range(1, n):
			if arr[i - 1] > prefix_max[i - 1]:
				prefix_max[i] = arr[i - 1]
			else:
				prefix_max[i] = prefix_max[i - 1]
		for i in range(n - 2, -1, -1):
			if arr[i + 1] > suffix_max[i + 1]:
				suffix_max[i] = arr[i + 1]
			else:
				suffix_max[i] = suffix_max[i + 1]
		water = 0
		for i in range(n):
			if arr[i] < suffix_max[i] and arr[i] < prefix_max[i]:
				water = water + min(suffix_max[i], prefix_max[i]) - arr[i]
		return water


class Solution:

	def trappingWater(self, arr, n):
		if n <= 2:
			return 0
		left_max = [0] * n
		right_max = [0] * n
		left_max[0] = arr[0]
		for i in range(1, n):
			left_max[i] = max(left_max[i - 1], arr[i])
		right_max[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			right_max[i] = max(right_max[i + 1], arr[i])
		water = 0
		for i in range(n):
			water += min(left_max[i], right_max[i]) - arr[i]
		return water


class Solution:

	def trappingWater(self, arr, n):
		lmax = []
		rmax = []
		maxi = arr[0]
		for i in range(n):
			maxi = max(maxi, arr[i])
			lmax.append(maxi)
		maxi = arr[-1]
		for i in range(n - 1, -1, -1):
			maxi = max(maxi, arr[i])
			rmax.append(maxi)
		rmax = rmax[::-1]
		water = 0
		for i in range(n):
			mini = min(lmax[i], rmax[i])
			if mini - arr[i] > 0:
				water += mini - arr[i]
		return water


class Solution:

	def trappingWater(self, arr, n):
		left = self.leftmax(arr)
		right = self.rightmax(arr)
		ans = 0
		for i in range(1, n - 1):
			ans += min(left[i], right[i]) - arr[i]
		if ans < 0:
			return 0
		return ans

	def leftmax(self, arr):
		n = len(arr)
		big = arr[0]
		ans = [0] * n
		ans[0] = big
		for i in range(1, n):
			ans[i] = max(arr[i], ans[i - 1])
		return ans

	def rightmax(self, arr):
		n = len(arr)
		big = arr[-1]
		ans = [0] * n
		ans[-1] = big
		for i in range(n - 2, -1, -1):
			ans[i] = max(arr[i], ans[i + 1])
		return ans


class Solution:

	def trappingWater(self, arr, n):
		right_max = [0] * n
		right_max[0] = arr[0]
		left_max = [0] * n
		left_max[n - 1] = arr[n - 1]
		for i in range(1, n):
			right_max[i] = max(right_max[i - 1], arr[i])
		for i in reversed(range(n - 1)):
			left_max[i] = max(left_max[i + 1], arr[i])
		res = 0
		for i in range(n):
			res += min(left_max[i], right_max[i]) - arr[i]
		return res


class Solution:

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


class Solution:

	def trappingWater(self, arr, n):
		leftlimit = arr[0]
		rightlimit = arr[-1]
		maximum = max(arr)
		for i in range(n):
			if arr[i] == maximum:
				max_index = i
		units = 0
		if rightlimit == maximum:
			for i in range(1, n - 1):
				if leftlimit >= arr[i]:
					units += leftlimit - arr[i]
				else:
					leftlimit = arr[i]
		elif leftlimit == maximum:
			for i in range(n - 2, 0, -1):
				if rightlimit >= arr[i]:
					units += rightlimit - arr[i]
				else:
					rightlimit = arr[i]
		else:
			rightlimit = arr[max_index]
			for i in range(1, max_index):
				if leftlimit >= arr[i]:
					units += leftlimit - arr[i]
				else:
					leftlimit = arr[i]
			leftlimit = arr[max_index]
			rightlimit = arr[-1]
			for i in range(n - 2, max_index, -1):
				if rightlimit >= arr[i]:
					units += rightlimit - arr[i]
				else:
					rightlimit = arr[i]
		return units


class Solution:

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


class Solution:

	def trappingWater(self, arr, n):
		min_height = []
		max_so_far = 0
		for i in range(n):
			max_so_far = max(max_so_far, arr[i])
			min_height.append(max_so_far)
		max_so_far = 0
		for j in range(n - 1, -1, -1):
			max_so_far = max(max_so_far, arr[j])
			min_height[j] = min(max_so_far, min_height[j])
		water_trapped = 0
		for i in range(n):
			water_trapped += abs(min_height[i] - arr[i])
		return water_trapped


class Solution:

	def trappingWater(self, arr, n):
		(left, right) = (0, n - 1)
		(lmax, rmax) = (arr[0], arr[n - 1])
		water = 0
		while left < right:
			lmax = max(lmax, arr[left])
			rmax = max(rmax, arr[right])
			if lmax > rmax:
				water = water + rmax - arr[right]
				right = right - 1
			else:
				water = water + lmax - arr[left]
				left = left + 1
		return water


class Solution:

	def trappingWater(self, arr, n):
		if len(arr) < 3:
			return 0
		left = 0
		right = len(arr) - 1
		left_max = right_max = total_water = 0
		while left < right:
			if arr[left] <= arr[right]:
				if arr[left] >= left_max:
					left_max = arr[left]
				else:
					total_water += left_max - arr[left]
				left += 1
			else:
				if arr[right] >= right_max:
					right_max = arr[right]
				else:
					total_water += right_max - arr[right]
				right -= 1
		return total_water


class Solution:

	def trappingWater(self, A, n):
		n = len(A)
		left = [0] * n
		right = [0] * n
		sum = 0
		left[0] = A[0]
		for i in range(1, len(A)):
			left[i] = max(left[i - 1], A[i])
		right[n - 1] = A[n - 1]
		for i in range(n - 2, -1, -1):
			right[i] = max(right[i + 1], A[i])
		for i in range(len(A)):
			sum = sum + min(left[i], right[i]) - A[i]
		return sum


class Solution:

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


class Solution:

	def trappingWater(self, arr, n):
		a = [arr[0]]
		for i in range(1, n):
			a.append(max(arr[i], a[i - 1]))
		b = arr[n - 1]
		s = max(0, min(a[n - 1], b) - arr[n - 1])
		for i in range(n - 2, -1, -1):
			b = max(b, arr[i])
			s += max(0, min(a[i], b) - arr[i])
		return s


class Solution:

	def findWater(self, arr, n):
		left = [0] * n
		right = [0] * n
		water = 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(0, n):
			water += min(left[i], right[i]) - arr[i]
		return water

	def trappingWater(self, arr, n):
		return self.findWater(arr, n)


class Solution:

	def trappingWater(self, arr, n):
		maxi = 0
		output = 0
		stack = []
		for item in arr:
			count = 1
			while stack and item > stack[-1][0]:
				(height, num) = stack.pop()
				output += (min(maxi, item) - height) * num
				count += num
			if item < maxi:
				stack.append((item, count))
			else:
				maxi = item
		return output


class Solution:

	def trappingWater(self, arr, n):
		rain_trap = 0
		A = arr
		n = len(A)
		left_max_prefix = [0] * n
		left_max_prefix[0] = A[0]
		right_max_suffix = [0] * n
		right_max_suffix[-1] = A[n - 1]
		for i in range(1, len(A)):
			if A[i] > left_max_prefix[i - 1]:
				left_max_prefix[i] = A[i]
			else:
				left_max_prefix[i] = left_max_prefix[i - 1]
		for i in range(n - 2, -1, -1):
			if A[i] > right_max_suffix[i + 1]:
				right_max_suffix[i] = A[i]
			else:
				right_max_suffix[i] = right_max_suffix[i + 1]
		for i in range(n):
			rain_trap += min(left_max_prefix[i], right_max_suffix[i]) - A[i]
		return rain_trap


class Solution:

	def trappingWater(self, arr, n):
		i = 1
		left_max = [arr[i - 1]] * n
		while i < n:
			if left_max[i - 1] < arr[i]:
				left_max[i] = arr[i]
			else:
				left_max[i] = left_max[i - 1]
			i += 1
		i = n - 1
		right_max = [arr[i]] * n
		while i > 0:
			if right_max[i] < arr[i - 1]:
				right_max[i - 1] = arr[i - 1]
			else:
				right_max[i - 1] = right_max[i]
			i -= 1
		res = 0
		i = 1
		while i < n - 1:
			res += min(left_max[i], right_max[i]) - arr[i]
			i += 1
		return res


class Solution:

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


class Solution:

	def trappingWater(self, arr, n):
		max_from_left = [arr[0]] * n
		max_from_right = [arr[n - 1]] * n
		for i in range(1, n):
			max_from_left[i] = max(max_from_left[i - 1], arr[i])
		for i in range(n - 2, -1, -1):
			max_from_right[i] = max(max_from_right[i + 1], arr[i])
		rain = [min(max_from_left[i], max_from_right[i]) - arr[i] for i in range(n)]
		return sum(rain)


class Solution:

	def trappingWater(self, arr, n):
		cap = 0
		lft = [0] * n
		rgt = [0] * n
		lftmax = 0
		rgtmax = 0
		for i in range(0, n):
			lftmax = max(lftmax, arr[i])
			lft[i] = lftmax
		for i in range(n - 1, -1, -1):
			rgtmax = max(rgtmax, arr[i])
			rgt[i] = rgtmax
		for i in range(0, n, 1):
			cap = cap + min(lft[i], rgt[i]) - arr[i]
		return cap


class Solution:

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


class Solution:

	def trappingWater(self, arr, n):
		if n <= 2:
			return 0
		i = 1
		j = n - 1
		lmax = arr[0]
		rmax = arr[n - 1]
		ans = 0
		while i <= j:
			if arr[i] > lmax:
				lmax = arr[i]
			if arr[j] > rmax:
				rmax = arr[j]
			if lmax <= rmax:
				ans += lmax - arr[i]
				i = i + 1
			else:
				ans += rmax - arr[j]
				j = j - 1
		return ans


class Solution:

	def trappingWater(self, arr, n):
		prefix_max = [0] * n
		suffix_max = [0] * n
		prefix_max[0] = arr[0]
		for i in range(1, n):
			prefix_max[i] = max(prefix_max[i - 1], arr[i])
		suffix_max[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			suffix_max[i] = max(suffix_max[i + 1], arr[i])
		trapped_water = 0
		for i in range(n):
			trapped_water += min(prefix_max[i], suffix_max[i]) - arr[i]
		return trapped_water


class Solution:

	def trappingWater(self, arr, n):
		left = [0] * n
		right = [n - 1] * n
		for i in range(1, n):
			j = left[i - 1]
			if arr[i] > arr[j]:
				left[i] = i
			else:
				left[i] = j
		for i in range(n - 2, -1, -1):
			j = right[i + 1]
			if arr[i] > arr[j]:
				right[i] = i
			else:
				right[i] = j
		trapped = 0
		for i in range(n):
			(j, k) = (left[i], right[i])
			h = min(arr[j], arr[k])
			trapped += h - arr[i]
		return trapped


class Solution:

	def trappingWater(self, arr, n):
		(left, right) = (0, n - 1)
		(maxL, maxR) = (0, 0)
		result = 0
		while left <= right:
			if arr[left] <= maxR:
				if arr[left] >= maxL:
					maxL = arr[left]
				else:
					result += maxL - arr[left]
				left += 1
			else:
				if arr[right] >= maxR:
					maxR = arr[right]
				else:
					result += maxR - arr[right]
				right += -1
		return result


class Solution:

	def trappingWater(self, array, n):
		stack = list()
		result = 0
		for i in range(n):
			while stack and array[stack[-1]] < array[i]:
				pop_height = array[stack[-1]]
				stack.pop()
				if not stack:
					break
				distance = i - stack[-1] - 1
				min_height = min(array[stack[-1]], array[i]) - pop_height
				result += distance * min_height
			stack.append(i)
		return result


class Solution:

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


class Solution:

	def trappingWater(self, arr, n):
		if not arr:
			return 0
		(l, r) = (0, n - 1)
		(leftmax, rightmax) = (arr[l], arr[r])
		res = 0
		while l < r:
			if leftmax < rightmax:
				l += 1
				leftmax = max(leftmax, arr[l])
				res += leftmax - arr[l]
			else:
				r -= 1
				rightmax = max(rightmax, arr[r])
				res += rightmax - arr[r]
		return res


class Solution:

	def trappingWater(self, arr, n):
		gn = arr[0]
		l = []
		for i in range(n):
			if arr[i] > gn:
				gn = arr[i]
			l.append(gn)
		r = [0] * n
		gn = arr[n - 1]
		for i in range(n - 1, -1, -1):
			if arr[i] > gn:
				gn = arr[i]
			r[i] = gn
		t = 0
		for i in range(n):
			t += min(l[i], r[i]) - arr[i]
		return t


class Solution:

	def trappingWater(self, arr, n):
		lef = arr[0]
		rig = arr[n - 1]
		l = 0
		r = n - 1
		r1 = 0
		while l < r:
			if lef < rig:
				l = l + 1
				lef = max(lef, arr[l])
				if lef - arr[l] >= 1:
					r1 += lef - arr[l]
			else:
				r = r - 1
				rig = max(rig, arr[r])
				if rig - arr[r] >= 0:
					r1 += rig - arr[r]
		return r1


class Solution:

	def trappingWater(self, ar, n):
		Lpillar = [None] * n
		Rpillar = [None] * n
		Lpillar[0] = ar[0]
		Rpillar[n - 1] = ar[n - 1]
		for i in range(1, len(ar)):
			Lpillar[i] = max(Lpillar[i - 1], ar[i])
		for i in reversed(range(0, len(ar) - 1)):
			Rpillar[i] = max(Rpillar[i + 1], ar[i])
		Water = 0
		for i in range(len(ar)):
			Water += min(Lpillar[i], Rpillar[i]) - ar[i]
		return Water


class Solution:

	def trappingWater(self, arr, n):
		left = []
		right = []
		left_max = -1
		right_max = -1
		ans = 0
		for i in range(n):
			if arr[i] > left_max:
				left_max = arr[i]
			if arr[n - 1 - i] > right_max:
				right_max = arr[n - 1 - i]
			left.append(left_max)
			right.append(right_max)
		for i in range(n):
			ans += min(left[i], right[n - 1 - i]) - arr[i]
		return ans


class Solution:

	def trappingWater(self, arr, n):
		result = 0
		lmax = min(arr)
		rmax = max(arr)
		for i in range(1, n - 1):
			if lmax < arr[i - 1]:
				lmax = arr[i - 1]
			if rmax == arr[i - 1]:
				rmax = max(arr[i + 1:n])
			if arr[i] < lmax:
				if arr[i] < rmax:
					result += (rmax, lmax)[lmax < rmax] - arr[i]
		return result


class Solution:

	def trappingWater(self, arr, n):
		right_max_list = [-1] * n
		left_max_list = [-1] * n
		for i in range(1, n):
			max_till_previous = max(left_max_list[i - 1], arr[i - 1])
			if max_till_previous > arr[i]:
				left_max_list[i] = max_till_previous
		for i in range(n - 2, -1, -1):
			max_till_previous = max(right_max_list[i + 1], arr[i + 1])
			if max_till_previous > arr[i]:
				right_max_list[i] = max_till_previous
		water = 0
		for i in range(n):
			minimum_of_left_and_right = min(left_max_list[i], right_max_list[i])
			if minimum_of_left_and_right != -1:
				water += minimum_of_left_and_right - arr[i]
		return water


class Solution:

	def trappingWater(self, arr, n):
		left = 0
		right = n - 1
		leftmax = 0
		rightmax = 0
		res = 0
		while left < right:
			if arr[left] < arr[right]:
				if leftmax < arr[left]:
					leftmax = arr[left]
				else:
					res = res + (leftmax - arr[left])
				left += 1
			else:
				if rightmax < arr[right]:
					rightmax = arr[right]
				else:
					res = res + (rightmax - arr[right])
				right -= 1
		return res


class Solution:

	def trappingWater(self, arr, n):
		prefix = [0 for i in range(n)]
		suffix = [0 for i in range(n)]
		prefix[0] = arr[0]
		suffix[n - 1] = arr[n - 1]
		amount = 0
		for i in range(1, n):
			prefix[i] = max(prefix[i - 1], arr[i])
		for i in range(n - 2, -1, -1):
			suffix[i] = max(suffix[i + 1], arr[i])
		for i in range(n):
			amount = amount + (min(suffix[i], prefix[i]) - arr[i])
		return amount


class Solution:

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


class Solution:

	def trappingWater(self, arr, n):
		if n == 0:
			return 0
		left_max = [arr[0]]
		right_max = [0] * n
		right_max[n - 1] = arr[n - 1]
		for i in range(1, n):
			left_max.append(max(arr[i], left_max[i - 1]))
		for i in range(n - 2, -1, -1):
			right_max[i] = max(right_max[i + 1], arr[i])
		water_ = 0
		for i in range(n - 1):
			v1 = min(left_max[i], right_max[i])
			water_ += v1 - arr[i] if v1 - arr[i] >= 0 else 0
		return water_


class Solution:

	def trappingWater(self, arr, n):
		left = 0
		right = n - 1
		leftMax = 0
		rightMax = 0
		res = 0
		while left <= right:
			if arr[left] <= arr[right]:
				if leftMax <= arr[left]:
					leftMax = arr[left]
				else:
					res += leftMax - arr[left]
				left += 1
			else:
				if rightMax <= arr[right]:
					rightMax = arr[right]
				else:
					res += rightMax - arr[right]
				right -= 1
		return res


import numpy as np

class Solution:

	def trappingWater(self, arr, n):
		a = np.array(arr)
		pos = a.argmax()
		got = False
		suma = 0
		niv = 0
		for i in range(pos if pos != len(arr) else pos - 1):
			if got == True and arr[i] >= niv:
				got = False
				niv = arr[i]
			if got == False and arr[i] > arr[i + 1]:
				got = True
				niv = arr[i]
			if got == True and arr[i] < niv:
				suma += niv - arr[i]
		arr1 = arr[pos:]
		arr1.reverse()
		niv = 0
		got = False
		for i in range(len(arr1) - 1 if len(arr1) > 1 else 0):
			if got == True and arr1[i] >= niv:
				got = False
				niv = arr1[i]
			if got == False and arr1[i] > arr1[i + 1]:
				got = True
				niv = arr1[i]
			if got == True and arr1[i] < niv:
				suma += niv - arr1[i]
		return suma
		return suma


class Solution:

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


class Solution:

	def trappingWater(self, arr, n):
		trap = 0
		maxi = -1
		arr1 = []
		arr2 = []
		for i in range(len(arr)):
			if arr[i] > maxi:
				maxi = arr[i]
			arr1.append(maxi)
		maxi = -1
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] > maxi:
				maxi = arr[i]
			arr2.append(maxi)
		arr2 = arr2[::-1]
		for i in range(len(arr)):
			if arr1[i] < arr2[i]:
				if arr1[i] - arr[i] > 0:
					trap = trap + arr1[i] - arr[i]
			elif arr1[i] > arr2[i]:
				if arr2[i] - arr[i] > 0:
					trap = trap + (arr2[i] - arr[i])
			else:
				temp = arr1[i]
				if temp > arr[i]:
					trap = trap + (temp - arr[i])
		return trap


class Solution:

	def trappingWater(self, arr, n):
		lefty = 0
		righty = 0
		s = 0
		e = n - 1
		ans = 0
		while s <= e:
			if arr[s] < arr[e]:
				if arr[s] > lefty:
					lefty = arr[s]
				else:
					ans += lefty - arr[s]
				s += 1
			else:
				if arr[e] > righty:
					righty = arr[e]
				else:
					ans += righty - arr[e]
				e -= 1
		return ans


class Solution:

	def trappingWater(self, arr, n):
		arr1 = [0] * n
		arr2 = [0] * n
		(mxL, mxR) = (arr[0], arr[-1])
		for i in range(n):
			if arr[i] > mxL:
				mxL = arr[i]
			arr1[i] = mxL
		for i in range(n - 1, -1, -1):
			if arr[i] > mxR:
				mxR = arr[i]
			arr2[i] = mxR
		ans = 0
		for i in range(n):
			ans += min(arr1[i], arr2[i]) - arr[i]
		return ans


class Solution:

	def trappingWater(self, arr, n):
		if n < 3:
			return 0
		count = 0
		l_max = arr[0]
		r_max = arr[n - 1]
		l = 1
		r = n - 2
		while l <= r:
			if l_max < r_max:
				if arr[l] < l_max:
					count += l_max - arr[l]
				else:
					l_max = arr[l]
				l += 1
			else:
				if arr[r] < r_max:
					count += r_max - arr[r]
				else:
					r_max = arr[r]
				r -= 1
		return count


class Solution:

	def trappingWater(self, arr, n):
		water = 0
		leftmax = [0] * n
		rightmax = [0] * n
		tempmax = 0
		if n < 2:
			return 0
		for i in range(n):
			leftmax[i] = tempmax
			if arr[i] > tempmax:
				tempmax = arr[i]
		tempmax = 0
		for i in range(n):
			rightmax[n - i - 1] = tempmax
			if arr[n - i - 1] > tempmax:
				tempmax = arr[n - i - 1]
		for i in range(n):
			temp = min(rightmax[i], leftmax[i]) - arr[i]
			if temp > 0:
				water += temp
		return water


class Solution:

	def trappingWater(self, arr, n):
		nex = [-1] * n
		prev = [-1] * n
		s = arr[n - 1]
		for i in range(n - 2, -1, -1):
			if arr[i] >= s:
				s = arr[i]
				nex[i] = -1
			else:
				nex[i] = s
		s = arr[0]
		for i in range(1, n):
			if arr[i] >= s:
				s = arr[i]
				prev[i] = -1
			else:
				prev[i] = s
		ans = 0
		for i in range(1, n - 1):
			if nex[i] == -1 or prev[i] == -1:
				continue
			ans += min(nex[i], prev[i]) - arr[i]
		return ans


class Solution:

	def trappingWater(self, arr, n):
		max = arr[0]
		steps = 0
		max_index = 0
		for i in range(1, n):
			if arr[i] >= max:
				for j in range(max_index, i):
					steps += max - arr[j]
				max = arr[i]
				max_index = i
		new_Max = arr[n - 1]
		new_Max_index = n - 1
		for i in range(n - 1, max_index, -1):
			if arr[i - 1] >= new_Max:
				for j in range(new_Max_index, i - 1, -1):
					if new_Max - arr[j] >= 0:
						steps += new_Max - arr[j]
					else:
						continue
				new_Max = arr[i - 1]
				new_Max_index = i - 1
		return steps


class Solution:

	def trappingWater(self, arr, n):
		if n < 3:
			return 0
		lefts = [arr[0]]
		for i in range(1, n):
			lefts.append(max(lefts[-1], arr[i]))
		rights = [arr[n - 1]]
		for j in range(n - 2, -1, -1):
			rights.append(max(rights[-1], arr[j]))
		rights.reverse()
		water = 0
		for i in range(n):
			water += max(0, min(lefts[i], rights[i]) - arr[i])
		return water


class Solution:

	def trappingWater(self, arr, n):
		stack = []
		res = 0
		for i in range(len(arr)):
			while stack and arr[i] > arr[stack[-1]]:
				pop = stack.pop()
				if stack:
					left = arr[stack[-1]]
					right = arr[i]
					res += (min(right, left) - arr[pop]) * (i - stack[-1] - 1)
			stack.append(i)
		return res


class Solution:

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


class Solution:

	def trappingWater(self, arr, n):
		left = [0] * n
		right = [0] * n
		max_height = 0
		for i in range(n):
			left[i] = max_height
			max_height = max(max_height, arr[i])
		max_height = 0
		for i in range(n - 1, -1, -1):
			right[i] = max_height
			max_height = max(max_height, arr[i])
		res = 0
		for i in range(n):
			trapped_water = min(left[i], right[i]) - arr[i]
			if trapped_water > 0:
				res += trapped_water
		return res


class Solution:

	def trappingWater(self, arr, n):
		leftside = arr[0]
		rightside = arr[n - 1]
		left = 0
		right = n - 1
		s = 0
		while left <= right:
			if leftside < rightside:
				if arr[left] > leftside:
					leftside = arr[left]
				else:
					s += leftside - arr[left]
				left += 1
			else:
				if arr[right] > rightside:
					rightside = arr[right]
				else:
					s += rightside - arr[right]
				right -= 1
		return s


class Solution:

	def trappingWater(self, arr, n):
		if n == 0:
			return 0
		res = 0
		right = 0
		left = n - 1
		maxr = arr[right]
		maxl = arr[left]
		result = 0
		while right <= left:
			if maxr <= maxl:
				if arr[right] >= maxr:
					maxr = arr[right]
				else:
					result += maxr - arr[right]
				right += 1
			else:
				if arr[left] >= maxl:
					maxl = arr[left]
				else:
					result += maxl - arr[left]
				left -= 1
		return result


class Solution:

	def trappingWater(self, arr, n):
		lwall = 0
		rwall = n - 1
		vol = 0
		peak = arr[0]
		peak_i = 0
		for i in range(n):
			if arr[i] > peak:
				peak = arr[i]
				peak_i = i
		cur_vol = 0
		exclude_vol = 0
		for i in range(1, peak_i + 1):
			if arr[i] >= arr[lwall]:
				vol = vol + cur_vol - exclude_vol
				lwall = i
				cur_vol = 0
				exclude_vol = 0
			else:
				cur_vol = cur_vol + arr[lwall]
				exclude_vol = exclude_vol + arr[i]
		cur_vol = 0
		exclude_vol = 0
		for j in range(1, n - peak_i + 1):
			i = n - j
			if arr[i] >= arr[rwall]:
				vol = vol + cur_vol - exclude_vol
				rwall = i
				cur_vol = 0
				exclude_vol = 0
			else:
				cur_vol = cur_vol + arr[rwall]
				exclude_vol = exclude_vol + arr[i]
		return vol


class Solution:

	def trappingWater(self, arr, n):
		lge = [-1] * n
		rge = [-1] * n
		stackl = [-1]
		stackr = [-1]
		for i in range(n - 1, -1, -1):
			num = arr[i]
			while stackr:
				if num > stackr[-1]:
					stackr.pop()
				else:
					rge[i] = stackr[-1]
					break
			if len(stackr) == 0:
				rge[i] = num
				stackr.append(num)
		for i in range(0, n):
			num = arr[i]
			while stackl:
				if num >= stackl[-1]:
					stackl.pop()
				else:
					lge[i] = stackl[-1]
					break
			if len(stackl) == 0:
				lge[i] = num
				stackl.append(num)
		water = 0
		for i in range(0, n):
			left = lge[i]
			right = rge[i]
			min_height = min(left, right)
			water += min_height - arr[i]
		return water


class Solution:

	def trappingWater(self, arr, n):
		start = 0
		end = 0
		max_pill = arr[0]
		trapQ = 0
		for i in range(0, n - 1, 1):
			j = i + 1
			if i == end:
				start = i
				max_pill = 0
				while j < n:
					if max_pill <= arr[j]:
						max_pill = arr[j]
						end = j
					j += 1
			if arr[start] < arr[i]:
				start = i
			curr_pos = 0 if min(arr[start], arr[end]) <= arr[i] else min(arr[start], arr[end]) - arr[i]
			trapQ = trapQ + curr_pos
		return trapQ


class Solution:

	def trappingWater(self, arr, n):
		lmax = arr[0]
		rmax = arr[n - 1]
		l = []
		r = []
		for i in range(1, n - 1):
			l.append(lmax)
			if lmax < arr[i]:
				lmax = arr[i]
		for j in range(n - 2, 0, -1):
			r.append(rmax)
			if rmax < arr[j]:
				rmax = arr[j]
		r.reverse()
		res = []
		for i in range(0, n - 2):
			if l[i] > r[i]:
				if r[i] - arr[i + 1] > 0:
					res.append(r[i] - arr[i + 1])
			elif l[i] - arr[i + 1] > 0:
				res.append(l[i] - arr[i + 1])
		return sum(res)


class Solution:

	def trappingWater(self, arr, n):
		leftm = [0] * n
		leftm[0] = arr[0]
		rightm = [0] * n
		rightm[n - 1] = arr[n - 1]
		for i in range(1, n):
			leftm[i] = max(leftm[i - 1], arr[i])
		for i in range(n - 2, -1, -1):
			rightm[i] = max(rightm[i + 1], arr[i])
		maxW = 0
		for i in range(n):
			maxW += max(0, min(leftm[i], rightm[i]) - arr[i])
		return maxW