Skip to content
Tutorials Center
My learning

Topics

Lesson 217 of 225 ยท Projects

Project: Real-time Leaderboard

Build a game leaderboard in stages. Compare a dict with sorting, a bisect-sorted list and a Fenwick tree for fast ranks, top-k queries and live updates.

Every online game, coding contest and fitness app has a leaderboard. It looks simple: a list of names with scores, best at the top. But a real leaderboard has to answer questions while the scores keep changing: "What are the top 10 right now?", "What rank am I?", "Who is just above and below me?". Ask those a thousand times a second with a million players and the obvious solution stops being good enough.

In this project you build a leaderboard in stages. You begin with a plain dictionary and sorting, move to a list kept in order with binary search (bisect), then switch to a Fenwick tree whose rank queries do not depend on the number of players at all. You finish with a differential test and a heap-based high-score table. All code is complete and runs in your browser.

The specification

A leaderboard stores one integer score per player. Higher is better.

  • set_score(player, score) creates or replaces a player's score.
  • remove(player) deletes a player (for example a banned cheater).
  • rank(player) returns the player's rank. Players with equal scores share a rank and the next rank is skipped, like 1, 2, 2, 4 in sports. This is called competition ranking.
  • top(k) returns the k best (player, score) pairs, ordered by score descending, then by name ascending so output is deterministic.
TEXT
player   score   rank
fatima    150     1
alice     120     2     <- tied, so both are 2
cara      120     2
bob        95     4     <- rank 3 is skipped

Stage 1: a dictionary and sorting

The first version stores player -> score in a dict. Updates are O(1). For a rank we count how many scores are strictly greater, and for the top list we sort everything:

Python Stage 1: dict plus sorting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Correct, simple, and a good reference for later tests. The costs show the problem: rank scans all N players, so it is O(N), and top(k) with a full sort is O(N log N). The heap version, heapq.nsmallest, brings that to O(N log k), which is better for small k but still looks at every player on every call. A leaderboard is read far more often than it is written, so we want to pay at update time and make queries cheap.

Stage 2: keep the players sorted with bisect

Instead of sorting on every query, keep a list of (-score, name) pairs always in sorted order. Negating the score makes the best player sort first and gives the tie-break by name for free, because Python compares tuples element by element:

TEXT
order = [(-150, "fatima"), (-120, "alice"), (-120, "cara"),
         (-95, "bob"), (-95, "eli"), (-95, "hana"), (-70, "dmitri"), (-70, "gus")]
          index 0            1               2         3          4         5          6             7

Now every operation is a binary search:

  • top(k) is a slice, order[:k].
  • rank(player): the number of entries strictly better than (-score, ...) is bisect_left(order, (-score, "")), because the empty string sorts before every name. Add 1 for the rank.
  • set_score: find the old entry with bisect_left, delete it, then insort the new one.
Python Stage 2: a sorted list with bisect

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Queries are now O(log N) for rank, and O(k) for top(k). Updates cost O(log N) to find the position, but del and insort must shift every later list element one place, which is O(N) in theory. In practice that shifting is one fast memory move written in C, so a list of a few hundred thousand players updates comfortably; the dynamic arrays lesson explains why. Tens of millions of players, or thousands of updates per second on a huge board, need something better.

The standard library has no sorted-container type with O(log N) insertion. Outside this tutorial, most Python code reaches for the sortedcontainers package (SortedList), or a balanced tree or skip list in other languages. Redis sorted sets, the usual production answer, use a skip list internally.

Stage 3: a Fenwick tree over the score range

Look at what a rank really is: the number of players with a higher score. That is a counting question, and counting over ranges is what a Fenwick tree (binary indexed tree) does best. If scores are integers in a bounded range (say 0 to 1000), keep an array count[s] = number of players with score s, stored in a Fenwick tree. Then:

TEXT
rank(player)  = 1 + (total players) - (players with score <= my score)
update        = add -1 at the old score, +1 at the new score

Both are prefix operations that touch about log2(M) cells, where M is the size of the score range. The number of players no longer matters. A tiny extra trick, binary lifting on the tree, finds the score of the player at rank r in the same O(log M). Combined with a bucket of names per score, that gives top(k):

Python Stage 3: ranks with a Fenwick tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The Fenwick board has a different set of trade-offs:

  • Fast and independent of N: rank, update and "score at place" are O(log M). A board with ten million players is as quick as one with ten.
  • Bounded integer scores. The tree is indexed by score. If scores are floats or span billions, you would compress them to ranks first, which only works if you know all values up front.
  • Memory is O(M + N): one counter per possible score plus one entry per player.
  • Lists of neighbours ("the players just above me") are awkward, since the tree only holds counts. The buckets help, but the bisect list in Stage 2 is simpler for that feature.

Stage 4: test the three against each other

Three implementations of the same specification are an opportunity: feed them the same random sequence of updates and compare every answer. This is the differential test from the autocomplete project. We use a seeded random generator, so the run is repeatable:

Python Stage 4: random operations on all three boards

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The small score range (0 to 50 for 30 players) is intentional: it creates many ties, which is exactly where ranking code usually breaks. When this test reports 0 disagreements, you have decent evidence that the clever versions match the simple one.

Stage 5: a different board, the all-time high-score table

Some boards never update a player: each game submits a score and the board only keeps the best k submissions ever. That is the top-k pattern, and the right tool is a min-heap of size k. The smallest of the kept scores sits at the root, so a new submission either beats it (replace the root) or is discarded, all in O(log k):

Python Stage 5: top-3 table with a min-heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compare the two designs: the Fenwick and bisect boards answer rank queries for any player; the heap table answers only "who is in the top k" but uses just O(k) memory and never needs to know the full list of players. Choosing between them is the essential skill the choosing structures lesson will practise.

Complexity summary

N = players, M = size of the score range, k = requested top size.

Design update rank top(k) Memory
dict + scan/sort O(1) O(N) O(N log N) (or O(N log k) with a heap) O(N)
sorted list + bisect O(N) shift, tiny constant O(log N) O(k) O(N)
Fenwick tree + buckets O(log M) O(log M) O(k log M) O(M + N)
min-heap of size k O(log k) per submission not supported O(k log k) O(k)

Common mistakes

  • Using rank = position. With ties, the 3rd row of the sorted list is not "rank 3". Decide between competition ranking (1, 2, 2, 4), dense ranking (1, 2, 2, 3) and unique positions, and test ties.
  • Forgetting to delete the old entry when a player's score changes. The stale pair stays in the list and the player appears twice.
  • Searching for the old entry with the new score. The key you delete must be built from the old score.
  • Sorting without a tie-break. Two players with equal scores may swap places between calls.
  • Fenwick indexing off by one. Fenwick trees are 1-indexed, while scores start at 0. Add 1 on the way in.
  • Assuming scores fit the tree. Validate the range, as set_score does above.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is the sorted list from Stage 2 kept as (-score, name) pairs?

    The list sorts ascending, so negating the score puts the highest scores first. Tuple comparison falls through to the name when scores are equal, giving a deterministic order.
  2. 2. What is the time complexity of rank(player) in the Fenwick board, where M is the score range and N the number of players?

    Counting the players with scores up to a value is a Fenwick prefix sum, which touches about log2(M) cells and never looks at individual players.
  3. 3. Four players have scores 100, 90, 90 and 80. With competition ranking, what is the rank of the player with 80?

    Three players have a strictly higher score, so the rank is 3 + 1 = 4. The tied 90s both have rank 2, and rank 3 is skipped.
  4. 4. When is the min-heap of size k the better choice than a sorted list?

    A size-k min-heap keeps just the best k entries and discards the rest in O(log k), but it cannot answer rank or neighbour queries.
  5. 5. What is the main weakness of bisect.insort on a very large list?

    Finding the position takes O(log N) comparisons, but inserting into a Python list moves all later elements, which is O(N) memory movement, though a very fast one.

Summary

  • A leaderboard answers rank, top-k and update queries; the right structure depends on which one dominates and how many players there are.
  • A dict plus sorting is the easy reference: O(N) ranks and O(N log N) top lists.
  • A list kept sorted with bisect gives O(log N) ranks and instant top-k, with O(N) (but fast) shifts on update.
  • A Fenwick tree over a bounded score range makes rank, update and "score at place" O(log M), independent of the number of players.
  • Decide how ties work first (competition ranking here) and test them with many equal scores.
  • A size-k min-heap is the tool for an all-time top-k table over a stream.
  • Keep the simple version around: differential testing against it is the best protection against bugs in the fast one.

Next: Problem Patterns Cheat Sheet