O(n) time, O(1) space, short DP C++ solution!


  • 0
    H
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
            
            if (duration == 0 || timeSeries.size() == 0) return 0;
            
            int dp0 = duration;
            int dp1 = 0;
            
            for (int i = 1; i < timeSeries.size(); i++) {
                int val = timeSeries[i-1] + duration - timeSeries[i];
                dp1 = dp0 + duration - (val>0 ? val:0);
                dp0 = dp1;
            }
            
            return dp0;
        }
    

Log in to reply
 

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