# Ruby Solution

• Three parts

1. My plain solution
2. Two pointers scanning by Sharing my simple c++ code: O(n) time, O(1) space
3. Stack based solution by A stack based solution for reference, inspired by Histogram

The basic idea is: Find the valley, check the lower boundary (peak), and fill water.

My plain solution

``````  # Solution - plain
def trap(height)
return 0 if height.length == 0

# make head and tail of height are peaks
pre_process!(height)

# find max element's index
max_ele, max_idx = -1, -1

height.each_with_index do |ele, idx|
next if max_ele >= ele

max_ele = ele
max_idx = idx
end

calc_trap(height[0..max_idx]) + calc_trap(height[max_idx..-1].reverse)
end

# Pre-condition: tail of height is the max element
def calc_trap(height)
return 0 if height.length < 3

n = height.length
pos = 0
res = 0
peak = height[0]

loop do
p1 = pos
pos += 1 while pos+1 < n && height[pos] >= height[pos+1]
pos += 1 while pos+1 < n && height[pos] <= height[pos+1]
p2 = pos

height[p1+1..p2].each do |ele|
next if peak <= ele
res += (peak - ele)
end

peak = height[pos] if peak < height[pos]

# puts "height: #{height}"
# puts "p1: #{p1} p2: #{p2}"
# puts "h1: #{height[p1]} h2: #{height[p2]}"
# puts "peak: #{peak}, res: #{res}"

break if pos+1 == n
end

res
end

def pre_process!(height)
n = height.length

# shift until the first peak
i = 0
i += 1 while i+1 < n && height[i] <= height[i+1]

# pop until the last peak
j = n-1
j -= 1 while j-1 >= 0 && height[j] <= height[j-1]

return 0 if i >= j

height[i..j]
end
``````

Two pointers scanning by Sharing my simple c++ code: O(n) time, O(1) space

``````  # Solution - two pointers
def trap(height)
left_max, right_max = 0, 0
water = 0

if left <= right
left_max < left ? left_max = left : (water += left_max - left)
else
right_max < right ? right_max = right : (water += right_max - right)
tail -= 1
end
end

water
end
d

``````

Stack based solution by A stack based solution for reference, inspired by Histogram

``````  # Solution - stack
def trap(height)
water = 0
stack = [] # used to store the index of height
i = 0

while i < height.length
if stack.empty? or height[i] <= height[ stack.last ]
stack << i
i += 1
else
valley = height[ stack.pop ]

next if stack.empty?

left_idx, right_idx = stack.last, i
peak = height.values_at(left_idx, right_idx).min

water += (peak - valley) * (right_idx - left_idx - 1)
end
end

water
end
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.