Leaderboard implementation in Redis - Time & Space Complexity

Time Complexity: Leaderboard implementation

O(log n)

Understanding Time Complexity

When we build a leaderboard using Redis, we want to know how fast it can add scores and find rankings as more players join.

We ask: How does the work grow when the number of players grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

ZADD leaderboard 1500 "player1"
ZADD leaderboard 2000 "player2"
ZADD leaderboard 1800 "player3"

ZRANK leaderboard "player2"
ZREVRANGE leaderboard 0 9 WITHSCORES

ZINCRBY leaderboard 100 "player1"

This code adds players with scores, finds a player's rank, lists top players, and updates a player's score.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorted set commands like ZADD, ZRANK, ZREVRANGE, and ZINCRBY that internally manage sorted data.
• How many times: Each command works on the sorted set of all players, which can be large.

How Execution Grows With Input

As the number of players (n) grows, each operation takes more time but not equally.

Input Size (n)	Approx. Operations
10	About 4 x log(10) ≈ 8
100	About 4 x log(100) ≈ 18
1000	About 4 x log(1000) ≈ 28

Pattern observation: The work grows slowly as the number of players grows, roughly increasing with the logarithm of n.

Final Time Complexity

Time Complexity: O(log n)

This means that adding or finding a player's rank takes a little more time as the leaderboard grows, but it grows slowly and stays efficient.

Common Mistake

[X] Wrong: "Adding a new player or updating a score takes the same time no matter how many players there are."

[OK] Correct: Actually, Redis uses a sorted data structure that needs to keep things in order, so it does a bit more work as the list grows, but this extra work grows slowly, not instantly.

Interview Connect

Understanding how Redis handles leaderboards helps you explain how data structures affect speed, a useful skill when discussing real-world systems.

Self-Check

"What if we used a simple list instead of a sorted set for the leaderboard? How would the time complexity change?"

Practice

1. What Redis data structure is best suited for implementing a leaderboard where members have scores?

easy

A. Hash

B. Sorted Set

C. List

D. String

Solution

1. Step 1: Understand leaderboard requirements

   A leaderboard needs to store members with scores and retrieve them sorted by score.

2. Step 2: Identify Redis data structure

   Redis Sorted Sets store members with scores and keep them sorted automatically.

3. Final Answer:

   Sorted Set -> Option B

4. Quick Check:

   Leaderboard = Sorted Set [OK]

Hint: Leaderboards need sorted data, use Sorted Sets [OK]

Common Mistakes:

• Choosing List which is ordered by insertion, not score
• Using Hash which stores key-value but not sorted by score
• Using String which holds plain text, not multiple members

2. Which Redis command correctly adds or updates a member's score in a leaderboard stored as a sorted set?

easy

A. ZADD leaderboard 100 user1

B. ZADD leaderboard user1 100

C. ZINCRBY leaderboard 100 user1

D. ZREM leaderboard user1

Solution

1. Step 1: Recall ZADD syntax

   ZADD command syntax is: ZADD key score member.

2. Step 2: Match syntax to options

   ZADD leaderboard 100 user1 uses ZADD leaderboard 100 user1 which matches the correct syntax.

3. Final Answer:

   ZADD leaderboard 100 user1 -> Option A

4. Quick Check:

   ZADD syntax = ZADD key score member [OK]

Hint: ZADD syntax: key, score, then member [OK]

Common Mistakes:

• Swapping score and member order
• Using ZINCRBY which increments score, not sets it
• Using ZREM which removes member instead of adding

3. Given the following Redis commands executed in order:

ZADD leaderboard 50 user1
ZADD leaderboard 100 user2
ZADD leaderboard 75 user3
ZREVRANGE leaderboard 0 1 WITHSCORES

What is the output of the last command?

medium

A. ["user2", "100", "user3", "75"]

B. ["user1", "50", "user3", "75"]

C. ["user3", "75", "user2", "100"]

D. ["user2", "100", "user1", "50"]

Solution

1. Step 1: Add members with scores

   user1=50, user2=100, user3=75 added to sorted set.

2. Step 2: Use ZREVRANGE 0 1 WITHSCORES

   This fetches top 2 members by highest score descending: user2(100), user3(75).

3. Final Answer:

   ["user2", "100", "user3", "75"] -> Option A

4. Quick Check:

   Top 2 by score desc = user2, user3 [OK]

Hint: ZREVRANGE 0 1 gets top 2 highest scores [OK]

Common Mistakes:

• Confusing ZREVRANGE with ZRANGE (ascending order)
• Ignoring WITHSCORES option output format
• Mixing member and score order in output

4. You run the following Redis commands:

ZADD leaderboard 30 user1
ZADD leaderboard 60 user2
ZADD leaderboard 45 user3
ZREVRANGE leaderboard 0 2

But the output is empty. What is the most likely cause?

medium

A. ZREVRANGE returns ascending order by default

B. ZREVRANGE syntax is incorrect, it needs WITHSCORES

C. ZADD commands used wrong order of arguments

D. The leaderboard key was deleted before ZREVRANGE

Solution

1. Step 1: Check command correctness

   ZADD commands have correct syntax and add members with scores.

2. Step 2: Analyze empty output from ZREVRANGE

   Empty output means the key 'leaderboard' likely does not exist or was deleted before ZREVRANGE.

3. Final Answer:

   The leaderboard key was deleted before ZREVRANGE -> Option D

4. Quick Check:

   Empty output = missing key [OK]

Hint: Empty ZREVRANGE means key missing or deleted [OK]

Common Mistakes:

• Thinking WITHSCORES is required for output (it's optional)
• Assuming ZREVRANGE returns ascending order
• Believing ZADD argument order was wrong (it was correct)

5. You want to implement a leaderboard that shows the top 3 users but excludes any user with a score below 50. Which Redis commands or approach should you use?

hard

A. Use ZRANGEBYSCORE leaderboard 50 +inf LIMIT 0 3

B. Use ZREVRANGE leaderboard 0 2 and filter scores < 50 in application

C. Use ZREVRANGEBYSCORE leaderboard +inf 50 LIMIT 0 3

D. Use ZRANGE leaderboard 0 2 WITHSCORES and exclude scores < 50

Solution

1. Step 1: Understand filtering by score

   We want top 3 users with scores >= 50, sorted descending.

2. Step 2: Choose correct Redis command

   ZREVRANGEBYSCORE leaderboard +inf 50 LIMIT 0 3 returns members with scores between +inf and 50 descending, limited to 3.

3. Final Answer:

   Use ZREVRANGEBYSCORE leaderboard +inf 50 LIMIT 0 3 -> Option C

4. Quick Check:

   Filter by score with ZREVRANGEBYSCORE [OK]

Hint: Use ZREVRANGEBYSCORE with score limits and LIMIT [OK]

Common Mistakes:

• Using ZREVRANGE without score filtering
• Using ZRANGEBYSCORE which sorts ascending, not descending
• Filtering scores in app instead of Redis command