Trapping Rain Water
Python
Hard
5 views
Problem Description
Read n heights. Water trapped between bars should be calculated and printed.
Input Format
First line n. Second line n heights.
Output Format
One integer water.
Sample Test Case
Input:
12
0 1 0 2 1 0 1 3 2 1 2 1
Official Solution
import sys
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
n=int(p[0])
h=list(map(int,p[1:1+n]))
if n==0:
sys.stdout.write('0')
else:
l=0
r=n-1
leftMax=0
rightMax=0
water=0
while l<r:
if h[l]<=h[r]:
if h[l]>=leftMax:
leftMax=h[l]
else:
water+=leftMax-h[l]
l+=1
else:
if h[r]>=rightMax:
rightMax=h[r]
else:
water+=rightMax-h[r]
r-=1
sys.stdout.write(str(water))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!