LeetCode 3709 - Design Exam Scores Tracker

This problem asks us to design a system that tracks Alice's exam scores over time and efficiently computes the total score for any given time interval.

leetcodemediumarraybinary-searchdesignprefix-sum

LeetCode Problem 3709

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Design, Prefix Sum

Solution

Problem Understanding

This problem asks us to design a system that tracks Alice's exam scores over time and efficiently computes the total score for any given time interval. The system must support two operations: recording a new exam with a timestamp and score, and querying the total score of exams between two timestamps inclusive.

The input consists of a series of function calls, starting with ExamTracker() to initialize the tracker, followed by record(time, score) calls, which are guaranteed to have strictly increasing times. This guarantee allows us to maintain the scores in chronological order without needing to reorder them later. The totalScore(startTime, endTime) query can only ask about past or present exams, never future exams, ensuring that no lookahead is needed.

The constraints indicate that times and scores can be as large as $10^9$, and the number of operations can reach $10^5$. Therefore, a naive solution that scans all recorded exams for each query could be too slow for large inputs.

Key edge cases include querying intervals where no exams exist, querying intervals that cover only one exam, or intervals that start or end at the exact recorded exam times.

Approaches

The brute-force approach is straightforward: for each totalScore(startTime, endTime) query, iterate over all recorded exams, sum the scores of exams that fall within the interval, and return the sum. While this is correct, it can take $O(n)$ time per query, which is too slow for $10^5$ operations.

The optimal approach leverages the fact that exam times are strictly increasing. By maintaining two parallel arrays-one for exam times and another for the prefix sum of scores-we can answer total score queries using binary search. Specifically, we locate the first exam at or after startTime and the last exam at or before endTime using bisect_left and bisect_right. The total score is then obtained by subtracting prefix sums, which is an $O(\log n)$ operation per query instead of $O(n)$.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per query O(n) Scans all exams for each query, slow for many queries
Optimal O(log n) per query O(n) Uses prefix sum and binary search on sorted times

Algorithm Walkthrough

  1. Initialize two empty lists: times for storing exam times in chronological order, and prefix_sums for storing cumulative scores.

  2. On each record(time, score) call, append the time to times and append score + last_prefix_sum to prefix_sums to maintain the running total.

  3. On each totalScore(startTime, endTime) query:

  4. Use binary search to find the index l of the first exam at or after startTime.

  5. Use binary search to find the index r of the last exam at or before endTime.

  6. If l > r, return 0 because no exams exist in the interval.

  7. Otherwise, return prefix_sums[r] - prefix_sums[l-1] if l > 0, or prefix_sums[r] if l == 0.

  8. Return the computed total score.

Why it works: By maintaining the times in a sorted array and using prefix sums, we ensure that every query can quickly compute the sum of scores in a given range. Binary search guarantees that the start and end indices of the range are found efficiently. The running total in prefix_sums guarantees that summation is constant-time once indices are known.

Python Solution

from bisect import bisect_left, bisect_right

class ExamTracker:

    def __init__(self):
        self.times = []
        self.prefix_sums = []

    def record(self, time: int, score: int) -> None:
        self.times.append(time)
        if self.prefix_sums:
            self.prefix_sums.append(self.prefix_sums[-1] + score)
        else:
            self.prefix_sums.append(score)

    def totalScore(self, startTime: int, endTime: int) -> int:
        l = bisect_left(self.times, startTime)
        r = bisect_right(self.times, endTime) - 1
        if l > r:
            return 0
        return self.prefix_sums[r] - (self.prefix_sums[l-1] if l > 0 else 0)

Explanation: The record function appends the time and updates the cumulative sum in prefix_sums. The totalScore function uses bisect_left and bisect_right to locate the range of relevant exams and computes the total efficiently using the prefix sums.

Go Solution

import "sort"

type ExamTracker struct {
    times       []int
    prefixSums  []int64
}

func Constructor() ExamTracker {
    return ExamTracker{
        times:      []int{},
        prefixSums: []int64{},
    }
}

func (this *ExamTracker) Record(time int, score int)  {
    this.times = append(this.times, time)
    if len(this.prefixSums) == 0 {
        this.prefixSums = append(this.prefixSums, int64(score))
    } else {
        this.prefixSums = append(this.prefixSums, this.prefixSums[len(this.prefixSums)-1] + int64(score))
    }
}

func (this *ExamTracker) TotalScore(startTime int, endTime int) int64 {
    l := sort.Search(len(this.times), func(i int) bool { return this.times[i] >= startTime })
    r := sort.Search(len(this.times), func(i int) bool { return this.times[i] > endTime }) - 1
    if l > r {
        return 0
    }
    if l == 0 {
        return this.prefixSums[r]
    }
    return this.prefixSums[r] - this.prefixSums[l-1]
}

Explanation: Go uses slices for dynamic arrays and sort.Search for binary search. The logic mirrors the Python solution, with explicit handling of int64 for cumulative sums to avoid integer overflow.

Worked Examples

Example trace for input:

["ExamTracker", "record", "totalScore", "record", "totalScore", "totalScore", "totalScore", "totalScore"]
[[], [1, 98], [1, 1], [5, 99], [1, 3], [1, 5], [3, 4], [2, 5]]
Step times prefix_sums Query Computation Result
record(1,98) [1] [98] - - -
totalScore(1,1) [1] [98] l=0, r=0 98-0 98
record(5,99) [1,5] [98,197] - - -
totalScore(1,3) [1,5] [98,197] l=0, r=0 98-0 98
totalScore(1,5) [1,5] [98,197] l=0, r=1 197-0 197
totalScore(3,4) [1,5] [98,197] l=1, r=0 l>r 0
totalScore(2,5) [1,5] [98,197] l=1, r=1 197-98 99

Complexity Analysis

Measure Complexity Explanation
Time O(log n) per query, O(1) per record Binary search on sorted times for queries; appending is O(1)
Space O(n) Storing times and prefix sums for all recorded exams

The algorithm is efficient because each query only involves two binary searches and a subtraction, avoiding a full scan of the exams.

Test Cases

# provided example
obj = ExamTracker()
obj.record(1, 98)
assert obj.totalScore(1, 1) == 98
obj.record(5, 99)
assert obj.totalScore(1, 3) == 98
assert obj.totalScore(1, 5) == 197
assert obj.totalScore(3, 4) == 0
assert obj.totalScore(2, 5) == 99

# boundary tests
obj = ExamTracker()
obj.record(1, 1)
assert obj.totalScore(1, 1) == 1  # only one exam
obj.record(2, 2)
assert obj.totalScore(1, 2) == 3  # sum of two exams
assert obj.totalScore(3, 3) == 0  # no exams in range

# large values
obj = ExamTracker()
obj.record(1_000_000_000, 1_000_000_000)
assert obj.totalScore(1_000_000_000, 1_000_000_000) == 1_000_000_000
Test Why
Provided example Validates correctness across multiple records and queries