//examples
// x marks the troughs' boundaries
x
x ##
## ##
## ##
## ##
x## ### x
### ### # x
########_###
x
x ##
## ###
## ###
## ###
x## # ### x
### # ### # x
###########_###
x
x #
x # #
x # # #
#_#_#_#
x
# x
# #
# # #
#_#_#_#
x
# x
# # x
# # # x
#_#_#_#

Find the boundaries of troughs. Trough has a decreasing slope followed by an increasing slope. For increasing slope, stop when the increasing slope ends or till value is greater than value at start while recording the highest so far (ex: W trough).

// time: O(n) typically but O(n^2) for last example, space: O(1)
(a):
volume = 0
i = 0
while true:
if i+1 == a.length:
break
// trough boundaries
start = i
// decreasing slope
while i+1 < a.length && a[i] >= a[i+1]:
i++
end = i
// increasing slope
while i+1 < a.length && (a[i] <= a[i+1] || a[end] <= a[start]):
i++
if a[i] >= a[end]:
end = i
// trough volume
level = min(a[start], a[end])
for j = start, j <= end, j++:
if a[j] < level:
volume += level - a[j]
i = end
return volume

Get the max before and after for every i. Water level is min of the two maxs and volume is less a[i] of that.

// time: O(n), space: O(n)
(a):
// max for i before itself
maxbefore = new [a.length]
max = 0
for i = 0, i < a.length, i++:
max = max(max, a[i])
maxbefore[i] = max
// max for i after itself
maxafter = new [a.length]
max = 0
for i = a.length-1, i >= 0, i--:
max = max(max, a[i])
maxafter[i] = max
// volume
volume = 0
for i = 0, i < a.length, i++:
level = min(maxbefore[i], maxafter[i])
volume += level - a[i]
return volume

For histograms with gap between two bars, the volume between two bars is min of water levels at them.

//example
# #
# # #
# # #
# # #
# # # #
# # # # #
#_#_#_#_#_#_#

// time: O(n), space: O(n)
(a):
// max for i before itself
maxbefore = new [a.length]
max = 0
for i = 0, i < a.length, i++:
max = max(max, a[i])
maxbefore[i] = max
// max for i after itself
maxafter = new [a.length]
max = 0
for i = a.length-1, i >= 0, i--:
max = max(max, a[i])
maxafter[i] = max
// volume
levelprev = 0
for i = 0, i < a.length, i++:
level = min(maxbefore[i], maxafter[i])
volume += level - a[i]
levelbetween = min(level, levelprev)
volume += levelbetween
levelprev = level
return volume

[Hat tip to N]

## No comments:

## Post a Comment