Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.


The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:


Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures

Amortized analysis

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

Solutions:
class Solution:

	def trap(self, height):
		if not height:
			return 0
		result = 0
		left = 0
		right = len(height) - 1
		while left < right:
			if height[left] <= height[right]:
				tmp = height[left]
				left += 1
				while left < right and height[left] <= tmp:
					result += tmp - height[left]
					left += 1
			else:
				tmp = height[right]
				right -= 1
				while left < right and height[right] <= tmp:
					result += tmp - height[right]
					right -= 1
		return result


class Solution:

	def trap(self, height):
		if not height:
			return 0
		(left, right) = (0, len(height) - 1)
		(maxLeft, maxRight) = (height[left], height[right])
		maxTrap = 0
		while left <= right:
			if height[left] <= height[right]:
				if height[left] > maxLeft:
					maxLeft = height[left]
				else:
					maxTrap += maxLeft - height[left]
				left += 1
			else:
				if height[right] > maxRight:
					maxRight = height[right]
				else:
					maxTrap += maxRight - height[right]
				right -= 1
		return maxTrap


class Solution:

	def trap(self, height):
		maxRight = 0
		maxLeft = 0
		left = 0
		right = len(height) - 1
		ret = 0
		while left < right:
			maxRight = max(maxRight, height[right])
			maxLeft = max(maxLeft, height[left])
			if maxLeft > maxRight:
				ret += maxRight - height[right]
				right -= 1
			else:
				ret += maxLeft - height[left]
				left += 1
		return ret


class Solution:

	def trap(self, height):
		l_bounds = []
		lb = float('-inf')
		for h in height:
			lb = max(lb, h)
			l_bounds.append(lb)
		water = 0
		rb = float('-inf')
		for (lb, h) in zip(reversed(l_bounds), reversed(height)):
			rb = max(rb, h)
			water += min(lb, rb) - h
		return water


class Solution:

	def trap(self, height):
		ans = 0
		(max_left, max_right) = ([0] * len(height), [0] * len(height))
		for i in range(1, len(height)):
			max_left[i] = max(max_left[i - 1], height[i - 1])
		for i in range(len(height) - 2, -1, -1):
			max_right[i] = max(max_right[i + 1], height[i + 1])
		for i in range(1, len(height) - 1):
			ans += max(min(max_left[i], max_right[i]) - height[i], 0)
		return ans


class Solution:

	def trap(self, barHeights):
		if barHeights == []:
			return 0
		numberOfBars = len(barHeights)
		leftMaxima = [0 for counter in range(numberOfBars)]
		rightMaxima = [0 for counter in range(numberOfBars)]
		leftMaxima[0] = barHeights[0]
		for counter in range(1, numberOfBars):
			leftMaxima[counter] = max(leftMaxima[counter - 1], barHeights[counter])
		rightMaxima[numberOfBars - 1] = barHeights[numberOfBars - 1]
		for counter in range(numberOfBars - 2, -1, -1):
			rightMaxima[counter] = max(rightMaxima[counter + 1], barHeights[counter])
		waterTrapped = 0
		for counter in range(0, numberOfBars):
			waterTrapped += min(leftMaxima[counter], rightMaxima[counter]) - barHeights[counter]
		return waterTrapped


class Solution:

	def trap(self, height):
		n = len(height)
		(l, r, water, minHeight) = (0, n - 1, 0, 0)
		while l < r:
			while l < r and height[l] <= minHeight:
				water += minHeight - height[l]
				l += 1
			while r > l and height[r] <= minHeight:
				water += minHeight - height[r]
				r -= 1
			minHeight = min(height[l], height[r])
		return water


class Solution:

	def trap(self, height):
		(left, right) = (0, len(height) - 1)
		result = 0
		while left < right:
			mh = min(height[left], height[right])
			if height[left] < height[right]:
				left = left + 1
				while height[left] <= mh and left < right:
					result = result + mh - height[left]
					left = left + 1
			else:
				right = right - 1
				while height[right] <= mh and left < right:
					result = result + mh - height[right]
					right = right - 1
		return result


class Solution:

	def trap(self, height):
		leftmaxes = []
		rightmaxes = []
		maximum = 0
		for i in range(len(height)):
			maximum = max(maximum, height[i])
			leftmaxes.append(maximum)
		maximum = 0
		for i in range(len(height)):
			maximum = max(maximum, height[len(height) - i - 1])
			rightmaxes.append(maximum)
		water = 0
		print(leftmaxes)
		print(rightmaxes)
		for i in range(len(height)):
			trappable = min(leftmaxes[i], rightmaxes[-i - 1])
			if trappable > height[i]:
				water += trappable - height[i]
		return water


class Solution:

	def trap(self, height):
		length = len(height)
		if length == 0:
			return 0
		maxLeft = [0] * length
		maxRight = [0] * length
		result = 0
		maxLeft[0] = height[0]
		maxRight[length - 1] = height[length - 1]
		for i in range(1, length):
			maxLeft[i] = max(maxLeft[i - 1], height[i])
		for i in reversed(list(range(0, length - 1))):
			maxRight[i] = max(maxRight[i + 1], height[i])
		for i in range(length):
			result += min(maxLeft[i], maxRight[i]) - height[i]
		return result


class Solution:

	def trap(self, height):
		N = len(height)
		valleys = []
		i = 0
		while i < N - 1:
			while i < N - 1 and height[i] <= height[i + 1]:
				i += 1
			while i < N - 1 and height[i] > height[i + 1]:
				i += 1
			j = i
			while j < N - 1 and height[j] == height[j + 1]:
				j += 1
			if j < N - 1 and height[j] < height[j + 1]:
				valleys.append([i - 1, j + 1])
			i = j
		total_water = 0
		further_valleys = []
		k = 0
		if valleys:
			l = valleys[k][0]
			r = valleys[k][1]
			old_level = height[l + 1]
		while k < len(valleys):
			water = 0
			while l >= 0 and r < N and (height[l] >= height[l + 1]) and (height[r - 1] <= height[r]):
				new_level = min(height[l], height[r])
				water += (new_level - old_level) * (r - l - 1)
				old_level = new_level
				if l >= 0 and r < N:
					if height[l] == height[r]:
						l -= 1
						r += 1
					elif height[l] < height[r]:
						l -= 1
					else:
						r += 1
					while l >= 0 and height[l] == height[l + 1]:
						l -= 1
					while r < N and height[r - 1] == height[r]:
						r += 1
			total_water += water
			if l >= 0 and r < N:
				if height[l] > height[l + 1]:
					further_valleys.append([l, r])
				elif further_valleys and height[further_valleys[-1][1] - 1] == height[l + 1]:
					old_level = height[l + 1]
					l = further_valleys[-1][0]
					further_valleys.pop()
					continue
			k += 1
			if k < len(valleys):
				l = valleys[k][0]
				r = valleys[k][1]
				old_level = height[l + 1]
		return total_water


class Solution:

	def get_empty_per_level(self, height, level):
		print(('Level: ', level))
		block_start = 0
		n = len(height)
		while block_start < n and height[block_start] < level:
			block_start += 1
		if block_start == n:
			print('No start')
			return n
		block_end = n - 1
		while block_end > block_start and height[block_end] < level:
			block_end -= 1
		if block_end == block_start:
			print('No end')
			return n - 1
		print('Some value')
		return n - (block_end - block_start + 1)

	def trap(self, height):
		if not height or len(height) == 0:
			return 0
		levels = set(height)
		levels = list(levels)
		if 0 in levels:
			levels.remove(0)
		levels.sort()
		if len(levels) == 0:
			return 0
		max_level = max(height)
		total_count = sum([max_level - item for item in height])
		prev_level = levels.pop(0)
		missing_water_per_level = self.get_empty_per_level(height, prev_level)
		total_count -= prev_level * missing_water_per_level
		for level in levels:
			missing_water_per_level = self.get_empty_per_level(height, level)
			multi_level_count = (level - prev_level) * missing_water_per_level
			total_count -= multi_level_count
			prev_level = level
		return total_count