algoadvance

Leetcode 495. Teemo Attacking

Problem Statement

In the game, Teemo is attacking an enemy Ashe with poison attacks. When Teemo attacks Ashe, Ashe gets poisoned for a certain duration of time. If Teemo attacks again before the poison effect ends, the poison duration will be extended by the time of the new attack, not by adding the new attack’s poison time to the remaining poison time.

You are given a non-decreasing array timeSeries where timeSeries[i] denotes the time at which Teemo attacks Ashe, and an integer duration which denotes the duration of the poison effect. Your task is to return the total time that Ashe is poisoned.

Example

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

  2. Input: timeSeries = [1, 2], duration = 2 Output: 3

Clarifying Questions

  1. Can timeSeries be empty?
    • Yes, if timeSeries is empty, the output should be 0 since no attack means no poison.
  2. Is the timeSeries guaranteed to be sorted?
    • Yes, it is guaranteed to be a non-decreasing array.
  3. Can duration be zero or negative?
    • For the purpose of this problem, duration will be a positive integer.

Code

public class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        if (timeSeries.length == 0) return 0;

        int totalDuration = 0;

        for (int i = 0; i < timeSeries.length - 1; i++) {
            totalDuration += Math.min(timeSeries[i + 1] - timeSeries[i], duration);
        }

        // Add the duration for the last attack
        totalDuration += duration;

        return totalDuration;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        
        int[] timeSeries1 = {1, 4};
        int duration1 = 2;
        System.out.println(solution.findPoisonedDuration(timeSeries1, duration1));  // Output: 4

        int[] timeSeries2 = {1, 2};
        int duration2 = 2;
        System.out.println(solution.findPoisonedDuration(timeSeries2, duration2));  // Output: 3
    }
}

Strategy

  1. Initialize totalDuration: Start by initializing totalDuration to 0.
  2. Iterate through the timeSeries array:
    • For each attack, determine the duration of poisoning by comparing the difference between the current attack and the next attack with duration.
    • Use Math.min(timeSeries[i + 1] - timeSeries[i], duration) to get the actual contaminated time due to overlapping attacks.
  3. Add the duration of the last attack: Once loop terminates, append the duration caused by the last attack.
  4. **Return the calculated totalDuration.

Time Complexity

This ensures the solution is both time and space efficient, making it suitable for large inputs as well.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI