Rolling back solution in C++ with O(n) time and O(1) space


  • 0
    L
    class Solution {
    public:
        int trap(int A[], int n) {
            if (n==0) return 0;
            int tallest = 0, localTallest = 0, rain = 0, rainRollBack = 0;
            
            for (int i=0; i<n; i++)
            {
            	if (A[i]>=tallest)
            	{
            		tallest = A[i];
            		rainRollBack = rain;
            	}
            	else 
            	{
            		rain += tallest - A[i];
            	}
            }
            
            int i = n - 1;
            while (A[i]!=tallest)
            {
            	if (A[i]>=localTallest) localTallest = A[i];
            	else rainRollBack += localTallest - A[i];
            	i--;
            	rain = rainRollBack;
            }
            return rain;
        }
    };

Log in to reply
 

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