Who's on top this week?
Sikau wants a weekly XP leaderboard: a ranked list with fair handling of ties, plus a fast "what rank would this score be?" for thousands of lookups. Sort once, then binary search.
Sort once, query many times
Leaderboards appear in games, learning apps and sales dashboards, and they all need the same two things: a fair ranking and fast lookups.
The leaderboard is read far more often than it changes, so do the expensive work once. Sort entries by XP (highest first, names alphabetically for ties) when the leaderboard is built. Every top(n) is then a slice, and every "what rank would this score get?" is a binary search instead of a scan.
- Constructor: copy and sort — O(n log n) once.
- top(n): slice and format — O(n) for the slice only.
- rankOf(xp): binary search over the sorted XP values — O(log n).
- Many queries: O(n log n + q log n) instead of O(q·n).
Keep a separate ascending array of XP values if that makes the binary search simpler; it costs one extra pass.