Table: Stadium
+---------------+---------+ | Column Name | Type | +---------------+---------+ | id | int | | visit_date | date | | people | int | +---------------+---------+ visit_date is the column with unique values for this table. Each row of this table contains the visit date and visit id to the stadium with the number of people during the visit. As the id increases, the date increases as well.
Write a solution to display the records with three or more rows with consecutive id's, and the number of people is greater than or equal to 100 for each.
Return the result table ordered by visit_date in ascending order.
The result format is in the following example.
Example 1:
Input: Stadium table: +------+------------+-----------+ | id | visit_date | people | +------+------------+-----------+ | 1 | 2017-01-01 | 10 | | 2 | 2017-01-02 | 109 | | 3 | 2017-01-03 | 150 | | 4 | 2017-01-04 | 99 | | 5 | 2017-01-05 | 145 | | 6 | 2017-01-06 | 1455 | | 7 | 2017-01-07 | 199 | | 8 | 2017-01-09 | 188 | +------+------------+-----------+ Output: +------+------------+-----------+ | id | visit_date | people | +------+------------+-----------+ | 5 | 2017-01-05 | 145 | | 6 | 2017-01-06 | 1455 | | 7 | 2017-01-07 | 199 | | 8 | 2017-01-09 | 188 | +------+------------+-----------+ Explanation: The four rows with ids 5, 6, 7, and 8 have consecutive ids and each of them has >= 100 people attended. Note that row 8 was included even though the visit_date was not the next day after row 7. The rows with ids 2 and 3 are not included because we need at least three consecutive ids.
This approach utilizes SQL window functions to help identify consecutive rows with the required conditions. By computing a lag on the 'people' field, we can identify groups of qualifying rows by checking the conditions on currently selected and previous rows.
This SQL solution makes use of the LAG function to look into previous rows' people counts. The three consecutive rows meeting the criteria are filtered using WHERE conditions.
The time complexity of this query is O(n), where n is the number of rows because each row is processed once. The space complexity is also O(n) due to the use of window functions.
In this approach, we manually iterate over the records, maintaining a sliding window of three elements to check the condition on people counts. This involves checking the count of the previous two IDs.
This Python solution iterates over the input data with an index starting from the third row and checks if the current and the previous two rows have a people count of at least 100. If valid, the rows are then added to the result, ensuring no duplicates using dictionary keys to preserve order.
The time complexity of this approach is O(n), where n is the length of the dataset, as each row is visited once. The space complexity is O(1) for storing temporary variables outside of external list storage.
This approach utilizes a sliding window or similar mechanism to iterate over the rows and assess whether consecutive rows satisfy the conditions.
The solution traverses the list of visits and uses a sliding window approach to check for three or more consecutive days where the number of people in attendance is greater than or equal to 100. If the condition is met, it appends those days to the results list. Finally, the results are deduplicated and sorted by visit date.
Time Complexity: O(n), where n is the number of records in the stadium table.
Space Complexity: O(n) due to the result storage.
This approach employs a segmenting strategy, similar to using SQL WHERE clauses, to filter and then sort the data based on conditions using language-specific features.
The JS solution iterates over the stadium data and counts consecutive entries with more than or equal to 100 people. Once the count reaches three, it gathers these entries into a result list. Finally, the results are sorted based on date before returning.
Time Complexity: O(n log n), primarily due to the sorting operation.
Space Complexity: O(n) as it stores the results list.
| Approach | Complexity |
|---|---|
| Using SQL Window Functions | The time complexity of this query is O(n), where n is the number of rows because each row is processed once. The space complexity is also O(n) due to the use of window functions. |
| Iterative Comparison | The time complexity of this approach is O(n), where n is the length of the dataset, as each row is visited once. The space complexity is O(1) for storing temporary variables outside of external list storage. |
| Approach 1: Sliding Window Method | Time Complexity: O(n), where n is the number of records in the stadium table. |
| Approach 2: SQL-like Filter and Sort Strategy | Time Complexity: O(n log n), primarily due to the sorting operation. |
Leetcode Hard SQL Problem | Human Traffic of Stadium • Ankit Bansal • 33,627 views views
Watch 9 more video solutions →Practice Human Traffic of Stadium with our built-in code editor and test cases.
Practice on FleetCode