Code Logo

Find Poisoned Duration

Published at24 Jul 2026
Created by
Easy 0 views
Like0

In the game League of Legends, Teemo attacks Ashe and poisons her. Given an array timeSeries of attack times and an integer duration (poison lasts for duration seconds after each attack), return the total seconds that Ashe is poisoned. If a new attack hits before the previous poison expires, the poison timer resets from the new attack time.

This is a state tracking DP problem. Track the end time of the current poison. For each attack time t, if t is greater than or equal to the previous poison end time, add the full duration. Otherwise, add the non-overlapping portion: t + duration - end. Then update the end time to t + duration.

The DP recurrence maintains a single state variable (end time) and accumulates the total duration. Each attack's contribution depends entirely on the previous end time, which captures all relevant history. This is a classic example of overlapping interval aggregation.

Time is O(n) with O(1) space. Edge cases include empty timeSeries (return 0), single attack (return full duration), and overlapping attacks where the total is less than attacks times duration due to overlaps.

This problem illustrates how DP state can be a single scalar that captures all necessary history, enabling linear-time processing of sequential events with dependency on previous state.

Example Input & Output

Example 1
Input
[1], 5
Output
5
Explanation

Single attack total=5.

Example 2
Input
[], 10
Output
0
Explanation

No attacks.

Example 3
Input
[1,2,3], 2
Output
4
Explanation

1-3,2-4,3-5: 2+1+1=4.

Example 4
Input
[1,4], 2
Output
4
Explanation

First 1-3, second 4-6. Total=4.

Example 5
Input
[1,2], 2
Output
3
Explanation

First 1-3, second 2-4: overlap total=3.

Algorithm Flow

Recommendation Algorithm Flow for Find Poisoned Duration
Recommendation Algorithm Flow for Find Poisoned Duration

Solution Approach

Track poison end time. For each attack, add full duration if no overlap, else add only the non-overlapping part.

function solution(timeSeries, duration) {
  if (timeSeries.length === 0) return 0;
  var total = 0;
  var end = 0;
  for (var i = 0; i < timeSeries.length; i++) {
    var t = timeSeries[i];
    if (t >= end) total += duration;
    else total += t + duration - end;
    end = t + duration;
  }
  return total;
}

Time O(n), Space O(1).

Best Answers

java
class Solution {
    public int solution(int[] timeSeries, int duration) {
        if (timeSeries.length==0) return 0;
        int total=0,end=0;
        for (int t: timeSeries) {
            if (t>=end) total+=duration;
            else total+=t+duration-end;
            end=t+duration;
        }
        return total;
    }
}