Rain Water Trap
Given a non-negative integer array representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. For example, given [0,1,0,2,1,0,1,3,2,1,2,1], returns 6.
Follow up:
What is the complexity of your solution?
for input:
A=[0,1,0,2,1,0,1,3,2,1,2,1]
N= sizeof(A)
compute B[] where B[i]= Max(A[0..i]) Calculate Max bar height from node 0-i
B=[0,1,1,2,2,2,2,3,3,3,3,3]
compute C[] where C[i]= Max(A[i..N]) Calculate Max bar height from node i-n
C=[3,3,3,3,3,3,3,3,2,2,2,1]
compute D[] where D[i]=Min(B[i],C[I]) Calculate Min bar height between bar before Vs after i, coz only this much water could fill
D=[0,1,1,2,2,2,2,3,2,2,2,1]
compute E[] where E[i]=D[i]-A[i] Subtract the height of bar i from Max water bars could hold before Vs after
E[i]=[0,0,1,0,1,2,1,0,0,1,0,0]
the answer is sum(E[i])
the complexity is O(N)