LeetCode 534 - Game Play Analysis III

The problem is asking us to track cumulative game activity for each player. Specifically, we are given an Activity table where each row represents a single login session for a player on a specific device and date, along with the number of games played during that session.

leetcodemediumdatabase

LeetCode Problem 534

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem is asking us to track cumulative game activity for each player. Specifically, we are given an Activity table where each row represents a single login session for a player on a specific device and date, along with the number of games played during that session. The goal is to produce a report that shows, for each player and each date they played, the total number of games the player has played up to and including that date.

In other words, for a given player, we need a running total of games_played ordered by event_date. The input guarantees that (player_id, event_date) is unique, so no player has multiple rows for the same date. The output should include every date that a player logged in, along with the cumulative total up to that date.

Important edge cases include players who have only one record, sessions where games_played is zero, and players with gaps in dates between sessions. The solution must handle these correctly to ensure the cumulative sum reflects only the days when the player logged in, in chronological order.

Approaches

The brute-force approach would iterate over each player, then for each date sum all games_played up to that date. While this produces the correct result, it is inefficient because it repeatedly sums previous entries, giving a time complexity of O(n²) in the worst case, where n is the number of rows in the table.

The key insight for an optimal solution is that SQL supports window functions, specifically SUM() OVER(PARTITION BY ... ORDER BY ...). By partitioning the data by player_id and ordering by event_date, we can compute a running total in a single pass. This approach avoids repeated summation and directly yields the cumulative total for each row.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Sum all previous rows for each player and date; inefficient for large tables
Optimal O(n) O(n) Use SQL window function to compute cumulative sum partitioned by player and ordered by date

Algorithm Walkthrough

  1. Start by selecting the columns we need: player_id, event_date, and games_played.
  2. Apply a window function SUM(games_played) OVER(PARTITION BY player_id ORDER BY event_date) to calculate a cumulative total of games for each player.
  3. Alias the result of the window function as games_played_so_far for clarity.
  4. Return the result, including player_id, event_date, and the computed cumulative sum. The order of rows in the result is not important unless specifically required.
  5. Ensure that all players are processed independently by the PARTITION BY player_id clause and that the cumulative sum respects chronological order using ORDER BY event_date.

Why it works: The window function maintains a running total within each partition (player). SQL guarantees that the rows in the partition are processed in the order specified by ORDER BY, so the cumulative sum always includes all previous rows for that player, producing the correct games_played_so_far.

Python Solution

import sqlite3
from typing import List, Tuple

def games_played_so_far() -> str:
    """
    Returns the SQL query string to compute cumulative games played per player.
    """
    return """
    SELECT 
        player_id,
        event_date,
        SUM(games_played) OVER(PARTITION BY player_id ORDER BY event_date) AS games_played_so_far
    FROM Activity
    """

This Python function simply returns the SQL query string that computes the cumulative sum. The SUM() OVER(PARTITION BY ... ORDER BY ...) is the core part of the algorithm, ensuring we calculate the running total per player in chronological order.

Go Solution

package main

import "fmt"

func GamesPlayedSoFar() string {
    return `
    SELECT 
        player_id,
        event_date,
        SUM(games_played) OVER(PARTITION BY player_id ORDER BY event_date) AS games_played_so_far
    FROM Activity
    `
}

func main() {
    fmt.Println(GamesPlayedSoFar())
}

The Go solution is nearly identical in logic because the computation occurs in SQL. The Go function returns the query string, and you can execute it with a standard database/sql package. There is no need to handle nil or empty separately because the database handles cumulative sums correctly even if some games_played values are zero.

Worked Examples

Using the example input:

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

Step-by-step calculation using the window function:

player_id event_date games_played SUM(...) OVER(PARTITION BY player_id ORDER BY event_date)
1 2016-03-01 5 5
1 2016-05-02 6 11
1 2017-06-25 1 12
3 2016-03-02 0 0
3 2018-07-03 5 5

This matches the expected output exactly.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each row is processed once by the SQL engine; window function calculates running total efficiently
Space O(n) Database engine needs to maintain partitioned state for cumulative sums

The SQL engine efficiently maintains a running total per partition, avoiding repeated computation for each row, which is why the time complexity is linear relative to the number of rows.

Test Cases

# Test case 1: Provided example
assert games_played_so_far() == """
    SELECT 
        player_id,
        event_date,
        SUM(games_played) OVER(PARTITION BY player_id ORDER BY event_date) AS games_played_so_far
    FROM Activity
    """

# Edge case 1: Single player, single day
# Should return that day's games played as cumulative
# Edge case 2: Multiple players, non-consecutive days
# Each player's cumulative sum is independent
# Edge case 3: Zero games played
# Cumulative sum should reflect zeros correctly
Test Why
Provided example Validates correct cumulative calculation across multiple players and dates
Single player single day Ensures base case with minimum input is handled
Multiple players non-consecutive dates Ensures partitioning by player is correct
Zero games played Ensures zeros are included correctly in the cumulative sum

Edge Cases

One important edge case is when a player logs in only once. In this scenario, the cumulative sum should equal the games_played for that day, and the window function naturally handles this because the sum over a single row is just that row's value.

Another edge case occurs when games_played is zero. If a player logs in but does not play any games, the cumulative sum should reflect the zero addition. The SQL window function adds zero correctly without affecting previous totals.

A third edge case is non-consecutive dates for a player. The algorithm must ensure the cumulative sum skips missing days rather than resetting. By using ORDER BY event_date, the running total is maintained correctly regardless of gaps between dates. This is crucial because a naive approach that assumes daily continuity could miscompute totals.