Quick Select

Use Cases

Use Case	Description	Example
K-th smallest / largest	Find the k-th order statistic without sorting the whole array. Average O(n) time, in-place.	`[3, 2, 1, 5, 6, 4]`, k = 2 → 2 (2nd smallest); k-th largest uses index `len(nums) - k`.
Median	Median is the middle order statistic. On an even-length array, pick the lower or upper middle consistently.	`[5, 3, 1, 2, 4]` → median index `len(nums) // 2` → 3.
Partition-based selection	Same partition idea as quicksort, but only recurse into one side.	After partition, pivot is in its final sorted position.
When heap is overkill	Prefer quickselect when you need one order statistic and k is large (full sort is O(n log n); heap is O(n log k)).	215. Kth Largest Element in an Array
Top-K by frequency (with care)	Often solved with a heap or bucket sort; quickselect applies when you select on values or unique keys after counting.	347. Top K Frequent Elements — bucket sort is more common; quickselect on unique frequencies is possible.

Index convention: The template below treats k as a 0-based rank (0 = smallest, n - 1 = largest). LeetCode “k-th largest” usually means k = len(nums) - k for 0-based smallest rank, or quickselect(nums, 0, n - 1, n - k) when k is 1-based largest rank.

Code Template

Imports and partition setup

Import random for pivot sampling — a fixed pivot (always left) can degrade to O(n²) on sorted input.
Lomuto-style partition: move pivot to right, scan [left, right), place elements < pivot on the left, then place pivot at its final index store_index.

Partition loop

For each index i in [left, right), swap elements smaller than the pivot toward the front.
Swap pivot into place and return its final index (the pivot’s sorted rank in this subarray).

Quickselect recursion

Base case: one element in range → return it.
Pick random pivot, partition, compare pivot index to k.
Recurse only on the side that contains k (left if k < pivot_index, else right).

import random

def partition(arr, left, right, pivot_index):
    pivot_value = arr[pivot_index]
    arr[pivot_index], arr[right] = arr[right], arr[pivot_index]
    store_index = left

Common Mistakes

Off-by-one on k (1-based vs 0-based)

# Wrong: LeetCode asks for "2nd smallest" (1-based) but you pass k=2 into 0-based quickselect
return quickselect(nums, 0, len(nums) - 1, k)

# Correct: convert 1-based rank to 0-based index
return quickselect(nums, 0, len(nums) - 1, k - 1)

K-th largest vs k-th smallest index

# Wrong: use k directly for "k-th largest"
return quickselect(nums, 0, len(nums) - 1, k)

# Correct: largest k (1-based) → index len(nums) - k
return quickselect(nums, 0, len(nums) - 1, len(nums) - k)

Wrong recursion bounds

# Wrong: include pivot index in both sides
return quickselect(arr, left, pivot_index, k)
return quickselect(arr, pivot_index, right, k)

# Correct: exclude pivot after it is placed
return quickselect(arr, left, pivot_index - 1, k)
return quickselect(arr, pivot_index + 1, right, k)

Issues and Considerations

Average vs worst time: Quickselect is O(n) on average; with bad pivots it is O(n²). Random pivots work well in practice. For guaranteed linear worst case, use median-of-medians (rare in interviews).
Versus sorting: Full sort is O(n log n) and simpler when you need the full order or many order statistics.
Versus a heap: A size-k min-heap is O(n log k) — often better when k is small (e.g. top 10 of millions of items). Quickselect wins when you need a single statistic and k is large.
In-place mutation: Partition reorders arr. Copy first if the input must stay unchanged.
Recursion stack: Depth is O(log n) on average, O(n) worst case; an iterative loop on (left, right) avoids deep recursion.
Duplicates: Standard Lomuto partition (< pivot) still finds a valid k-th smallest, but many equal elements can make recursion unbalanced. Three-way partition (Dutch national flag) is safer when duplicates are heavy.
Stability: Not stable; order of equal elements is not preserved.
Median on even n: Define whether you want the lower or upper middle index; stay consistent with k = len(nums) // 2 or k = (len(nums) - 1) // 2.

Same partition / quickselect as the template above; only the wrapper or compare key changes.

215. Kth Largest Element in an Array

import random
from typing import List

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def partition(arr, left, right, pivot_index):
            pivot_value = arr[pivot_index]
            arr[pivot_index], arr[right] = arr[right], arr[pivot_index]
            store_index = left
            for i in range(left, right):
                if arr[i] < pivot_value:
                    arr[store_index], arr[i] = arr[i], arr[store_index]
                    store_index += 1
            arr[right], arr[store_index] = arr[store_index], arr[right]
            return store_index

        def quickselect(arr, left, right, k):
            if left == right:
                return arr[left]
            pivot_index = random.randint(left, right)
            pivot_index = partition(arr, left, right, pivot_index)
            if k == pivot_index:
                return arr[k]
            if k < pivot_index:
                return quickselect(arr, left, pivot_index - 1, k)
            return quickselect(arr, pivot_index + 1, right, k)

        # find_kth_largest: 1-based largest k → 0-based index len(nums) - k
        return quickselect(nums, 0, len(nums) - 1, len(nums) - k)

973. K Closest Points to Origin

import random
from typing import List

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        def distance(point):
            return point[0] * point[0] + point[1] * point[1]

        def partition(arr, left, right, pivot_index):
            pivot_value = distance(arr[pivot_index])
            arr[pivot_index], arr[right] = arr[right], arr[pivot_index]
            store_index = left
            for i in range(left, right):
                if distance(arr[i]) < pivot_value:
                    arr[store_index], arr[i] = arr[i], arr[store_index]
                    store_index += 1
            arr[right], arr[store_index] = arr[store_index], arr[right]
            return store_index

        def quickselect(arr, left, right, k):
            if left == right:
                return arr[left]
            pivot_index = random.randint(left, right)
            pivot_index = partition(arr, left, right, pivot_index)
            if k == pivot_index:
                return arr[k]
            if k < pivot_index:
                return quickselect(arr, left, pivot_index - 1, k)
            return quickselect(arr, pivot_index + 1, right, k)

        # find_kth_smallest on distance rank, then first k points are closest
        quickselect(points, 0, len(points) - 1, k - 1)
        return points[:k]