LeetCode 495: Teemo Attacking Solution in Python – A Step-by-Step Guide

What Is LeetCode 495: Teemo Attacking?

In LeetCode 495: Teemo Attacking, you’re given an integer array timeSeries representing the times Teemo attacks an enemy, and an integer duration for how long each poison lasts. Your task is to calculate the total time the enemy is poisoned, accounting for overlapping poison durations. For example, with timeSeries = [1, 4] and duration = 2, the poison covers 1-3 and 4-6 (4 seconds total); with [1, 2] and duration = 2, it’s 1-4 (3 seconds due to overlap). It’s like tracking how long Teemo’s poison keeps the enemy under its effect, merging those pesky overlapping darts into one continuous sting.

Problem Statement

• Input: timeSeries (List[int])—array of attack times; duration (int)—poison duration per attack.
• Output: int—total time the enemy is poisoned.
• Rules:
• Each attack at time t poisons from t to t + duration - 1.
• Overlapping durations merge into continuous poisoned time.
• timeSeries is sorted in non-decreasing order.

Constraints

• \( 0 \leq timeSeries.length \leq 10^4 \).
• \( 0 \leq timeSeries[i], duration \leq 10^7 \).

Examples to Get Us Started

• Input: timeSeries = [1,4], duration = 2
• Output: 4 (Poisoned: 1-3, 4-6, total = 4).
• Input: timeSeries = [1,2], duration = 2
• Output: 3 (Poisoned: 1-4, total = 3 due to overlap).
• Input: timeSeries = [], duration = 5
• Output: 0 (No attacks, no poison).

Understanding the Problem: Tracking the Sting

To solve LeetCode 495: Teemo Attacking in Python, we need to calculate the total time an enemy is poisoned, given attack times in timeSeries and a fixed duration per attack, merging overlapping poison intervals. A naive approach—simulating the entire timeline—could be O(n + T) (T = max time), inefficient for large durations or times up to 10^7. The key? Use a single-pass approach to compute non-overlapping durations by comparing consecutive attack times, achieving O(n) time (n = length of timeSeries). We’ll explore:

• Best Solution (Single-Pass Interval Merging): O(n) time, O(1) space—fast and optimal.
• Alternative Solution (Brute Force Timeline Simulation): O(n + T) time, O(T) space—simple but slow.

Let’s dive into the single-pass solution—it’s Teemo’s precise dart we need.

Best Solution: Single-Pass Interval Merging

Why This Is the Best Solution

The single-pass interval merging approach is the top pick because it’s O(n) time (n = length of timeSeries) and O(1) space, efficiently calculating the total poisoned time by iterating through timeSeries once, adding the minimum of the full duration or the gap to the next attack, thus merging overlaps naturally. It avoids simulating the entire timeline, leveraging the sorted nature of timeSeries. It’s like Teemo darting through his attack log, tallying poison time with a quick glance—smart and streamlined!

How It Works

Here’s the strategy:

• Step 1: Handle edge case:
• If timeSeries is empty, return 0.
• Step 2: Iterate through timeSeries:
• For each attack time t[i]:
• Poison lasts from t[i] to t[i] + duration - 1.
• If next attack t[i+1] exists, add min(duration, t[i+1] - t[i]).
• This merges overlaps (e.g., if next attack is within duration, take gap).
• Step 3: Add final attack’s full duration.
• Step 4: Return total poisoned time.
• Why It Works:
• Min(duration, gap) ensures no double-counting of overlapped time.
• Final duration added covers last attack fully.

Step-by-Step Example

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

• Init: total = 0.
• i=0: t[0] = 1, poison 1-3:
• Next t[1] = 4, gap = 4 - 1 = 3, min(2, 3) = 2.
• Total = 2.
• i=1: t[1] = 4, poison 4-6 (last):
• Add duration = 2, total = 2 + 2 = 4.
• Result: 4.

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

• i=0: 1-3, gap to 2 = 1, min(2, 1) = 1, total = 1.
• i=1: 2-4 (last), total = 1 + 2 = 3.
• Result: 3.

Example: timeSeries = [1,2,3], duration = 3

• i=0: 1-4, gap to 2 = 1, min(3, 1) = 1, total = 1.
• i=1: 2-5, gap to 3 = 1, min(3, 1) = 1, total = 2.
• i=2: 3-6, total = 2 + 3 = 5.
• Result: 5.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
        # Step 1: Handle empty case
        if not timeSeries:
            return 0

        # Step 2: Iterate and merge intervals
        total = 0
        for i in range(len(timeSeries) - 1):
            # Add min of duration or gap to next attack
            total += min(duration, timeSeries[i + 1] - timeSeries[i])

        # Step 3: Add final attack duration
        total += duration

        # Step 4: Return total poisoned time
        return total

• Line 4-5: Return 0 if no attacks.
• Line 8-11: Loop through attacks:
• Add min(duration, gap) to avoid overlap.
• Line 14: Add final duration (no next attack to overlap).
• Line 17: Return total.
• Time Complexity: O(n)—single pass through timeSeries.
• Space Complexity: O(1)—single variable.

It’s like Teemo’s dart timer!

Alternative Solution: Brute Force Timeline Simulation

Why an Alternative Approach?

The brute force timeline simulation—O(n + T) time (T = max time), O(T) space—creates a timeline array marking each second as poisoned or not, then counts total poisoned seconds. It’s slow and memory-heavy but intuitive, like painting the whole timeline with Teemo’s poison to see the coverage. Good for small timelines or learning!

How It Works

• Step 1: Find max time (last attack + duration).
• Step 2: Create timeline array, mark poisoned seconds.
• Step 3: Count total poisoned seconds.
• Step 4: Return count.

Step-by-Step Example

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

• Max time: 2 + 2 = 4.
• Timeline: [0, 0, 0, 0] → [0, 1, 1, 0] (1-3) → [0, 1, 1, 1] (2-4).
• Count: 3 (seconds 1, 2, 3 poisoned).
• Result: 3.

Code for Brute Force

Copy codeclass Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
        if not timeSeries:
            return 0

        # Step 1: Determine timeline size
        max_time = max(timeSeries) + duration
        timeline = [0] * max_time

        # Step 2: Mark poisoned seconds
        for t in timeSeries:
            for i in range(t, min(t + duration, max_time)):
                timeline[i] = 1

        # Step 3-4: Count and return
        return sum(timeline)

• Line 4-10: Setup timeline up to max time.
• Line 12-14: Mark each attack’s duration.
• Line 17: Sum poisoned seconds.
• Time Complexity: O(n + T)—n attacks, T timeline size.
• Space Complexity: O(T)—timeline array.

It’s a slow poison painter!

Comparing the Two Solutions

• Single-Pass (Best):
• Pros: O(n), fast, no extra space.
• Cons: Requires interval logic.
• Brute Force (Alternative):
• Pros: O(n + T), intuitive.
• Cons: Slow, memory-intensive.

Single-pass wins for efficiency.

Edge Cases and Examples

• Input: [], 5 → 0.
• Input: [1], 1 → 1.
• Input: [1,1], 2 → 2.

Single-pass handles all perfectly.

Complexity Recap

• Single-Pass: Time O(n), Space O(1).
• Brute Force: Time O(n + T), Space O(T).

Single-pass is the champ.

Key Takeaways

• Single-Pass: Merge intervals smartly.
• Brute Force: Paint the timeline.
• Python Tip: Loops optimize—see [Python Basics](/python/basics).

Final Thoughts: Dart That Poison

LeetCode 495: Teemo Attacking in Python is a tactical poison timer. Single-pass interval merging is your fast dart, while brute force is a slow brush. Want more interval fun? Try LeetCode 56: Merge Intervals or LeetCode 252: Meeting Rooms. Ready to poison some foes? Head to Solve LeetCode 495 on LeetCode and dart it today—your coding skills are Teemo-ready!