# One pointer solution / Divide&Conquer solution / Explanation / Python

• For every "temp highest bar" so far, we suppose there exists a bar that is higher, and we can add water without worrying, until we find a bar there is no bar higher in the future, we reverse the rest of the array and add water again

The solution is actually very similar to two-pointer solution

``````class Solution(object):
def trap(self, height):  # one pointer solution
if len(height)<=2:
return 0
def one_pass_to_last_high(height):
temp_max, temp_water, water_total, last_id = 0,0,0,0
for i, h in enumerate(height):
if h>=temp_max:
water_total+=temp_water
last_id, temp_max, temp_water = i, h, 0
else:
temp_water+=(temp_max-h)
return last_id, water_total

last_id, total_water = one_pass_to_last_high(height)

``````

Divide&Conquer is much more easier to understand, the highest bar and the second highest bar can always form a "bowl" and contain water if they have distance in x-axis, then we divide until there is no "bowl" at all

``````class Solution(object):
def trap(self, height):   # dc solution
"""
:type height: List[int]
:rtype: int
"""

if len(height)<=2:
return 0

# find indices of the top2 highest bar
max_1 = max_2 = float('-inf')
idx1 = idx2 = len(height)
for i, h in enumerate(height):
if h>max_2:
if h>max_1:
max_1, max_2, idx1, idx2 = h, max_1, i, idx1
else:
max_2, idx2 = h, i
if idx1>idx2:
idx1, idx2 = idx2, idx1
# finish finding

return self.one_bowl(height[idx1:idx2+1])+self.trap(height[:idx1+1])+self.trap(height[idx2:])

def one_bowl(self, heights):
h_min, water_sum = min(heights[0], heights[-1]), 0
for h in heights[1:-1]:
water_sum+=(h_min-h)
return water_sum
``````

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