Java 8 lines O(n) solution


  • 0

    The maximum output is timeSeries[timeSeries.length - 1] - timeSeries[0] + duration. Then we just find uncovered time intervals.

    class Solution {
        public int findPoisonedDuration(int[] timeSeries, int duration) {
            if (timeSeries.length == 0 || duration == 0) return 0;
            int result = timeSeries[timeSeries.length - 1] - timeSeries[0] + duration;
            int endT = timeSeries[0] + duration;
            for (int i = 0; i < timeSeries.length; i++) {
                if (timeSeries[i] > endT) result -= timeSeries[i] - endT;
                endT = timeSeries[i] + duration;
            }
            return result;
        }
    }
    

Log in to reply
 

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