SyntaxPilot
Courses/DSA and Coding Problems/Lesson 18

DSA and Coding Problems · Lesson 18 of 90 · 15 min

Quick sort and quickselect: kth largest element

queued

These are the notes for DSA episode 18, the third episode of the sorting block. Merge sort (episode 17) split the array in half and merged; today we split it around a pivot. That one idea, partition, gives us quick sort (the O(n log n) average sort inside many libraries) and quickselect, which finds the kth largest element in O(n) average time without sorting. We also see the two inputs that break quick sort: already sorted data with a fixed pivot (fixed by a random pivot) and all-equal data (fixed next episode by a 3-way partition). Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

Results day. Two lakh students wrote an entrance exam and their marks sit in a list, in no particular order. The college has one lakh seats: the best one lakh get in. The college needs one number, the cutoff: the marks of the one lakh-th topper. In coding terms that is the kth largest element, with k = 1,00,000, and the results portal must answer fast.

In the school line (the key idea) In the array
The PT teacher picks any one student, say Ravi Pivot: one chosen value, here p = a[hi]
Everyone shorter goes to his left, everyone taller to his right; nobody sorts within a side Partition: values < p to the left, >= p to the right, in one pass
Ravi's spot is now exactly right: with 12 students on his left he is 13th shortest The pivot lands at its final index and never moves again

Problem statement

Given an integer array a and an integer k (1 ≤ k ≤ n), return the kth largest element in sorted order (duplicates count separately; it is not the kth distinct value).

  • [3, 2, 1, 5, 6, 4], k = 2 → 5 (largest 6, second largest 5)
  • [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4 → 4 (6, 5, 5, 4)
  • Edge cases: one element ([7], k = 1 → 7), k = 1, k = n, all values equal ([9, 9, 9], k = 3 → 9).
  • Constraints: n up to 2 × 10⁵, a few seconds of time.

The key fact: in sorted (ascending) order, the kth largest sits at index n - k. For n = 6 and k = 2 that is index 4.

Brute force: pick the topper k times

What a clerk would do: find the topper, set the sheet aside, repeat k times. The last one picked is the answer.

import java.util.*;

public class Main {
    static int kthBrute(int[] a, int k) {
        boolean[] used = new boolean[a.length];
        int ans = 0;
        for (int round = 0; round < k; round++) {
            int best = -1;
            for (int i = 0; i < a.length; i++)
                if (!used[i] && (best == -1 || a[i] > a[best]))
                    best = i;
            used[best] = true;
            ans = a[best];
        }
        return ans;
    }
    public static void main(String[] args) {
        int[] a = {3, 2, 1, 5, 6, 4};
        int[] b = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        int[] c = {7};
        int[] d = {9, 9, 9};
        System.out.println(kthBrute(a, 2));
        System.out.println(kthBrute(b, 4));
        System.out.println(kthBrute(c, 1));
        System.out.println(kthBrute(d, 3));
    }
}

Output:

5
4
7
9

Correct on every example. Now two lakh random marks with k = n / 2:

import java.util.*;

public class Main {
    static int kthBrute(int[] a, int k) {
        boolean[] used = new boolean[a.length];
        int ans = 0;
        for (int round = 0; round < k; round++) {
            int best = -1;
            for (int i = 0; i < a.length; i++)
                if (!used[i] && (best == -1 || a[i] > a[best]))
                    best = i;
            used[best] = true;
            ans = a[best];
        }
        return ans;
    }
    public static void main(String[] args) {
        int n = 200000;
        int[] a = new int[n];
        Random r = new Random(1);
        for (int i = 0; i < n; i++) a[i] = r.nextInt(1000000);
        long t0 = System.nanoTime();
        int ans = kthBrute(a, n / 2);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(ans + "   " + ms + " ms");
    }
}

Result in the compiler: Time Limit Exceeded (stopped at 8 seconds; the same scan with n = 20,000 took about 0.75 s, so 2 lakh needs about 100 times that, over a minute).

Why it is slow

k rounds, each scanning all n values: O(n · k). With n = 2 × 10⁵ and k = 10⁵ that is 2 × 10¹⁰ steps, and when k is around n / 2 it is O(n²).

Approach Work for n = 2 lakh, k = 1 lakh
Pick the max k times k × n = 2 × 10¹⁰: minutes
Sort, then read a[n - k] n log n ≈ 35 lakh: a fraction of a second
Quickselect (today) about 2n = 4 lakh, on average

Sorting works, but it puts every student in order when we need one position. Interviewers ask for better than O(n log n).

Partition: the pivot lands in its final place

Lomuto partition of a[lo..hi]: take the last value as the pivot p. A pointer i marks where the next value smaller than p should go. Walk j from lo to hi - 1; whenever a[j] < p, swap it into a[i] and move i forward. Finally swap the pivot into a[i].

Trace on [5, 1, 4, 2, 8, 3], pivot 3:

Step j a[j] < 3? Action Array i
start [5, 1, 4, 2, 8, 3] 0
1 0 5: no skip [5, 1, 4, 2, 8, 3] 0
2 1 1: yes swap a[0], a[1] [1, 5, 4, 2, 8, 3] 1
3 2 4: no skip [1, 5, 4, 2, 8, 3] 1
4 3 2: yes swap a[1], a[3] [1, 2, 4, 5, 8, 3] 2
5 4 8: no skip [1, 2, 4, 5, 8, 3] 2
end swap pivot into a[2] [1, 2, 3, 5, 8, 4] returns 2

Everything left of index 2 is smaller than 3, everything right is at least 3, so 3 is in its final sorted position. One pass: O(n) time, O(1) extra space.

Quick sort

Partition places one value for good; then partition the left part and the right part, and so on. A range with 0 or 1 values is already sorted. If the pivot splits ranges roughly in half, there are about log n levels with n work per level: O(n log n).

import java.util.*;

public class Main {
    static int partition(int[] a, int lo, int hi) {
        int p = a[hi], i = lo;
        for (int j = lo; j < hi; j++)
            if (a[j] < p) {
                int t = a[i]; a[i] = a[j]; a[j] = t;
                i++;
            }
        int t = a[i]; a[i] = a[hi]; a[hi] = t;
        return i;
    }
    static void quick(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int p = partition(a, lo, hi);
        quick(a, lo, p - 1);
        quick(a, p + 1, hi);
    }
    public static void main(String[] args) {
        int[] a = {5, 1, 4, 2, 8, 3};
        quick(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
        int[] e = {};
        quick(e, 0, e.length - 1);
        System.out.println(Arrays.toString(e));
        int[] d = {3, 3, 1, 3};
        quick(d, 0, d.length - 1);
        System.out.println(Arrays.toString(d));
    }
}

Output:

[1, 2, 3, 4, 5, 8]
[]
[1, 3, 3, 3]

The empty array works because lo = 0, hi = -1, so quick returns at once.

Sorted input: StackOverflowError

The same code on one lakh numbers that are already sorted (0 to 99999):

import java.util.*;

public class Main {
    static int partition(int[] a, int lo, int hi) {
        int p = a[hi], i = lo;
        for (int j = lo; j < hi; j++)
            if (a[j] < p) {
                int t = a[i]; a[i] = a[j]; a[j] = t;
                i++;
            }
        int t = a[i]; a[i] = a[hi]; a[hi] = t;
        return i;
    }
    static void quick(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int p = partition(a, lo, hi);
        quick(a, lo, p - 1);
        quick(a, p + 1, hi);
    }
    public static void main(String[] args) {
        int n = 100000;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = i;
        long t0 = System.nanoTime();
        quick(a, 0, n - 1);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(a[0] + " " + a[n - 1] + "   " + ms + " ms");
    }
}

Output:

Exception in thread "main" java.lang.StackOverflowError
    at Main.quick(Main.java:16)
    at Main.quick(Main.java:17)
    at Main.quick(Main.java:17)
    ...

Why: on sorted data the last value is always the maximum, so every value goes to the pivot's left and the right side is empty. Each call removes only one value, so the recursion is n levels deep (one lakh nested calls overflow Java's call stack) and the work is n + (n - 1) + ... + 1 = O(n²). That is quick sort's worst case. The same happens with the first element as pivot on sorted or reverse-sorted data.

The random pivot fix

Don't let the input choose the pivot. Pick a random index in [lo, hi], swap it to a[hi], and partition exactly as before:

import java.util.*;

public class Main {
    static Random rnd = new Random();

    static int partition(int[] a, int lo, int hi) {
        int r = lo + rnd.nextInt(hi - lo + 1);
        int s = a[r]; a[r] = a[hi]; a[hi] = s;
        int p = a[hi], i = lo;
        for (int j = lo; j < hi; j++)
            if (a[j] < p) {
                int t = a[i]; a[i] = a[j]; a[j] = t;
                i++;
            }
        int t = a[i]; a[i] = a[hi]; a[hi] = t;
        return i;
    }
    static void quick(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int p = partition(a, lo, hi);
        quick(a, lo, p - 1);
        quick(a, p + 1, hi);
    }
    public static void main(String[] args) {
        int n = 100000;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = i;
        long t0 = System.nanoTime();
        quick(a, 0, n - 1);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(a[0] + " " + a[n - 1] + "   " + ms + " ms");
    }
}

Output (the time varies a little from run to run):

0 99999   15 ms

With a random pivot no input is bad on purpose: the expected recursion depth is O(log n) and the expected time O(n log n). The O(n²) worst case is still possible, but astronomically unlikely.

Quickselect: follow only one side

To find the kth largest, set target = n - k. Partition once; the pivot lands at index p.

  • p == target: the pivot is the answer.
  • p < target: the answer is to the right; ignore the left side (lo = p + 1).
  • p > target: the answer is to the left (hi = p - 1).

Unlike quick sort we follow only one side, so a loop is enough (no recursion). With a random pivot each step throws away about half the range on average: n + n/2 + n/4 + ... ≈ 2n, so O(n) average.

Trace on [3, 2, 1, 5, 6, 4], k = 2, target = 6 - 2 = 4 (pivots shown as the last value, for illustration):

Partition Range Pivot Array after p Next
1 0..5 4 [3, 2, 1, 4, 6, 5] 3 3 < 4 → lo = 4
2 4..5 5 [3, 2, 1, 4, 5, 6] 4 p == target → answer 5
import java.util.*;

public class Main {
    static Random rnd = new Random();

    static int partition(int[] a, int lo, int hi) {
        int r = lo + rnd.nextInt(hi - lo + 1);
        int s = a[r]; a[r] = a[hi]; a[hi] = s;
        int p = a[hi], i = lo;
        for (int j = lo; j < hi; j++)
            if (a[j] < p) {
                int t = a[i]; a[i] = a[j]; a[j] = t;
                i++;
            }
        int t = a[i]; a[i] = a[hi]; a[hi] = t;
        return i;
    }
    static int kthLargest(int[] a, int k) {
        int target = a.length - k;
        int lo = 0, hi = a.length - 1;
        while (true) {
            int p = partition(a, lo, hi);
            if (p == target) return a[p];
            if (p < target) lo = p + 1;
            else hi = p - 1;
        }
    }
    public static void main(String[] args) {
        int[] a = {3, 2, 1, 5, 6, 4};
        int[] b = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        int[] c = {7};
        int[] d = {9, 9, 9};
        System.out.println(kthLargest(a, 2));
        System.out.println(kthLargest(b, 4));
        System.out.println(kthLargest(c, 1));
        System.out.println(kthLargest(d, 3));
    }
}

Output:

5
4
7
9

And the input that timed out (two lakh marks, k = one lakh), with a sorted copy as a check:

import java.util.*;

public class Main {
    static Random rnd = new Random();

    static int partition(int[] a, int lo, int hi) {
        int r = lo + rnd.nextInt(hi - lo + 1);
        int s = a[r]; a[r] = a[hi]; a[hi] = s;
        int p = a[hi], i = lo;
        for (int j = lo; j < hi; j++)
            if (a[j] < p) {
                int t = a[i]; a[i] = a[j]; a[j] = t;
                i++;
            }
        int t = a[i]; a[i] = a[hi]; a[hi] = t;
        return i;
    }
    static int kthLargest(int[] a, int k) {
        int target = a.length - k;
        int lo = 0, hi = a.length - 1;
        while (true) {
            int p = partition(a, lo, hi);
            if (p == target) return a[p];
            if (p < target) lo = p + 1;
            else hi = p - 1;
        }
    }
    public static void main(String[] args) {
        int n = 200000;
        int[] a = new int[n];
        Random r = new Random(1);
        for (int i = 0; i < n; i++) a[i] = r.nextInt(1000000);
        long t0 = System.nanoTime();
        int ans = kthLargest(a, n / 2);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(ans + "   " + ms + " ms");
        int[] b = a.clone();
        Arrays.sort(b);
        System.out.println("check: " + b[n - n / 2]);
    }
}

Output (time varies):

499312   19 ms
check: 499312

From 2 × 10¹⁰ steps to a few lakh: milliseconds instead of minutes.

The off-by-one bug: target = n - k + 1

"The kth largest is the kth from the end", so someone writes a.length - k + 1:

import java.util.*;

public class Main {
    static Random rnd = new Random();

    static int partition(int[] a, int lo, int hi) {
        int r = lo + rnd.nextInt(hi - lo + 1);
        int s = a[r]; a[r] = a[hi]; a[hi] = s;
        int p = a[hi], i = lo;
        for (int j = lo; j < hi; j++)
            if (a[j] < p) {
                int t = a[i]; a[i] = a[j]; a[j] = t;
                i++;
            }
        int t = a[i]; a[i] = a[hi]; a[hi] = t;
        return i;
    }
    static int kthLargest(int[] a, int k) {
        int target = a.length - k + 1;
        int lo = 0, hi = a.length - 1;
        while (true) {
            int p = partition(a, lo, hi);
            if (p == target) return a[p];
            if (p < target) lo = p + 1;
            else hi = p - 1;
        }
    }
    public static void main(String[] args) {
        System.out.println(kthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2));
        System.out.println(kthLargest(new int[]{3, 2, 1, 5, 6, 4}, 1));
    }
}

Output:

6
Exception in thread "main" java.lang.IllegalArgumentException: bound must be positive
    at java.base/java.util.Random.nextInt(Random.java:557)
    at Main.partition(Main.java:7)
    ...

For k = 2 it returns 6, the largest (wrong). For k = 1 the target is 6, an index that does not exist; the window lo..hi shrinks to nothing and rnd.nextInt(0) throws. Indexes start at 0: the largest is at n - 1, so the kth largest is at n - k. Always test k = 1 and k = n.

Many equal values: still a StackOverflowError

Real marks have ties. With every value equal to 7, every pivot is 7, nothing is < 7, so everything lands on one side again, random pivot or not:

import java.util.*;

public class Main {
    static Random rnd = new Random();

    static int partition(int[] a, int lo, int hi) {
        int r = lo + rnd.nextInt(hi - lo + 1);
        int s = a[r]; a[r] = a[hi]; a[hi] = s;
        int p = a[hi], i = lo;
        for (int j = lo; j < hi; j++)
            if (a[j] < p) {
                int t = a[i]; a[i] = a[j]; a[j] = t;
                i++;
            }
        int t = a[i]; a[i] = a[hi]; a[hi] = t;
        return i;
    }
    static void quick(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int p = partition(a, lo, hi);
        quick(a, lo, p - 1);
        quick(a, p + 1, hi);
    }
    public static void main(String[] args) {
        int n = 100000;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = 7;
        long t0 = System.nanoTime();
        quick(a, 0, n - 1);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(a[0] + " " + a[n - 1] + "   " + ms + " ms");
    }
}

Output:

Exception in thread "main" java.lang.StackOverflowError
    at java.base/java.util.Random.nextInt(Random.java:558)
    ...

The fix is a 3-way partition: smaller | equal | bigger, and skip the whole equal block. That is the Dutch national flag algorithm, next episode. (Hoare's partition scheme, which stops on equal values from both sides, also handles this case well.)

Alternative: a min-heap of size k

Keep the k largest values seen so far in a min-heap (PriorityQueue); when it grows past k, remove the smallest. At the end, the heap's top is the kth largest. O(n log k) time, O(k) extra space, and it works on a stream of marks arriving one by one (quickselect needs the whole array).

import java.util.*;

public class Main {
    static int kthLargest(int[] a, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int x : a) {
            heap.add(x);
            if (heap.size() > k) heap.poll();
        }
        return heap.peek();
    }
    public static void main(String[] args) {
        System.out.println(kthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2));
        System.out.println(kthLargest(new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4));
    }
}

Output:

5
4

The solution in Java, C++ and Python

Java

import java.util.*;

public class Main {
    static Random rnd = new Random();

    static int partition(int[] a, int lo, int hi) {
        int r = lo + rnd.nextInt(hi - lo + 1);
        int s = a[r]; a[r] = a[hi]; a[hi] = s;
        int p = a[hi], i = lo;
        for (int j = lo; j < hi; j++)
            if (a[j] < p) {
                int t = a[i]; a[i] = a[j]; a[j] = t;
                i++;
            }
        int t = a[i]; a[i] = a[hi]; a[hi] = t;
        return i;
    }
    static int kthLargest(int[] a, int k) {
        int target = a.length - k;
        int lo = 0, hi = a.length - 1;
        while (true) {
            int p = partition(a, lo, hi);
            if (p == target) return a[p];
            if (p < target) lo = p + 1;
            else hi = p - 1;
        }
    }
    static void quick(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int p = partition(a, lo, hi);
        quick(a, lo, p - 1);
        quick(a, p + 1, hi);
    }
    public static void main(String[] args) {
        int[] a = {3, 2, 1, 5, 6, 4};
        int[] b = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        int[] c = {7};
        int[] d = {9, 9, 9};
        System.out.println(kthLargest(a, 2));
        System.out.println(kthLargest(b, 4));
        System.out.println(kthLargest(c, 1));
        System.out.println(kthLargest(d, 3));
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

mt19937 rng(random_device{}());

int partition(vector<int>& a, int lo, int hi) {
    int r = lo + rng() % (hi - lo + 1);
    swap(a[r], a[hi]);
    int p = a[hi], i = lo;
    for (int j = lo; j < hi; j++)
        if (a[j] < p) swap(a[i++], a[j]);
    swap(a[i], a[hi]);
    return i;
}

void quick(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quick(a, lo, p - 1);
    quick(a, p + 1, hi);
}

int kthLargest(vector<int> a, int k) {
    int target = a.size() - k, lo = 0, hi = a.size() - 1;
    while (true) {
        int p = partition(a, lo, hi);
        if (p == target) return a[p];
        if (p < target) lo = p + 1;
        else hi = p - 1;
    }
}

int main() {
    vector<int> s = {5, 1, 4, 2, 8, 3};
    quick(s, 0, s.size() - 1);
    for (int x : s) cout << x << ' ';
    cout << '\n';
    cout << kthLargest({3, 2, 1, 5, 6, 4}, 2) << '\n';
    cout << kthLargest({3, 2, 3, 1, 2, 4, 5, 5, 6}, 4) << '\n';
    cout << kthLargest({7}, 1) << '\n';
    cout << kthLargest({9, 9, 9}, 3) << '\n';
    // the library way: nth_element is quickselect
    vector<int> b = {3, 2, 1, 5, 6, 4};
    nth_element(b.begin(), b.end() - 2, b.end());
    cout << *(b.end() - 2) << '\n';
}

Output:

1 2 3 4 5 8 
5
4
7
9
5

In C++, std::nth_element is a ready-made quickselect (introselect), and std::sort is an introsort: quick sort that switches to heap sort if recursion gets too deep.

Python

import random

def partition(a, lo, hi):
    r = random.randint(lo, hi)
    a[r], a[hi] = a[hi], a[r]
    p, i = a[hi], lo
    for j in range(lo, hi):
        if a[j] < p:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i

def quick(a, lo, hi):
    if lo >= hi:
        return
    p = partition(a, lo, hi)
    quick(a, lo, p - 1)
    quick(a, p + 1, hi)

def kth_largest(a, k):
    a = a[:]
    target, lo, hi = len(a) - k, 0, len(a) - 1
    while True:
        p = partition(a, lo, hi)
        if p == target:
            return a[p]
        if p < target:
            lo = p + 1
        else:
            hi = p - 1

s = [5, 1, 4, 2, 8, 3]
quick(s, 0, len(s) - 1)
print(s)
print(kth_largest([3, 2, 1, 5, 6, 4], 2))
print(kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))
print(kth_largest([7], 1))
print(kth_largest([9, 9, 9], 3))

import heapq
print(heapq.nlargest(2, [3, 2, 1, 5, 6, 4])[-1])

Output:

[1, 2, 3, 4, 5, 8]
5
4
7
9
5

(heapq.nlargest(k, a)[-1] is the heap approach in one line.)

Complexity

Approach Time (average) Time (worst) Extra space
Pick the max k times O(n · k) O(n²) when k ≈ n O(n) for used
Sort, read a[n - k] O(n log n) O(n log n) O(1) to O(n), by sort
Min-heap of size k O(n log k) O(n log k) O(k)
Quickselect, random pivot O(n) O(n²), practically never O(1)
Quick sort, random pivot O(n log n) O(n²), practically never O(log n) stack on average
Quick sort, last-element pivot, sorted input O(n²) O(n²) O(n) stack → StackOverflowError

Quick sort is in-place but not stable (partition swaps values across long distances).

Common mistakes

Mistake What you see Why Fix
p = a[hi] (fixed pivot) on sorted input java.lang.StackOverflowError the pivot is always the max: n levels deep, O(n²) random pivot, swap it to a[hi]
target = a.length - k + 1 k = 2 prints 6; k = 1: IllegalArgumentException: bound must be positive indexes start at 0 target = a.length - k
quick(a, lo, p) instead of p - 1 wasted work; with an end pivot the range may never shrink (StackOverflowError) p is already final recurse on lo..p-1 and p+1..hi
rnd.nextInt(hi - lo) the last index is never chosen as pivot; on a 1-value range: bound must be positive nextInt(b) returns 0..b-1 lo + rnd.nextInt(hi - lo + 1)
Many equal values with a 2-way partition java.lang.StackOverflowError (all 7s) everything goes to one side 3-way partition (next episode)
Brute force on n = 2 × 10⁵ Time Limit Exceeded O(n · k) quickselect or a heap

Mini project: the admission cutoff

Given everyone's marks and the number of seats, print the cutoff and how many students score at or above it (ties at the cutoff may take more students than seats, so the college must decide a tie-break rule).

import java.util.*;

public class Main {
    static Random rnd = new Random();

    static int partition(int[] a, int lo, int hi) {
        int r = lo + rnd.nextInt(hi - lo + 1);
        int s = a[r]; a[r] = a[hi]; a[hi] = s;
        int p = a[hi], i = lo;
        for (int j = lo; j < hi; j++)
            if (a[j] < p) {
                int t = a[i]; a[i] = a[j]; a[j] = t;
                i++;
            }
        int t = a[i]; a[i] = a[hi]; a[hi] = t;
        return i;
    }
    static int kthLargest(int[] a, int k) {
        int target = a.length - k;
        int lo = 0, hi = a.length - 1;
        while (true) {
            int p = partition(a, lo, hi);
            if (p == target) return a[p];
            if (p < target) lo = p + 1;
            else hi = p - 1;
        }
    }
    public static void main(String[] args) {
        int[] marks = {182, 145, 199, 160, 145, 171, 133, 160, 190, 145};
        int seats = 5;
        int cutoff = kthLargest(marks.clone(), seats);
        int admitted = 0;
        for (int m : marks) if (m >= cutoff) admitted++;
        System.out.println("Cutoff: " + cutoff);
        System.out.println("Students at or above the cutoff: " + admitted);
    }
}

Output:

Cutoff: 160
Students at or above the cutoff: 6

Two students tied at 160, so 6 students qualify for 5 seats. Extension: read the marks from input, and print the tie count separately.

Practice

  1. Find the kth smallest element with quickselect.
Solution

Only the target changes: target = k - 1. For [3, 2, 1, 5, 6, 4], k = 2 it printed 2.

    static int kthSmallest(int[] a, int k) {
        int target = k - 1, lo = 0, hi = a.length - 1;
        while (true) {
            int p = partition(a, lo, hi);
            if (p == target) return a[p];
            if (p < target) lo = p + 1;
            else hi = p - 1;
        }
    }
  1. Quick sort in descending order.
Solution

Flip one comparison in partition: if (a[j] > p). For [5, 1, 4, 2, 8, 3] it printed [8, 5, 4, 3, 2, 1].

  1. Print the top k marks (largest first) with a PriorityQueue of size k.
Solution
    static List<Integer> topK(int[] a, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int x : a) {
            heap.add(x);
            if (heap.size() > k) heap.poll();
        }
        List<Integer> res = new ArrayList<>(heap);
        res.sort(Collections.reverseOrder());
        return res;
    }

For {182, 145, 199, 160, 171, 133, 190}, k = 3 it printed [199, 190, 182]. O(n log k).

  1. Add a counter to partition and run quickselect on the same 2 lakh numbers 10 times. Why does the count change every run, and roughly what is it compared with n?
Solution

The pivot is random, so the splits differ each run. The total number of comparisons stays around 2n to 4n (a few lakh), never anywhere near n² / 2. That is what "O(n) on average" means.

Quick quiz

int[] a = {9, 4, 7, 1, 8, 2, 6}; (n = 7). For the 3rd largest, which index does quickselect target?

  • 4
  • 3
  • 2
  • 5
Answer

4 = n - k = 7 - 3. Sorted: [1, 2, 4, 6, 7, 8, 9], and index 4 holds 7, the 3rd largest (9, 8, 7).

Interview questions

  1. Kth largest element in an array: what's the best approach? Quickselect with a random pivot, O(n) average, O(1) extra space. Mention the heap (O(n log k)) for streams and when worst-case guarantees matter.
  2. What is the worst case of quick sort and when does it happen? O(n²), when the pivot is always the smallest or largest value, e.g. a last-element pivot on sorted input.
  3. How do you avoid it? Random pivot (or median-of-three); for many duplicates, a 3-way partition; libraries use introsort (switch to heap sort when recursion is too deep).
  4. Is quick sort stable? In-place? Not stable; in-place with O(log n) average stack.
  5. Quick sort vs merge sort? Quick sort: in-place, cache-friendly, usually faster in practice, O(n²) worst case. Merge sort: guaranteed O(n log n) and stable, but O(n) extra space. Java's Arrays.sort uses a dual-pivot quick sort for primitives and a merge-based TimSort for objects (where stability matters).
  6. Why is quickselect O(n) and not O(n log n)? It recurses into only one side: n + n/2 + n/4 + ... ≈ 2n.
  7. Can kth largest be found in worst-case O(n)? Yes, with the median-of-medians pivot, but its constant is large, so random pivots are used in practice.

Glossary

Term Meaning
Kth largest element The value at position k when the array is sorted from largest to smallest (duplicates counted)
Cutoff Real-life name for the kth largest mark when there are k seats
Pivot The value chosen to split the array around
Partition Rearranging a range so values smaller than the pivot come before it and the rest after it; the pivot ends at its final index
Lomuto partition The partition scheme used here: pivot at a[hi], pointer i marks the boundary of the smaller part
Hoare partition Another scheme with two pointers moving towards each other; fewer swaps, handles duplicates better
Quick sort Partition, then recursively sort the left and right parts
Quickselect Partition, then continue only in the part that contains the target index
Target index n - k for the kth largest, k - 1 for the kth smallest (0-based)
Random pivot Choosing the pivot at a random index so no input is consistently bad
Recursion depth How many calls are nested at the deepest point
Call stack Memory where Java keeps each active method call
StackOverflowError Java's error when nested calls use up the call stack
IllegalArgumentException Java's error for an invalid argument, here Random.nextInt(0)
Average case Expected running time over random choices (or random inputs)
Worst case The slowest possible running time
Min-heap / PriorityQueue A structure that always gives back its smallest element in O(log n)
In-place Uses O(1) extra memory besides the input (plus recursion stack)
Stable Equal keys keep their original relative order; quick sort is not stable
3-way partition Splitting into smaller / equal / bigger; the Dutch national flag (next episode)
Time Limit Exceeded (TLE) Too slow for the judge's limit (8 s in the SyntaxPilot compiler)

Summary

  • Partition puts the pivot in its final place in one O(n) pass.
  • Quick sort = partition + recurse on both sides: O(n log n) average, in-place, not stable.
  • A fixed last-element pivot on sorted input is O(n²) and throws StackOverflowError; a random pivot fixes it.
  • Quickselect follows only one side: the kth largest in O(n) average; the target is index n - k.
  • A min-heap of size k gives O(n log k) and works on streams.
  • Many equal values still break a 2-way partition: next episode's 3-way partition fixes it.

Next episode: Counting sort, radix sort and the Dutch national flag.