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
- 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;
}
}
- 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].
- Print the top k marks (largest first) with a
PriorityQueueof 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).
- Add a counter to
partitionand 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
- 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.
- 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.
- 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).
- Is quick sort stable? In-place? Not stable; in-place with O(log n) average stack.
- 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.sortuses a dual-pivot quick sort for primitives and a merge-based TimSort for objects (where stability matters). - Why is quickselect O(n) and not O(n log n)? It recurses into only one side: n + n/2 + n/4 + ... ≈ 2n.
- 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.