Problem overview
A game shows each player two numbers: the total of all their turns and their best single turn. ScoreKeeper keeps both up to date as points come in. add(points) records one turn, total() and best() report the numbers, and reset() starts over. Before any add, both numbers are 0.
After add(10), add(25) and add(5), the total is 40 and the best is 25. After a reset(), both are 0 again, and the earlier 25 no longer counts as the best.
Approach
The keeper doesn't need to remember the turns themselves. Two numbers are enough: the running total and the best turn so far. Each add updates both in constant time, so total() and best() never look back at old turns. Starting best at 0 is safe because points are never negative.
Storing every turn in a list would also work: total() would add the list up and best() would scan it for the largest value. But then each call costs time proportional to the number of turns, and the keeper's memory grows with every add. Keeping two running numbers gives the same answers with neither cost.
Step by step
- Declare
totalPointswith an initial value of 0. A field can start with a value, like a variable, so every new keeper begins at 0 and the class needs no constructor. - Declare
bestPointsthe same way. The fields have names that differ from the methodstotal()andbest(), so nothing is ambiguous. - In
add, add the points to the total with+=. - Update the best only when the new turn beats it. It is the same idea as finding the largest value in a list, one value at a time. An equal score changes nothing.
totalandbestonly report the fields.addalready did the work.resetsets both fields back to 0, the values a new keeper starts with.
The solution in Java
class ScoreKeeper {
public int totalPoints = 0;
public int bestPoints = 0;
public void add(int points) {
totalPoints += points;
if (points > bestPoints) {
bestPoints = points;
}
}
public int total() {
return totalPoints;
}
public int best() {
return bestPoints;
}
public void reset() {
totalPoints = 0;
bestPoints = 0;
}
}
The class has no constructor, so Java supplies a default one that takes no arguments, and new ScoreKeeper() works. The field initializers = 0 run each time an object is created.
Using the class
ScoreKeeper k = new ScoreKeeper();
k.add(30);
k.add(50);
System.out.println(k.total() + " " + k.best());
k.reset();
System.out.println(k.total() + " " + k.best());
k.add(20);
System.out.println(k.best() + " " + k.total());
ScoreKeeper fresh = new ScoreKeeper();
System.out.println(fresh.best() + " " + fresh.total());
prints:
80 50
0 0
20 20
0 0
After the reset, add(20) makes the best 20, not 50: the 50 belonged to the earlier session.
Tracing the state
The two fields are the keeper's whole memory. Here is how they change for add(30), add(50), reset() and add(20):
| Call | totalPoints | bestPoints |
|---|---|---|
| new keeper | 0 | 0 |
add(30) | 30 | 30 |
add(50) | 80 | 50 |
reset() | 0 | 0 |
add(20) | 20 | 20 |
Each row depends only on the row above it and the new points, which is why the keeper never needs the list of earlier turns.
Special cases
- No add yet.
total()andbest()return 0, because both fields start at 0. - A turn worth 0.
add(0)changes neither number. The total grows by 0, and 0 is not greater than the best. - Equal scores. If the new points equal the best, the comparison
points > bestPointsis false and the best stays the same, which is the same number anyway. - Reset twice in a row. It does no harm: both fields are already 0.
Two keepers at once
Each new ScoreKeeper() has its own two fields, so two players can be tracked side by side:
ScoreKeeper s1 = new ScoreKeeper();
ScoreKeeper s2 = new ScoreKeeper();
s1.add(10);
s1.add(25);
s1.add(5);
s2.add(7);
System.out.println(s1.total() + " " + s1.best());
System.out.println(s2.total() + " " + s2.best());
s2.add(0);
System.out.println(s2.total() + " " + s2.best());
prints:
40 25
7 7
7 7
Adding to s1 never changes s2, and a turn worth 0 leaves s2 as it was.
Complexity
Every method does a fixed number of operations, so each is O(1) time, and the keeper uses O(1) space however many turns it sees.
What a partial reset does
Suppose reset clears only the total:
public void reset() {
totalPoints = 0;
}
Then after add(50), reset() and add(20), the total is 20 but the best is still 50. The fields are two halves of one state, and any method that starts over must put both back. The rule to remember is that reset restores exactly the values a new keeper starts with, so afterwards the object behaves as if it had just been created.
The same thinking applies if you add a field later, for example a count of turns: add must update it and reset must clear it.
Common mistakes
- Not resetting
bestPoints. Ifresetonly clears the total, the old best survives. - Setting the best to the latest points without comparing. The best would then just be the last turn.
- Giving a field the same name as a method. Java allows a field and a method called
total, but it is confusing to read, which is why the fields are calledtotalPointsandbestPoints. - Starting the best at a large negative number is unnecessary here. 0 is right because the points are at least 0 and an empty keeper must report 0.
