Teemo Attacking - Practice Coding Problems

Teemo Attacking - Problem

Array Simulation Easy

Our hero Teemo is attacking an enemy Ashe with poison attacks! When Teemo attacks Ashe, Ashe gets poisoned for 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.

Input & Output

Example 1 — Basic Case

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

› Output: 4

💡 Note: Attack at t=1: poison from [1,2]. Attack at t=4: poison from [4,5]. Total: 2 + 2 = 4 seconds

Example 2 — Overlapping Attacks

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

› Output: 3

💡 Note: Attack at t=1: poison [1,2]. Attack at t=2 resets timer: poison [2,3]. Total unique seconds: 1,2,3 = 3 seconds

Example 3 — Single Attack

$ Input: timeSeries = [1], duration = 3

› Output: 3

💡 Note: Only one attack at t=1, poison lasts for 3 seconds: [1,2,3]

Constraints

1 ≤ timeSeries.length ≤ 10⁴
0 ≤ timeSeries[i], duration ≤ 10⁷
timeSeries is sorted in non-decreasing order

Visualization

Tap to expand

Understanding the Visualization

Input

Array of attack times and poison duration

Process

Calculate poison intervals with timer resets

Output

Total seconds poisoned

Key Takeaway

🎯 Key Insight: When attacks are close together, the poison timer resets - we only add the actual poisoned time, not overlapping periods

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that consecutive attacks either overlap or don't - we only need to add the minimum of the gap between attacks and the poison duration. The optimal approach uses gap analysis to calculate poison time in O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Gap Analysis	O(n)	O(1)	Calculate poison duration by analyzing gaps between consecutive attacks
Brute Force - Track Every Second	O(n × duration)	O(max_time)	Simulate every second and track poison status

Optimized - Gap Analysis — Algorithm Steps

Iterate through consecutive attack pairs
Calculate gap between attacks
Add minimum of gap and duration to total
Add full duration for last attack

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare Attacks

Look at consecutive attack pairs

Calculate Gap

Find time difference between attacks

Add Minimum

Add min(gap, duration) to total

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int* timeSeries, int timeSeriesSize, int duration) {
    if (timeSeriesSize == 0 || duration == 0) {
        return 0;
    }
    
    if (timeSeriesSize == 1) {
        return duration;
    }
    
    int total = 0;
    for (int i = 0; i < timeSeriesSize - 1; i++) {
        int gap = timeSeries[i + 1] - timeSeries[i];
        total += min(gap, duration);
    }
    
    // Add duration for the last attack
    total += duration;
    
    return total;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int timeSeries[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        timeSeries[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int duration;
    scanf("%d", &duration);
    
    printf("%d\n", solution(timeSeries, size, duration));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array of attacks

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to track total and current calculations

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Gap Analysis — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler