Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
This problem is also called trapping rain water problem. This problem can be solved using stacks approach and sliding window approach. But the ultimate approach is using only left-max and right-max values and in a single loop.
I this problem designer had this ultimate approach in mind and created the problem accordingly. Kudos to the problem designers.
I first tried stack approach with more if conditions.
First tried solution :
struct stknode{
int val;
};struct stk{
struct stknode *stk_ar;
int curidx;
int stksz;// current stk allocated size
};#define STK_INIT_SIZE 100struct stk *stk_create(int size){
struct stk *stkp;
stkp = (struct stk *)calloc(1, sizeof(struct stk));
stkp->stk_ar = (struct stknode *)calloc(size, sizeof(struct stknode));
stkp->stksz = size;
return stkp;
}int stk_push(struct stk *s, int val){
if (s->curidx >= s->stksz){
s->stksz += STK_INIT_SIZE;
s->stk_ar = (struct stknode *)realloc(s->stk_ar, s->stksz*sizeof(struct stknode));
}
s->stk_ar[s->curidx].val = val;
s->curidx++;
return 0;
}int stk_pop(struct stk *s){
if (!s->curidx)
return -1;
s->curidx--;
return (s->stk_ar[s->curidx].val);
}int stk_empty(struct stk *s){
return (!(s->curidx));
}
int stk_top(struct stk *s){
if (s->curidx)
return(s->stk_ar[s->curidx-1].val);
return -1;
}
void stk_assign_top(struct stk *s, int val){
if (s->curidx)
s->stk_ar[s->curidx-1].val = val;
return;
}int trap(int* height, int heightSize){
int res = 0;
int ii, top, prev_top, diff, diffind;
struct stk *st;
st = stk_create(100);
// todo check
for (ii=0; ii<heightSize; ii++){
/* check if stack is not empty */
if (!stk_empty(st)){
/* take the value of top element */
top = stk_top(st);
/* if top is smaller than current height */
if (height[top] < height[ii]){
//current height is bigger , pop it
top = stk_pop(st);
do {
diff = height[ii] - height[top];
prev_top = -1;
/* next check if another element in stack and
is greater than top */
while ((!stk_empty(st)) &&
(prev_top = stk_top(st)) &&
(height[prev_top] <= height[top])) {
prev_top = stk_pop(st);}
if (prev_top != -1) {
if (height[prev_top] <= height[ii])
prev_top = stk_pop(st);
if ((height[prev_top] - height[top]) < diff)
diff = height[prev_top] - height[top];
// printf("height[ii %d] %d, height[top %d] %d, height[prev_top %d] %d dif %d, diff_ind %d\n", ii, height[ii], top, height[top], prev_top, height[prev_top], diff, ii-prev_top);
if (diff)
res += (diff * (ii-prev_top-1));
top = prev_top;
if (height[top] >= height[ii])
break;
}
} while (!stk_empty(st));
}
}
// if the value is same, index should be updated
if (stk_empty(st) ||
(height[stk_top(st)] != height[ii]))
stk_push(st, ii);
else
stk_assign_top(st,ii);
}
return res;
}
after this, I felt my solution is complex. This many if conditions not expected.
then started going through solutions and learnt below solutions.
Optimized stacks approach:
/* improved version of above stack approach */
/* issue was with multiple checks */
int trap(int* height, int heightSize){
int res = 0;
int ii, top, prev_top, diff, diffind;
struct stk *stk;
stk = stk_create(100);
// todo check
for (ii=0; ii<heightSize; ii++){
/* check if stack is not empty and
the top value is lesser than the current element */
while ((!stk_empty(stk)) &&
(height[stk_top(stk)] < height[ii])) {
/* pop the stack element */
top = stk_pop(stk);
/* check for the next element in stack */
if (stk_empty(stk)) break;
/* check the difference */
prev_top = stk_top(stk);
diff = (height[ii] - height[top]) ;
diff = (diff > (height[prev_top] - height[top])) ?
(height[prev_top] - height[top]) : diff;
if (diff)
res += diff*(ii-prev_top-1);
}
stk_push(stk, ii);
}
return res;
}Sliding window approach:
/* sliding window method */
/* calculate max height of left side walls,
calculate the max height of right side walls
check the right and left walls sizes,
if bigger than current wall size, take the difference and
calculate the trap amount
*/
int trap(int* height, int hs){
int res = 0;
int lmax[hs], rmax[hs];
int ii,jj;
if (hs < 2)
return 0; /* calculate the array of left max and right max arrays*/
lmax[0] = 0; lmax[1] = 0;
rmax[hs-1] = 0; rmax[hs-2] = hs-1;
for (ii=2, jj= hs-3; ii<hs,jj>0; ii++, jj--){
if (height[ii-1] > height[lmax[ii-1]]) lmax[ii] = ii-1;
else lmax[ii] = lmax[ii-1];
if (height[jj+1] > height[rmax[jj+1]]) rmax[jj] = jj+1;
else rmax[jj] = rmax[jj+1];
} /* check if the corresponding left and right max values
are greater than current elements,
then calculate diff and add it to trap amount */
for (ii=1; ii<hs-1; ii++){
if ((height[ii] < height[lmax[ii]]) &&
(height[ii] < height[rmax[ii]])){
if (height[lmax[ii]] < height[rmax[ii]])
res += (height[lmax[ii]] - height[ii]);
else
res += (height[rmax[ii]] - height[ii]);
}
}
return res;
}
Below is the optimised approach for this problem where no space complexity and no additional time complexity.
/* Optimization of left max and right max approach */
/*
* initialise leftmax and rightmax
* set start to 0 and end to array size -1
* in a while loop check the a[start] with a[end],
* if a[start] < a[end]
* check leftmax value with a[start],
* if a[start] > left-max --> set the left-max to a[start]
* else (this means there is a before the current element)
* water can be trapped here ,
* increment trap amount with diff left-max and a[start]
* increment start to proceed to next element
* else (a[end] is greater than a[start])
* action on right-max
* check rightmax with a[end],
* if a[end] > right -max --> set the right-max to a[end]
* else case is where there is bigger wall after this current element
* water can be trapped at this current element
* increment the trap amount with diff of right-max and a[end]
* decrement end to proceed to previous element.
if bigger than current wall size, take the difference and
calculate the trap amount
*/
int trap(int* height, int hs){
int res = 0;
int lmax=height[0], rmax;
int strt = 0, end = hs-1;
if (hs < 2)
return 0;
rmax = height[hs-1];
while (strt < end){
/* check the case where height of start position is greater than
height of end position.
take the action on left-max */
if (height[strt] < height[end]){
/* case where current element height is bigger than
left max */
if (height[strt] >= lmax) lmax = height[strt];
/* case where there is bigger wall left side of it,
trap amount can be incremented here */
else res += (lmax - height[strt]);
strt++;
continue;
}
{/* take action on right max */
/* case where the current element height is bigger than
right max */
if (height[end] >= rmax) rmax = height[end];
/* case where there is bigger wall right side of it,
trap amound can be incremented here */
else res += (rmax - height[end]);
end --;
}
}
return res;
}Can we still optimize?
This left max and right max approach is very well explained in here. He tells this approach as lower envelope technique where
g(i)= min (max(H(1..i)), max(H(n..i)))
max(H(1..i)) is left max, max(H(n..i)) is right max. g(i) is the minimum of these values. As the name indicates lower envelope technique, lower value considered and next index is moved from the side of lower value.
