My 4ms O(n) C solution using 2 pointer


  • 0
    H
    int trap(int* height, int hsz) {
    int left = 0, right = hsz - 1,ret = 0,hlast = 0;
    int *ptr[]={&left,&right};
    const int step[]={1,-1};
    while(left <= right)
    {
        int tmp = (height[left] > height[right]);
        if(height[*ptr[tmp]] > hlast)
            hlast = height[*ptr[tmp]];
        else
            ret += hlast - height[*ptr[tmp]];
        *ptr[tmp] += step[tmp];
    }
    return ret;
    

    }


Log in to reply
 

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