[Python] Why Is My Leaderboard Showing Incorrect Ranks for Tied Scores(Python)?

I’m implementing a game leaderboard in Python where players can have the same score (ties), and I need to support three operations efficiently: • add_score player_id score — update a player’s score (ignore if the new score is not higher than the current) • get_rank player_id — return the rank of the player (rank 1 is the highest score) • get_score_by_rank rank — return the score of the player(s) at a given rank (ties should share the same rank)

For example, this sequence should work as follows:

<< in
add_score 1 100
get_rank 1
add_score 1 120
get_rank 1
add_score 2 100
get_rank 1
get_rank 2
get_score_by_rank 1

>> out
1
1
1
1
2
1
2
120


I’m using an AVL tree to efficiently support these operations. After several updates, my leaderboard sometimes outputs ranks like:

115,11253,1875
116,2199,1869
116,11972,1869
118,717,1863
118,3432,1863
121,783,1859
122,11760,1852


But I expect ranks like 118, 118, 120 for tied scores, instead of 118, 118, 121. That is, all players with the same score should get the same rank, and the next rank should be increased by the number of players with the previous score.

Interestingly, in some shorter sections, the leaderboard does seem to work as intended. For example, sometimes I get output like 116, 116, 118 for tied scores, which is correct. However, at other times, it jumps incorrectly, such as 118, 118, 121 instead of 118, 118, 120. So, sometimes the ranking for ties works as expected, but in other places it is off by one or more.

I’ve implemented an AVL tree-based leaderboard (see code below) to support efficient ranking and tie handling. I expect that when multiple players have the same score, they all get the same rank, and the next rank skips ahead by the number of tied players. However, in my implementation, the ranks sometimes increase by one per player, even when they have the same score, causing the rank numbers to be off by one or more.

I tried debugging my get_rank function and the AVL update logic, but I can’t pinpoint exactly where the off-by-one error for tied scores comes from.

Any advice or pointers on what to check, or how to structure my get_rank logic for correct tie handling?

import sys

class AVLNode:
def __init__(self, score):
self.score = score
self.players = set()
self.count = 0
self.height = 1
self.left = None
self.right = None
self.total = 0

class AVLTree:
def __init__(self):
self.root = None

def _height(self, node):
return node.height if node else 0

def _update(self, node):
if not node:
return
node.height = 1 + max(self._height(node.left), self._height(node.right))
left_total = node.left.total if node.left else 0
right_total = node.right.total if node.right else 0
node.total = left_total + right_total + node.count

def _balance_factor(self, node):
return self._height(node.left) - self._height(node.right)

def _rotate_left(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
self._update(z)
self._update(y)
return y

def _rotate_right(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
self._update(z)
self._update(y)
return y

def _balance(self, node):
if not node:
return node
balance = self._balance_factor(node)
if balance > 1:
if self._balance_factor(node.left) < 0:
node.left = self._rotate_left(node.left)
return self._rotate_right(node)
if balance < -1:
if self._balance_factor(node.right) > 0:
node.right = self._rotate_right(node.right)
return self._rotate_left(node)
return node

def _insert(self, node, score, player_id):
if not node:
new_node = AVLNode(score)
new_node.players.add(player_id)
new_node.count = 1
new_node.total = 1
return new_node

if score > node.score:
node.left = self._insert(node.left, score, player_id)
elif score < node.score:
node.right = self._insert(node.right, score, player_id)
else:
if player_id not in node.players:
node.players.add(player_id)
node.count += 1
node.total += 1
return node

self._update(node)
return self._balance(node)

def _remove(self, node, score, player_id):
if not node:
return None

if score > node.score:
node.left = self._remove(node.left, score, player_id)
elif score < node.score:
node.right = self._remove(node.right, score, player_id)
else:
if player_id in node.players:
node.players.remove(player_id)
node.count -= 1
node.total -= 1
if node.count > 0:
self._update(node)
return self._balance(node)
if not node.left:
return node.right
elif not node.right:
return node.left
temp = self._min_value_node(node.right)
node.score = temp.score
node.players = set(temp.players)
node.count = temp.count
node.right = self._remove(node.right, temp.score, next(iter(temp.players)))
self._update(node)
return self._balance(node)

def _min_value_node(self, node):
current = node
while current.left:
current = current.left
return current

class Leaderboard:
def __init__(self):
self.player_scores = {}
self.tree = AVLTree()

def add_score(self, player_id, new_score):
if player_id in self.player_scores:
old_score = self.player_scores[player_id]
if new_score <= old_score:
return self.get_rank(player_id)
self.tree.root = self.tree._remove(self.tree.root, old_score, player_id)
self.tree.root = self.tree._insert(self.tree.root, new_score, player_id)
self.player_scores[player_id] = new_score
return self.get_rank(player_id)

def get_rank(self, player_id):
score = self.player_scores.get(player_id)
if score is None:
return -1
higher_count = 0
current = self.tree.root
while current:
if score < current.score:
left_total = current.left.total if current.left else 0
higher_count += left_total + current.count
current = current.right
elif score > current.score:
current = current.left
else:
left_total = current.left.total if current.left else 0
higher_count += left_total
break
return higher_count + 1

def get_score_by_rank(self, rank):
if rank < 1 or not self.tree.root or rank > self.tree.root.total:
return -1
current = self.tree.root
count = 0
while current:
left_total = current.left.total if current.left else 0
if count + left_total >= rank:
current = current.left
elif count + left_total + current.count < rank:
count += left_total + current.count
current = current.right
else:
return current.score
return -1

if __name__ == '__main__':
leaderboard = Leaderboard()
outputs = []
for line in sys.stdin:
line = line.strip()
if not line:
continue
parts = line.split()
cmd = parts[0]
if cmd == 'add_score':
player_id = int(parts[1])
score = int(parts[2])
outputs.append(str(leaderboard.add_score(player_id, score)))
elif cmd == 'get_rank':
player_id = int(parts[1])
outputs.append(str(leaderboard.get_rank(player_id)))
elif cmd == 'get_score_by_rank':
rank = int(parts[1])
outputs.append(str(leaderboard.get_score_by_rank(rank)))
print('\n'.join(outputs))

Continue reading...