Java 7 lines O(n) solution


  • 10
    Y

    For each begin followed by t
    If t is within previous duration [begin, begin + duration] then increase total by t - begin
    If t in out of previous duration [begin, begin + duration] then increase total by duration
    In both cases update begin to the new begin time t

        public int findPoisonedDuration(int[] timeSeries, int duration) {
            if (timeSeries.length == 0) return 0;
            int begin = timeSeries[0], total = 0;
            for (int t : timeSeries) {
                total = total + (t < begin + duration ? t - begin : duration);
                begin = t;
            }   
            return total + duration;
        } 
    

  • 1
    R

    C++ version:

    class Solution {
    public:
        int findPoisonedDuration(vector<int>& timeSeries, int duration) {
            if(timeSeries.size() == 0) return 0;
            int begin = timeSeries[0], total = 0;
            for(auto t : timeSeries) {
                total += t < begin + duration ? t- begin : duration;
                begin = t;
            }
            return total + duration;
        }
    };
    

    Golang:

    func findPoisonedDuration(timeSeries []int, duration int) int {
        if len(timeSeries) == 0 {
            return 0
        }    
        begin, total := timeSeries[0], 0
        
        for _, v := range timeSeries {
            if v < begin  + duration {
                total += v - begin
            } else {
                total += duration 
            }
            begin = v
        }
        return total + duration
    }
    

    Javascript:

    var findPoisonedDuration = function(timeSeries, duration) {
        if(timeSeries.length == 0) return 0;
        var begin = timeSeries[0], total = 0;
        for (let t of timeSeries) {
            total += t < begin + duration ? t - begin : duration
            begin = t
        }
        return total + duration
    };
    
    

  • 0

    C# - I think it is a little simpler if you track end instead of start

        public int FindPoisonedDuration(int[] timeSeries, int duration) 
        {
            int cnt = 0, end = 0;
            foreach (int x in timeSeries)
            {
                cnt += end > x ? duration - (end - x) : duration;
                end = x + duration;
            }
            return cnt;
        }
    

  • 1

    These two examples are just the two cases:
    Input: [1,4], 2

    1. start + duration - 1 = 2
    2. 4 > 2, res = 2
    3. start = 4
    4. res = 2 + 2

    Input: [1,2], 2

    1. start + duration - 1 = 2
    2. 2 == 2, res= 2 - 1 = 1
    3. start = 2
    4. res = 1 + 2
        public int findPoisonedDuration(int[] timeSeries, int duration) {
          if(timeSeries.length == 0) return 0;
          
          int start = timeSeries[0], res = 0;
          for(int time : timeSeries){
             if(time > start + duration - 1){
                res += duration;
             } else {
                res += time - start;
             }
             start = time;
          }    
          return res + duration;
        }

  • 1

    Another approach.

    public int findPoisonedDuration(int[] timeSeries, int duration) {
            int ttime = 0;
            for (int idx = 1; idx < timeSeries.length; idx ++) 
                ttime += Math.min (timeSeries [idx] - timeSeries [idx - 1], duration);
            if (timeSeries.length > 0) ttime += duration;
            return ttime;
    }
    

  • 0

    Here's another one. Try to maintain invariant: duration of poison condition before ts[i] are accumulated on total. Thanks for sharing!

        public int findPoisonedDuration(int[] ts, int duration) {
            if (ts.length == 0) return 0;
            int total = 0, reach = ts[0] + duration; // how long poison condition will last by now
            for (int i = 1; i < ts.length; i++) {
                total += Math.min(ts[i], reach) - ts[i - 1];
                reach = ts[i] + duration;
            }
            return total + duration; // don't forget last duration
        }
    

  • 1
    Z

    just Math.min should do, why need a extra variable?

    public int findPoisonedDuration(int[] timeSeries, int duration) {
            if (timeSeries == null || timeSeries.length == 0) return 0;
       
            int sum = 0;
            for (int i=1; i<timeSeries.length; i++) {
                sum += Math.min(timeSeries[i] - timeSeries[i-1], duration);
            }
            
            return sum+duration;
        }
    

  • 0
    Y
    public class Solution {
    
        public int findPoisonedDuration(int[] timeSeries, int duration) {
            if(timeSeries.length == 0){
                return 0;
            }
            int sum = 0;
            for (int i = 1; i < timeSeries.length; i++) {
                sum += Math.min(timeSeries[i] - timeSeries[i - 1],duration);
            }
            return sum + duration;
        }
    }
    

Log in to reply
 

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