Quick Select

ArraySearchSort

Oct 14

Finds the kth smallest/largest element

Average: O(n)
Worst: O(n²)

Algorithm

	def quickSelect(list: List[int], l: int, r: int, k: int): -> int
	if l == r:
	return list[l]
	# Select a pivot index p between left and right
	p = partition(list, l, r, p)
	if k == p:
	return list[k]
	elif k < p:
	r = p - 1
	else:
	l = p + 1

view raw QuickSelectPseudo.py hosted with ❤ by GitHub

	def partition(nums: List[int], l: int, r: int) -> int:
	pivot, p = nums[r], r
	i = l
	while i < p:
	if nums[i] > pivot:
	nums[i], nums[p - 1] = nums[p - 1], nums[i]
	nums[p], nums[p - 1] = nums[p - 1], nums[p]
	i -= 1
	p -= 1
	i += 1
	return p

view raw partitionPseudo.py hosted with ❤ by GitHub

Given an integer array, find the kth largest element.

The easiest way? Sort the array. But that’s O(n log n).
Can we do better?
Sure! How about using a PriorityQueue? That’s O(n log k)!
Can we do even better?
Use Quick Select; the algorithm’s linear on average.

Why O(n)? The algorithm recurs only for the part that contains the kth largest element. If we assume it recurs half the list each time, it processes n elements in the first recursive call, n/2 in the second, n/4 in the third, and so on, until there’s only 1 element remaining.
Remember geometric series?

1 + (1 / 2) + (1 / 4) + ... + (1 / n) = 2. Similarly,
n + (n / 2) + (n / 4) + ... + 1 = 2n.

Average: O(n)
Worst: O(n²) if the array is already sorted

LeetCode

215. Kth Largest Element in an Array

Python | Java

	def findKthLargest(self, nums: List[int], k: int) -> int:
	def qselect(nums: List[int], l: int, r: int, k: int) -> None:
	p = partition(nums, l, r)

	if p < k:
	return qselect(nums, p + 1, r, k)
	if p > k:
	return qselect(nums, l, p - 1, k)

	return nums[p]

	def partition(nums: List[int], l: int, r: int) -> int:
	pivot, p = nums[r], r

	i = l
	while i < p:
	if nums[i] > pivot:
	nums[i], nums[p - 1] = nums[p - 1], nums[i]
	nums[p], nums[p - 1] = nums[p - 1], nums[p]
	i -= 1
	p -= 1

	i += 1

	return p

	return qselect(nums, 0, len(nums) - 1, len(nums) - k)

view raw findKthLargest.py hosted with ❤ by GitHub

	public int findKthLargest(int[] nums, int k) {
	return quickSelect(nums, 0, nums.length - 1, nums.length - k);
	}
	private int quickSelect(int[] nums, int l, int r, int k) {
	int p = partition(nums, l, r);
	if (p < k) return quickSelect(nums, p + 1, r, k);
	if (p > k) return quickSelect(nums, l, p - 1, k);
	return nums[p];
	}
	private int partition(int[] nums, int l, int r) {
	int pivot = nums[r];
	int p = r;
	for (int i = l; i < p; i++) {
	if (nums[i] > pivot) {
	swap(nums, i, p - 1);
	swap(nums, p, p - 1);
	i--;
	p--;
	}
	}
	return p;
	}
	private void swap(int[] nums, int a, int b) {
	int tmp = nums[a];
	nums[a] = nums[b];
	nums[b] = tmp;
	}