LeetCode 1308 - Running Total for Different Genders

The problem is asking us to compute cumulative scores for each gender across different days in a competition. The input

leetcodemediumdatabase

LeetCode Problem 1308

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem is asking us to compute cumulative scores for each gender across different days in a competition. The input is a table Scores with columns player_name, gender, day, and score_points. Each row represents a player’s score on a specific day. The primary key is the combination (gender, day), meaning each gender has unique entries for each day.

The expected output is a table that, for each gender, lists each day in chronological order along with the cumulative total score for that gender up to that day. Ordering is important: the results must first be grouped by gender and then ordered by day ascending.

Constraints and implications: there are no gaps in days for the scoring table; the dataset may have multiple players scoring on the same day. Edge cases include single-entry genders, multiple players on the same day, and days with zero additional scores.

Approaches

Brute Force

A naive approach would be to first group all rows by gender, then for each gender, sort the days, and finally iterate through the sorted days to compute cumulative totals. This would involve multiple passes over the data: one for grouping, one for sorting, and another for summing. While correct, it could be inefficient if the table has many entries because repeated aggregation and sorting are expensive.

Optimal

The key insight is that SQL provides window functions to handle running totals efficiently. By first aggregating scores per day and per gender and then using the SUM() window function with PARTITION BY gender ORDER BY day we can compute cumulative totals in a single pass. This approach avoids explicit iterative summing in application code and leverages the database engine for optimization.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Group by gender, sort by day, iterate to compute cumulative totals
Optimal O(n log n) O(n) Aggregate per day per gender, then use window function SUM over partitioned rows

Algorithm Walkthrough

  1. Aggregate Daily Scores: Group the Scores table by gender and day to sum up all individual score_points for players on the same day. This ensures that multiple scores on the same day are combined into one value.
  2. Compute Running Total: Use a window function SUM(score_points) OVER (PARTITION BY gender ORDER BY day) to calculate the cumulative score for each gender. This maintains an invariant: the cumulative sum at each day equals the sum of all previous daily totals for that gender.
  3. Order Results: Finally, sort the results by gender and day in ascending order to satisfy the output requirements.

Why it works: Aggregating first prevents double-counting, and using a window function ensures that cumulative totals respect both gender and chronological order. This guarantees correctness while leveraging database efficiency.

Python Solution

import sqlite3
from typing import List, Tuple

def running_total_scores() -> List[Tuple[str, str, int]]:
    conn = sqlite3.connect(':memory:')
    cursor = conn.cursor()
    
    cursor.execute('''
        CREATE TABLE Scores (
            player_name TEXT,
            gender TEXT,
            day DATE,
            score_points INTEGER
        )
    ''')
    
    # Assuming table is populated beforehand
    
    cursor.execute('''
        WITH DailyTotals AS (
            SELECT gender, day, SUM(score_points) AS total_points
            FROM Scores
            GROUP BY gender, day
        )
        SELECT gender, day,
               SUM(total_points) OVER (PARTITION BY gender ORDER BY day) AS total
        FROM DailyTotals
        ORDER BY gender, day
    ''')
    
    result = cursor.fetchall()
    conn.close()
    return result

The implementation first creates the table for demonstration purposes and assumes the table is populated. It uses a Common Table Expression (CTE) DailyTotals to aggregate scores per gender per day. Then, a window function SUM() OVER (PARTITION BY gender ORDER BY day) calculates the running total for each gender in chronological order.

Go Solution

package main

import (
    "database/sql"
    _ "github.com/mattn/go-sqlite3"
    "fmt"
)

func runningTotalScores(db *sql.DB) ([][3]interface{}, error) {
    query := `
        WITH DailyTotals AS (
            SELECT gender, day, SUM(score_points) AS total_points
            FROM Scores
            GROUP BY gender, day
        )
        SELECT gender, day,
               SUM(total_points) OVER (PARTITION BY gender ORDER BY day) AS total
        FROM DailyTotals
        ORDER BY gender, day;
    `
    
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()
    
    var results [][3]interface{}
    for rows.Next() {
        var gender string
        var day string
        var total int
        if err := rows.Scan(&gender, &day, &total); err != nil {
            return nil, err
        }
        results = append(results, [3]interface{}{gender, day, total})
    }
    return results, nil
}

func main() {
    db, _ := sql.Open("sqlite3", ":memory:")
    defer db.Close()
    // Assume Scores table is populated
    results, _ := runningTotalScores(db)
    fmt.Println(results)
}

In Go, we query the database with the same CTE and window function logic. The difference is handling sql.Rows and scanning into variables. Go requires explicit error handling for database operations.

Worked Examples

Using the problem’s example:

For female scores:

Day Score Points Cumulative Total
2019-12-30 17 17
2019-12-31 23 40
2020-01-01 17 57
2020-01-07 23 80

For male scores:

Day Score Points Cumulative Total
2019-12-18 2 2
2019-12-25 11 13
2019-12-30 13 26
2019-12-31 3 29
2020-01-07 7 36

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Grouping and sorting operations dominate runtime
Space O(n) Storing aggregated daily totals and window function results

Grouping per day and gender reduces the number of rows processed by the window function, optimizing both memory and computation.

Test Cases

# test cases
# Example from problem
assert running_total_scores() == [
    ('F','2019-12-30',17),
    ('F','2019-12-31',40),
    ('F','2020-01-01',57),
    ('F','2020-01-07',80),
    ('M','2019-12-18',2),
    ('M','2019-12-25',13),
    ('M','2019-12-30',26),
    ('M','2019-12-31',29),
    ('M','2020-01-07',36)
]  # verifies correct cumulative totals

# Single entry per gender
# Scores table: [('Alice','F','2020-01-01',10),('Bob','M','2020-01-01',5)]
# Expected: [('F','2020-01-01',10),('M','2020-01-01',5)]

# Multiple players on same day
# Scores table: [('Alice','F','2020-01-01',10),('Anya','F','2020-01-01',15)]
# Expected: [('F','2020-01-01',25)]
Test Why
Problem example Validates multiple days, multiple players, and correct cumulative totals
Single entry per gender Edge case with minimum data
Multiple players same day Checks aggregation logic

Edge Cases

Single Gender: If all rows belong to one gender, the algorithm still computes running totals correctly since the window function partitions by gender and simply ignores missing partitions.

Multiple Entries Same Day: Multiple players scoring on the same day must be summed before computing running totals. Aggregation ensures no double-counting occurs.

Non-consecutive Days: If days are non-consecutive, the cumulative sum still works since the running total is ordered by day and does not assume continuous dates. Missing days simply do not appear in the output, which matches the problem requirements.