How do you solve Human Traffic of Stadium on LeetCode?

Human Traffic of Stadium (LeetCode #601) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Consecutive IDs can be tracked using a simple counter.

What is the brute force solution for Human Traffic of Stadium?

The brute force approach for Human Traffic of Stadium is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute-force approach, we will check every possible combination of rows to find groups of three or more consecutive IDs with people counts of 100 or more. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Human Traffic of Stadium?

Human Traffic of Stadium uses the following concepts: Database. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Human Traffic of Stadium?

Always clarify the problem requirements before diving into coding. Think about edge cases, such as when there are no valid groups. Discuss your thought process and reasoning as you code.

What are common mistakes when solving Human Traffic of Stadium?

Not checking for consecutive IDs properly. Failing to reset the counter when encountering invalid rows.

#601

Human Traffic of Stadium

Hard

DatabaseHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

In the optimal approach, we will use a single pass through the table to count consecutive IDs with people counts of 100 or more. This is efficient because we avoid nested loops.

⚙️

Algorithm

4 steps

1Step 1: Initialize a counter to track consecutive valid rows and a list to store results.
2Step 2: Loop through the Stadium table, checking if each row has people >= 100.
3Step 3: If valid, increment the counter; if not, reset the counter and check if we have enough valid rows to add to the results.
4Step 4: After the loop, check if the last counted group is valid and add it to the results.

solution.py13 lines

1# Full working Python code
2WITH Consecutive AS (
3    SELECT id, visit_date, people,
4           ROW_NUMBER() OVER (ORDER BY id) -
5           ROW_NUMBER() OVER (PARTITION BY people >= 100 ORDER BY id) AS grp
6    FROM Stadium
7    WHERE people >= 100
8)
9SELECT id, visit_date, people
10FROM Consecutive
11GROUP BY grp
12HAVING COUNT(*) >= 3
13ORDER BY visit_date;

ℹ

Complexity note: The time complexity is O(n) because we only loop through the table once, and the space complexity is O(n) due to the storage of intermediate results.

1Consecutive IDs can be tracked using a simple counter.
2Filtering out rows with less than 100 people early can save processing time.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.