Skip to content

Leaderboard Runner Up

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 11 Session 1 (Click for link to problem statements)

Leaderboard Runner-Up

A game leaderboard holds unsorted scores in nums. You want the value that would sit in kth place if the scores were ranked from highest to lowest.

Return the kth largest element in nums.

def find_kth_largest(nums, k):
    pass

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Heaps, Priority Queues, Sorting, Selection

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • Q: Does "kth largest" mean the kth distinct value?

    • A: No. Duplicates each occupy their own leaderboard slot, so we want the kth element in sorted (descending) order, counting repeats.

  • Q: Do we need to keep nums sorted, or modify it?

    • A: No. We only need to return the single value in kth place; we do not need to produce a fully ranked leaderboard.

  • Q: Can we assume k is valid?

    • A: Yes, assume 1 <= k <= len(nums), so an answer always exists.
HAPPY CASE
Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
Explanation: Ranked from highest to lowest the scores are [6, 5, 4, 3, 2, 1], so 2nd place holds 5.

Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4
Explanation: Ranked from highest to lowest the scores are [6, 5, 5, 4, 3, 3, 2, 2, 1]. Duplicates count, so 4th place holds 4.

EDGE CASE
Input: nums = [7], k = 1
Output: 7
Explanation: With a single score, 1st place is the only place.

Input: nums = [2, 2, 2], k = 3
Output: 2
Explanation: Every slot on the leaderboard holds the same score, so 3rd place is still 2.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Top-K / Selection Problems, we can consider the following approaches:

  • Min-Heap of size k: Keep only the k largest scores seen so far in a min-heap; the heap's root is the kth largest. This is the classic top-k pattern.
  • Sorting: Sort descending and index position k - 1. Simple, but does more work than needed (O(N log N)).
  • Quickselect: Partition like quicksort to find the kth largest in average O(N) time, at the cost of a worse worst case and a trickier implementation.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Maintain a min-heap containing at most k scores. Push each score onto the heap; whenever the heap grows past size k, pop the minimum, evicting a score too small to be in the top k. After processing every score, the heap holds exactly the k largest values, and its root (the smallest of those) is the kth largest overall.

1) Create an empty min-heap.
2) For each score num in nums:
   a) Push num onto the heap.
   b) If the heap now holds more than k scores, pop the smallest one off.
3) The heap now contains exactly the k largest scores.
4) Return the root of the heap (its minimum), which is the kth largest score.

⚠️ Common Mistakes

  • Using a max-heap of all N elements and popping k times works, but misses the space savings of the size-k min-heap approach.
  • Confusing kth largest with kth distinct largest and skipping duplicates.
  • Returning the heap's maximum instead of its root (minimum) — the smallest of the top k is the answer.
  • Off-by-one when sorting instead: the kth largest lives at index k - 1 of a descending sort, or index len(nums) - k of an ascending sort.

4: I-mplement

Implement the code to solve the algorithm.

import heapq

def find_kth_largest(nums, k):
    # Min-heap holding the k largest scores seen so far
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        # If we have more than k scores, evict the smallest;
        # it cannot be the kth largest
        if len(heap) > k:
            heapq.heappop(heap)
    # The root (minimum) of the size-k heap is the kth largest overall
    return heap[0]

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: nums = [3, 2, 1, 5, 6, 4], k = 2

    • Push 3 → heap [3]. Push 2 → heap [2, 3].
    • Push 1 → size 3 > 2, pop 1 → heap [2, 3].
    • Push 5 → size 3 > 2, pop 2 → heap [3, 5].
    • Push 6 → size 3 > 2, pop 3 → heap [5, 6].
    • Push 4 → size 3 > 2, pop 4 → heap [5, 6].
    • Root is 5. Output: 5

  • Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4

    • After all pushes and evictions the heap holds the top 4 scores [4, 5, 5, 6].
    • Root is 4. Output: 4

  • Input: nums = [7], k = 1

    • Heap holds [7]; root is 7. Output: 7

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of scores in nums and K is the rank we are asked for.

  • Time Complexity: O(N log K) because each of the N scores triggers at most one push and one pop on a heap of size at most K, and each heap operation costs O(log K).
  • Space Complexity: O(K) for the heap, which never holds more than K scores.

Discussion:

  • Sorting gives a one-liner at O(N log N) time and is fine when N is small.
  • Quickselect improves the average time to O(N) with O(1) extra space, but has an O(N^2) worst case and is easier to get wrong under interview pressure. The min-heap approach is the sweet spot when K is much smaller than N — exactly the leaderboard scenario.

Clone this wiki locally