LeetCode 601: Human Traffic of Stadium Solution in Python – A Step-by-Step Guide

What Is LeetCode 601: Human Traffic of Stadium?

In LeetCode 601: Human Traffic of Stadium, you’re given a table of stadium records with three columns: id (day number), date, and people (attendance). Your task is to find all days where the attendance is at least 100 people for three consecutive days, including the current day as part of the streak. For example, if days 1, 2, and 3 have 50, 150, and 200 people, day 2 starts a valid streak (days 2, 3, 4 might continue it). This problem tests your ability to handle sequential data, often framed as an SQL query, but we’ll solve it in Python for a coding twist.

Problem Statement

• Input: A list of records (or table rows) with id, date, and people.
• Output: A list of records where people >= 100 for three consecutive days (including the day itself in a triplet).
• Rules:
• Days are consecutive by id.
• Return all qualifying records in any order.

Constraints

• Table has at least 3 rows.
• id is unique and sequential (1, 2, 3, …).
• people is a non-negative integer.

Examples

• Input:
``` id | date | people 1 | 2025-01-01 | 50 2 | 2025-01-02 | 150 3 | 2025-01-03 | 200 4 | 2025-01-04 | 120 5 | 2025-01-05 | 80 ```
• Output:
``` id | date | people 2 | 2025-01-02 | 150 3 | 2025-01-03 | 200 4 | 2025-01-04 | 120 ```
• Input:
``` id | date | people 1 | 2025-01-01 | 100 2 | 2025-01-02 | 200 3 | 2025-01-03 | 50 ```
• Output: Empty (no three consecutive days >= 100).

These examples show how streaks form—let’s solve it!

Understanding the Problem: Finding Consecutive High-Traffic Days

To solve LeetCode 601: Human Traffic of Stadium in Python, we need to process a list of records and identify days that are part of a three-day streak where attendance is at least 100. A naive approach might check every possible triplet, but that’s inefficient and messy. Instead, we’ll use:

• Best Solution (Sliding Window): O(n) time, O(1) space—fast and elegant.
• Alternative Solution (Grouping with Iteration): O(n) time, O(n) space—simpler but uses more memory.

Let’s start with the sliding window, breaking it down for beginners.

Best Solution: Sliding Window with SQL-Like Logic

Why This Is the Best Solution

The sliding window approach is the top choice for LeetCode 601 because it’s efficient—O(n) time with O(1) space—and mimics SQL window functions like LEAD and LAG in a Python-friendly way. It slides through the records, checking triplets on the fly, and collects qualifying days without extra storage. It’s like scanning the crowd with a quick, focused lens!

How It Works

Think of this as sliding a three-day window across the stadium’s timeline:

• Step 1: Model the Data:
• Use a list of [id, date, people] records.
• Step 2: Slide the Window:
• For each day, check the current, previous, and next days (if they exist).
• A day qualifies if it’s part of a triplet where all have >= 100 people.
• Step 3: Check Triplets:
• Day i can be:
• End of a triplet (i-2, i-1, i).
• Middle of a triplet (i-1, i, i+1).
• Start of a triplet (i, i+1, i+2).
• If any triplet has all >= 100, include the day.
• Step 4: Collect Results:
• Add qualifying records to the result list.

It’s like spotlighting busy streaks with a moving frame!

Step-by-Step Example

Example:

Copy codeid | date       | people
1  | 2025-01-01 | 50
2  | 2025-01-02 | 150
3  | 2025-01-03 | 200
4  | 2025-01-04 | 120
5  | 2025-01-05 | 80

• Day 1 (50):
• No triplet possible yet.
• Day 2 (150):
• Check (1,2,3): 50, 150, 200—fails (50 < 100).
• Check (2,3,4): 150, 200, 120—all >= 100, qualifies.
• Day 3 (200):
• Check (1,2,3): Fails.
• Check (2,3,4): 150, 200, 120—qualifies.
• Check (3,4,5): 200, 120, 80—fails.
• Day 4 (120):
• Check (2,3,4): 150, 200, 120—qualifies.
• Check (3,4,5): Fails.
• Day 5 (80):
• Check (3,4,5): Fails.
• Output: Days 2, 3, 4.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def humanTraffic(self, records: List[List[int]]) -> List[List[int]]:
        # Step 1: Sort by id (assuming input is sorted, but ensure it)
        records.sort(key=lambda x: x[0])
        n = len(records)
        result = []

        # Step 2: Slide through records
        for i in range(n):
            curr_people = records[i][2]
            # Check if part of a valid triplet
            is_valid = False

            # Case 1: Current day is end of triplet (i-2, i-1, i)
            if i >= 2:
                if (records[i-2][2] >= 100 and 
                    records[i-1][2] >= 100 and 
                    curr_people >= 100):
                    is_valid = True

            # Case 2: Current day is middle of triplet (i-1, i, i+1)
            if i >= 1 and i < n-1:
                if (records[i-1][2] >= 100 and 
                    curr_people >= 100 and 
                    records[i+1][2] >= 100):
                    is_valid = True

            # Case 3: Current day is start of triplet (i, i+1, i+2)
            if i < n-2:
                if (curr_people >= 100 and 
                    records[i+1][2] >= 100 and 
                    records[i+2][2] >= 100):
                    is_valid = True

            # If part of any valid triplet, add to result
            if is_valid:
                result.append(records[i])

        return result

• Line 4: Sort by id (assumes input is sequential, but ensures order).
• Lines 7-31: Slide window:
• Check three cases for each day:
• Lines 12-16: End of triplet.
• Lines 19-23: Middle of triplet.
• Lines 26-30: Start of triplet.
• If any case passes, mark as valid.
• Line 33: Add valid records.
• Time Complexity: O(n)—single pass with constant checks.
• Space Complexity: O(1)—excluding output space.

This is like a quick crowd scan—spot the streaks fast!

Alternative Solution: Grouping with Iteration

Why an Alternative Approach?

The grouping approach tracks consecutive days with >= 100 people, then extracts triplets—O(n) time, O(n) space. It’s simpler to conceptualize but uses more memory to store groups. It’s like tallying busy stretches and picking out the qualifying days.

How It Works

Picture this as grouping busy days:

• Step 1: Iterate records, group consecutive days >= 100.
• Step 2: For each group of 3 or more, include all days.
• Step 3: Collect qualifying records.

It’s like marking busy blocks on a calendar!

Step-by-Step Example

Example:

Copy codeid | date       | people
1  | 2025-01-01 | 50
2  | 2025-01-02 | 150
3  | 2025-01-03 | 200
4  | 2025-01-04 | 120
5  | 2025-01-05 | 80

• Group:
• Day 1: < 100, skip.
• Days 2-4: 150, 200, 120—group of 3.
• Day 5: < 100, new group (empty).
• Result: Days 2, 3, 4 (group >= 3).

Code for Grouping Approach

Copy codeclass Solution:
    def humanTraffic(self, records: List[List[int]]) -> List[List[int]]:
        records.sort(key=lambda x: x[0])
        n = len(records)
        result = []

        i = 0
        while i < n:
            # Start a group
            group = []
            while i < n and records[i][2] >= 100:
                group.append(records[i])
                i += 1
            # If group has 3 or more, add all to result
            if len(group) >= 3:
                result.extend(group)
            i += 1

        return result

• Lines 7-13: Build groups of >= 100.
• Lines 14-15: Add groups of 3+ to result.
• Time Complexity: O(n)—single pass.
• Space Complexity: O(n)—storing groups.

It’s a straightforward tally!

Comparing the Two Solutions

• Sliding Window (Best):
• Pros: O(n) time, O(1) space, fast and lean.
• Cons: Slightly trickier logic.
• Grouping (Alternative):
• Pros: O(n) time, O(n) space, easy to follow.
• Cons: More memory usage.

Sliding window wins for efficiency.

Additional Examples and Edge Cases

• Input: [1, "2025-01-01", 100], [2, "2025-01-02", 200], [3, "2025-01-03", 300]
• Output: All three days.
• Input: [1, "2025-01-01", 50], [2, "2025-01-02", 50], [3, "2025-01-03", 50]
• Output: Empty.

Both handle these well.

Complexity Breakdown

• Sliding Window: Time O(n), Space O(1).
• Grouping: Time O(n), Space O(n).

Sliding window is optimal.

Key Takeaways

• Sliding Window: Quick triplet checks—smart!
• Grouping: Simple streaks—clear!
• Sequences: Consecutive logic is fun.
• Python Tip: Lists shine—see Python Basics.

Final Thoughts: Track That Traffic

LeetCode 601: Human Traffic of Stadium in Python is a cool sequence challenge. The sliding window offers speed and elegance, while grouping provides a clear alternative. Want more? Try LeetCode 128: Longest Consecutive Sequence or LeetCode 239: Sliding Window Maximum. Ready to scan the stands? Head to Solve LeetCode 601 on LeetCode and spot those busy days today!