Game Play Analysis III - Solution & Explanation
Problem Statement
Table: Activity
+--------------+---------+ | Column Name | Type | +--------------+---------+ | player_id | int | | device_id | int | | event_date | date | | games_played | int | +--------------+---------+ (player_id, event_date) is the primary key (column with unique values) of this table. This table shows the activity of players of some games. Each row is a record of a player who logged in and played a number of games (possibly 0) before logging out on someday using some device.
Write a solution to report for each player and date, how many games played so far by the player. That is, the total number of games played by the player until that date. Check the example for clarity.
Return the result table in any order.
The result format is in the following example.
Example 1:
Input: Activity table: +-----------+-----------+------------+--------------+ | player_id | device_id | event_date | games_played | +-----------+-----------+------------+--------------+ | 1 | 2 | 2016-03-01 | 5 | | 1 | 2 | 2016-05-02 | 6 | | 1 | 3 | 2017-06-25 | 1 | | 3 | 1 | 2016-03-02 | 0 | | 3 | 4 | 2018-07-03 | 5 | +-----------+-----------+------------+--------------+ Output: +-----------+------------+---------------------+ | player_id | event_date | games_played_so_far | +-----------+------------+---------------------+ | 1 | 2016-03-01 | 5 | | 1 | 2016-05-02 | 11 | | 1 | 2017-06-25 | 12 | | 3 | 2016-03-02 | 0 | | 3 | 2018-07-03 | 5 | +-----------+------------+---------------------+ Explanation: For the player with id 1, 5 + 6 = 11 games played by 2016-05-02, and 5 + 6 + 1 = 12 games played by 2017-06-25. For the player with id 3, 0 + 5 = 5 games played by 2018-07-03. Note that for each player we only care about the days when the player logged in.
Approach Overview
Problem Overview: The Activity table records how many games each player plays on a given date. For every row, return the cumulative number of games played by that player up to that date. The result must include player_id, event_date, and the running total of games.
Approach 1: Correlated Subquery (Default Approach) (Time: O(n^2), Space: O(1))
This approach calculates the cumulative total using a correlated subquery. For each row in the table, run a subquery that sums games_played for the same player_id where event_date is less than or equal to the current row’s date. The database repeatedly scans matching rows to compute the running total. The logic is simple and mirrors how you would compute prefix sums manually, but it performs poorly on large datasets because each row triggers another aggregation.
Approach 2: Self Join + Group By (Time: O(n^2), Space: O(n))
Join the Activity table with itself on matching player_id values where the joined row’s event_date is less than or equal to the base row’s date. After the join, aggregate with SUM(games_played) and group by player_id and event_date. Each row effectively gathers all earlier rows for the same player before computing the total. This technique avoids correlated subqueries and works in older SQL engines that lack window functions, but the join size can grow quickly as the dataset increases.
Approach 3: Window Function (Optimal) (Time: O(n log n), Space: O(n))
The optimal solution uses a window function with SUM(games_played) OVER (PARTITION BY player_id ORDER BY event_date). The PARTITION BY clause groups rows by player, and the ORDER BY clause processes rows chronologically within each player’s partition. The database engine computes a running sum as it scans the ordered rows, eliminating repeated joins or subqueries. This approach is concise, efficient, and the standard way to compute cumulative metrics in modern SQL systems. Window functions are commonly used for analytics queries involving running totals, rankings, or moving averages.
Understanding window functions is critical for solving advanced problems in SQL and database interviews. The same pattern appears in financial reporting, event tracking, and analytics dashboards. If you frequently work with cumulative calculations, mastering window functions significantly simplifies query design.
Recommended for interviews: The window function approach is the expected solution. It demonstrates strong SQL fundamentals and familiarity with analytical queries. Mentioning the self-join or correlated subquery approach first can show you understand how cumulative totals work conceptually, but the window function shows practical SQL expertise.
Approach 1: Window Function
We can use the window function SUM() OVER() to group by player_id, sort by event_date, and calculate the total number of games played by each user up to the current date.
Code
MySQL
Approach 2: Self-Join + Group By
We can also use a self-join to join the Activity table with itself on the condition of t1.player_id = t2.player_id AND t1.event_date >= t2.event_date, and then group by t1.player_id and t1.event_date, and calculate the cumulative sum of t2.games_played. This will give us the total number of games played by each user up to the current date.
Code
MySQL
Approach 3: Default Approach
Code
MySQL
Complexity Comparison
| Approach | Complexity |
|---|---|
| Window Function | — |
| Self-Join + Group By | — |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Correlated Subquery | O(n^2) | O(1) | Simple logic when window functions are unavailable |
| Self Join + Group By | O(n^2) | O(n) | Works in older SQL versions that lack analytical functions |
| Window Function (SUM OVER) | O(n log n) | O(n) | Best approach for running totals and analytical queries |
Video Solution
LeetCode 534: Game Play Analysis III [SQL] • Frederik Müller • 6,156 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Game Play Analysis III easy or hard?
How to solve Game Play Analysis III in O(n)?
Game Play Analysis III Python or Java solution?
What is the best approach for Game Play Analysis III?
What is the time complexity of Game Play Analysis III?
Is Game Play Analysis III asked at Google, Amazon, or Meta?
What data structure or SQL feature is used in Game Play Analysis III?
Ready to solve this problem?
Practice Game Play Analysis III with our built-in code editor and test cases.
Practice on FleetCode