Find Poisoned Duration (LeetCode 495) - Understanding Overlapping Intervals

Difficulty: Easy

Topics: Array

Platform: Leetcode

Problem Statement

Our hero Teemo is attacking an enemy Ashe with poison attacks! When Teemo attacks Ashe, Ashe gets poisoned for a exactly duration seconds. More formally, an attack at second t will mean Ashe is poisoned during the inclusive time interval [t, t + duration - 1]. If Teemo attacks again before the poison effect ends, the timer for it is reset, and the poison effect will end duration seconds after the new attack.

You are given a non-decreasing integer array timeSeries, where timeSeries[i] denotes that Teemo attacks Ashe at second timeSeries[i], and an integer duration.

Return the total number of seconds that Ashe is poisoned.

Problem Statement Simplified

Imagine a character gets attacked multiple times, and each attack causes a poison effect that lasts for a fixed duration.

You are given:

timeSeries → the times when attacks happen.

duration → how long each poison effect lasts.

Your task is to calculate the total time the character remains poisoned.

Mistakes and Learning

1. Overwriting the Result Instead of Accumulating

• A common mistake is:




• result = timeSeries.length * duration - overlap;




• inside a loop.




• This overwrites the previous value of result during every iteration.




• Assuming Only One Overlap Exists




• Another mistake is calculating overlap only between the current pair and directly subtracting it from the total duration.




• Each pair of attacks can create a different overlap, so we need to process every attack individually.

Example 1

Input: timeSeries = [1,4], duration = 2

Output: 4

Explanation: Teemo's attacks on Ashe go as follows:

- At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2.

- At second 4, Teemo attacks, and Ashe is poisoned for seconds 4 and 5.

Ashe is poisoned for seconds 1, 2, 4, and 5, which is 4 seconds in total.

Example 2

Input: timeSeries = [1,2], duration = 2

Output: 3

Explanation: Teemo's attacks on Ashe go as follows:

- At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2.

- At second 2 however, Teemo attacks again and resets the poison timer. Ashe is poisoned for seconds 2 and 3.

Ashe is poisoned for seconds 1, 2, and 3, which is 3 seconds in total.

Key Insight

1. Count Only the New Poison Time Added
   For every attack:

• If the next attack occurs after the poison expires, add the full duration.




• If the next attack occurs before the poison expires, add only the non-overlapping part.

Algorithm

1.  Start with the first attack's poison durationSort the new array.


2. Traverse the remaining attacksthe second largest


3. Return the result

Algorithm in simple words

Think of poison as a timeline.

Every attack tries to add duration seconds of poison.

If there is no overlap, add the full duration.

If there is overlap, add only the time gap between attacks.

Repeat this for every attack and keep a running total.

Java code

class Solution {

    public int findPoisonedDuration(int[] timeSeries, int duration) {

        int  result = duration;

        if(timeSeries.length==1){

            return duration;

        }

        else{



for (int i = 1; i < timeSeries.length; i++) {

    result += Math.min(duration, timeSeries[i] - timeSeries[i-1]);

}



        }

        return result;

    }

}

Time & Space Complexity

Time Complexity: O(n)

Space Complexity: O(1)