Photo Contest Podium

MediumsortingAlso known as Kth Largest Element in an Array

A town runs an online photo contest. Each photo's score is upvotes minus downvotes, so a disliked photo can score below zero. The scores arrive in no particular order.

The organisers announce prizes one place at a time, and today they only need the score that takes place k. Sorting thousands of scores just to read off one of them is more work than the job needs.

Your task

Write kthMostVotes(scores, k). Return the k-th largest value in scores, where k = 1 means the largest. Equal scores each take their own place: in [8, 8, 3] the 2nd largest is 8, not 3.

Aim for O(n) on average. You may copy the list, but do not sort it.

kthMostVotes(scores: int[], k: int) → int

Examples

Example 1

Input

scores = [14, 3, 27, 9, 27, 18]
k = 2

Output

Why

In order from highest: 27, 27, 18, 14, 9, 3. Two photos tie on 27, so places 1 and 2 are both 27.

Example 2

Input

scores = [14, 3, 27, 9, 27, 18]
k = 3

Output

Why

Places 1 and 2 are the two 27s, so place 3 is 18. Removing duplicates first would wrongly give 14.

Constraints

1 ≤ scores.length ≤ 10,000
-1,000,000 ≤ scores[i] ≤ 1,000,000
1 ≤ k ≤ scores.length

Start with brute force

Sort the scores from highest to lowest and return the one at index k - 1. It is correct and short, and costs O(n log n).

Sorting puts every score in its exact place, but you only need one place. Quickselect does a partition, keeps one side, and the work shrinks roughly by half each time: n + n/2 + n/4 + … ≈ 2n steps on average.

A min-heap that keeps only the k biggest scores seen so far is another good answer, at O(n log k). It shines when scores arrive as a stream.

Hints

0 of 4 shown

Hint 1
Pick any score, say 14 in the example, and split the others into "higher than 14" and "lower than 14". How many are higher? What does that tell you about 14's place?
Hint 2
Three scores beat 14, so 14 is in place 4 exactly. You learned its rank without sorting anything. If you want place 3, which group must you look in?
Hint 3
That is quicksort's partition step, but you only follow the one side that contains the place you want. The other side is never touched again.
Hint 4
Keep a range lo..hi and a target index k - 1 in highest-first order. Pick a random pivot, split the range into bigger, equal and smaller groups. If the target falls in the equal group, return the pivot. Otherwise shrink the range to the group that holds the target and repeat.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

A partition tells you a pivot's exact rank: everything bigger goes in front of it, everything smaller behind. If that rank is not the one you want, you know which side to keep, and you never sort the other side.

Trace [14, 3, 27, 9, 27, 18] with k = 3, so the target index (highest first) is 2. The pivot is random; suppose these are the picks:

Pivot 14. Bigger: 27, 27, 18 go to indexes 0 to 2. Equal: 14 at index 3. Smaller: 3 and 9 at 4 and 5. Target 2 is before index 3, so keep only indexes 0 to 2.
Range 0..2 holds 27, 27, 18. Pivot 27. Bigger: none. Equal: the two 27s at 0 and 1. Smaller: 18 at 2. Target 2 is after the equal block, so keep index 2 only.
Range 2..2 holds 18. Pivot 18, equal block is index 2, which is the target. Return 18.

The equal block is what makes ties work. With a plain two-way split, a list like [7, 7, 7, 7, 7] sends every score to one side and the range shrinks by only one each round.

The random pivot matters too. Always taking the first element is O(n²) on an already-sorted list, because each partition peels off just one score. A random pivot makes that bad luck very unlikely.

Reference solution

function kthMostVotes(scores, k) {
  const a = scores.slice();
  const target = k - 1; // index in highest-first order
  let lo = 0, hi = a.length - 1;
  while (true) {
    const pivot = a[lo + Math.floor(Math.random() * (hi - lo + 1))];
    // after the loop: a[lo..big-1] > pivot, a[big..small] == pivot, a[small+1..hi] < pivot
    let big = lo, i = lo, small = hi;
    while (i <= small) {
      if (a[i] > pivot) { [a[big], a[i]] = [a[i], a[big]]; big++; i++; }
      else if (a[i] < pivot) { [a[i], a[small]] = [a[small], a[i]]; small--; }
      else i++;
    }
    if (target < big) hi = big - 1;         // answer is among the bigger scores
    else if (target > small) lo = small + 1; // answer is among the smaller scores
    else return pivot;                       // target landed on the pivot's block
  }
}

import random
 
def kth_most_votes(scores, k):
    a = list(scores)
    target = k - 1  # index in highest-first order
    lo, hi = 0, len(a) - 1
    while True:
        pivot = a[random.randint(lo, hi)]
        # after the loop: a[lo:big] > pivot, a[big:small+1] == pivot, a[small+1:hi+1] < pivot
        big, i, small = lo, lo, hi
        while i <= small:
            if a[i] > pivot:
                a[big], a[i] = a[i], a[big]
                big += 1
                i += 1
            elif a[i] < pivot:
                a[i], a[small] = a[small], a[i]
                small -= 1
            else:
                i += 1
        if target < big:
            hi = big - 1  # answer is among the bigger scores
        elif target > small:
            lo = small + 1  # answer is among the smaller scores
        else:
            return pivot  # target landed on the pivot's block

TimeO(n)On average: each partition is linear in the current range and the range shrinks by a constant fraction on average. The worst case is O(n²), but random pivots make it very unlikely.

SpaceO(n)The copy of the list. The partition itself uses O(1) extra space.

Learn the idea: Quicksort Heaps and Priority Queues

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code