---
title: 'K-th Element'
source: 'https://academia.sh/en/courses/advanced-algorithms/kth-element'
course: 'Advanced Algorithms and Problem Solving'
language: en
updated: '2026-08-17T18:07:30+00:00'
license: 'CC BY-SA 4.0'
---

# K-th Element

Heap-based and partition-based solutions to selection problems; the 27 diverging inputs that appear once the question shifts, and the 15-fold step increase from pivot choice.

The previous pattern gave the median, the value **in the middle** of sorted order. The median
is a special case of a general question: what is the **k-th** value in sorted order. If k is
in the middle, that is the median; if k is one, the smallest value is asked; if k is n, the
largest.

This lesson answers the question with two separate patterns. The first keeps a k-sized
**heap**; the second **partitions** the array and searches only the relevant half. Both are
tested against the same oracle, and two different kinds of precondition emerge: one touches
**the question's definition**, the other touches **the input's arrangement**.

## Two Patterns, One Oracle

The oracle places the array front to back by comparison and reads the k-th position; every
comparison is counted as one step. The heap pattern holds only k elements: every new value
goes into a max-heap, and if the heap exceeds k, its top is popped. The value left on top at
the end is the k-th smallest among all values seen. The heap invariant and sift operations
were established in the Data Structures course's Heaps lesson; they are not repeated here.

The same structure appears to answer one more question: **the k-th smallest distinct
value.** The only difference is that a value already seen is not put back into the heap. The
code is nearly identical, the output is a number, the pattern is still cheap.

**PP47.** The corpus is the previous lessons' corpus: 40 arrays, 12 values each, ranging from
−9 to 20; seed `20260218`.
**PP48.** The oracle's answer is the **k-th element**: the value at position k in sorted
order, duplicates included.
**PP49.** The heap's steps are real comparisons; values are placed into a wrapper that counts
comparisons.
**PP50.** Four k values are swept: 3, 4, 6, and 8.

```python
import heapq

SEED, LENGTH, CORPUS_SIZE = 20260218, 12, 40


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def corpus(seed=SEED, n=CORPUS_SIZE, length=LENGTH):
    r = generator(seed)
    return [{"no": i + 1, "array": [r(30) - 9 for _ in range(length)]}
            for i in range(n)]


class Counter:
    def __init__(self):
        self.step = 0

    def count(self):
        self.step += 1


class Counted:
    """Counts every heap comparison. sign=-1 gives a max-heap."""
    __slots__ = ("d", "sign", "s")

    def __init__(self, d, sign, s):
        self.d, self.sign, self.s = d, sign, s

    def __lt__(self, o):
        self.s.count()
        return self.d * self.sign < o.d * o.sign


def oracle_kth(array, k, s):
    """Places the whole array by comparison, reads the k-th position."""
    a = list(array)
    for i in range(len(a)):
        least = i
        for j in range(i + 1, len(a)):
            s.count()
            if a[j] < a[least]:
                least = j
        a[i], a[least] = a[least], a[i]
    return a[k - 1]


def pattern_heap(array, k, s):
    """Keeps a k-sized max-heap; the top is the k-th smallest value."""
    heap = []
    for x in array:
        heapq.heappush(heap, Counted(x, -1, s))
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0].d


def pattern_distinct_value(array, k, s):
    """SAME structure, DIFFERENT question: the k-th smallest DISTINCT value."""
    heap, seen = [], set()
    for x in array:
        s.count()
        if x in seen:
            continue
        seen.add(x)
        heapq.heappush(heap, Counted(x, -1, s))
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0].d if len(heap) == k else None


K40 = corpus()
print("corpus: 40 arrays x 12 values | arrays with a duplicate value:",
      sum(1 for k in K40 if len(set(k["array"])) < LENGTH))
print(" k  pattern            diverging/40  pattern  oracle   ratio")
for k in (3, 4, 6, 8):
    for ad, pattern in (("k-th element     ", pattern_heap),
                        ("k-th distinct val", pattern_distinct_value)):
        diverging, pk, ok = 0, 0, 0
        for record in K40:
            s1, s2 = Counter(), Counter()
            a = pattern(record["array"], k, s1)
            b = oracle_kth(record["array"], k, s2)
            pk, ok = pk + s1.step, ok + s2.step
            diverging += (a != b)
        print(f"{k:2d}  {ad}  {diverging:10d}  {pk:5d}  {ok:5d}  {ok / pk:5.2f}")
print()
first = K40[0]["array"]
print("input 1          :", first)
print("  sorted order   :", sorted(first))
print("  oracle k=4     :", oracle_kth(first, 4, Counter()))
print("  heap k=4       :", pattern_heap(first, 4, Counter()))
print("  distinct k=4   :", pattern_distinct_value(first, 4, Counter()))
```

```
corpus: 40 arrays x 12 values | arrays with a duplicate value: 37
 k  pattern            diverging/40  pattern  oracle   ratio
 3  k-th element                0   1440   2640   1.83
 3  k-th distinct val           9   1640   2640   1.61
 4  k-th element                0   1559   2640   1.69
 4  k-th distinct val          17   1723   2640   1.53
 6  k-th element                0   1348   2640   1.96
 6  k-th distinct val          27   1503   2640   1.76
 8  k-th element                0   1292   2640   2.04
 8  k-th distinct val          30   1381   2640   1.91

input 1          : [-8, -5, 2, -1, 2, 5, 4, 1, 16, 17, 6, -1]
  sorted order   : [-8, -5, -1, -1, 1, 2, 2, 4, 5, 6, 16, 17]
  oracle k=4     : -1
  heap k=4       : -1
  distinct k=4   : 1
```

The heap pattern matches the oracle on **40 of 40 inputs** at all four k values; the ratio
falls between 1.69 and 2.04. The distinct-value form diverges more as k grows: **9, 17, 27,
30**.

The first input's difference shows this at a glance. Sorted order is `[-8, -5, -1, -1, 1,
...]`; the fourth element is **−1**, because −1 appears twice. The fourth **distinct** value
is **1**. Both answers are correct — but to two **different questions**. This is not a flaw
in the pattern, it is the question shifting.

## The Question Looks the Same, But Is Not

To show that the divergence really comes from duplicates, a control is needed: the same
measurement, repeated on a corpus with duplicates stripped out. If there are no duplicates,
the two questions should become **identical** and the divergence should be zero.

**PP51.** The control corpus consists of the same arrays' distinct values; it comes from no
other generator. Because the arrays shrink, only k=3 and k=6 are measured.
**PP52.** The second corpus comes from seed `20260219` and is swept with the same four k
values.

```python
import heapq


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def corpus(seed, n=40, length=12):
    r = generator(seed)
    return [[r(30) - 9 for _ in range(length)] for _ in range(n)]


def oracle_kth(array, k):
    a = list(array)
    for i in range(len(a)):
        least = i
        for j in range(i + 1, len(a)):
            if a[j] < a[least]:
                least = j
        a[i], a[least] = a[least], a[i]
    return a[k - 1]


def pattern_heap(array, k):
    heap = []
    for x in array:
        heapq.heappush(heap, -x)
        if len(heap) > k:
            heapq.heappop(heap)
    return -heap[0]


def pattern_distinct_value(array, k):
    heap, seen = [], set()
    for x in array:
        if x in seen:
            continue
        seen.add(x)
        heapq.heappush(heap, -x)
        if len(heap) > k:
            heapq.heappop(heap)
    return -heap[0] if len(heap) == k else None


print("seed       k  k-th element  k-th distinct value  distinct-value ratio")
for seed in (20260218, 20260219):
    K = corpus(seed)
    for k in (3, 4, 6, 8):
        e = sum(1 for d in K if pattern_heap(d, k) != oracle_kth(d, k))
        f = sum(1 for d in K if pattern_distinct_value(d, k) != oracle_kth(d, k))
        print(f"{seed}  {k:2d}  {e:13d}  {f:17d}  {f / 40:16.4f}")
print()
print("same measurement on a duplicate-free corpus (each array's distinct values):")
for seed in (20260218, 20260219):
    K = [sorted(set(d)) for d in corpus(seed)]
    for k in (3, 6):
        f = sum(1 for d in K if pattern_distinct_value(d, k) != oracle_kth(d, k))
        print(f"  {seed}  k={k}  diverging {f}/40")
```

```
seed       k  k-th element  k-th distinct value  distinct-value ratio
20260218   3              0                  9            0.2250
20260218   4              0                 17            0.4250
20260218   6              0                 27            0.6750
20260218   8              0                 30            0.7500
20260219   3              0                 12            0.3000
20260219   4              0                 24            0.6000
20260219   6              0                 28            0.7000
20260219   8              0                 32            0.8000

same measurement on a duplicate-free corpus (each array's distinct values):
  20260218  k=3  diverging 0/40
  20260218  k=6  diverging 0/40
  20260219  k=3  diverging 0/40
  20260219  k=6  diverging 0/40
```

The control is decisive: on a corpus with duplicates stripped out, diverging inputs are
**zero** on all four measurements. The source of divergence is not the pattern, it is the
duplicates in the corpus and **the question's definition**.

In the second corpus, ratios fall between 0.30 and 0.80; in the first, between 0.2250 and
0.7500 — the **same order of magnitude**, rising in the same direction. The result does not
depend on the corpus. The heap pattern's k-th-element column is **zero** on all eight of
eight rows.

The warning that follows from this is the topic's most practical one. The difference between
the two questions is **a single line in code**, and that line looks like an improvement: not
putting the same value into the heap twice shrinks the heap and lowers the step count. On
none of the eight rows is there any sign that this line is wrong; the only sign is in the
oracle's column.

## Partitioning's Precondition Is Pivot Choice

The second pattern **partitions** the array around a **pivot**: values smaller than the pivot
move left, larger ones move right, and the pivot settles into its final position. If that
position is k, the answer is found; if not, the search continues on one side only. The
partitioning procedure was established inside quicksort in the Algorithms course; it is not
repeated here.

This pattern's precondition touches not correctness but **step count**: the pivot must
actually split the array in two. If the pivot always lands on the array's edge value, the
split advances by one element at a time and the search space shrinks slowly.

**PP53.** Two pivot choices are compared: the section's **first** value and its **middle**
value.
**PP54.** k is the array's middle (`length // 2`), that is, the position that demands the most
partitioning.
**PP55.** The measurement is repeated at two lengths: 12 and 60 values. The sorted pool is the
same arrays in sorted form.

```python
def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def corpus(seed, n=40, length=12):
    r = generator(seed)
    return [[r(30) - 9 for _ in range(length)] for _ in range(n)]


class Counter:
    def __init__(self):
        self.step = 0

    def count(self):
        self.step += 1


def oracle_kth(array, k, s):
    a = list(array)
    for i in range(len(a)):
        least = i
        for j in range(i + 1, len(a)):
            s.count()
            if a[j] < a[least]:
                least = j
        a[i], a[least] = a[least], a[i]
    return a[k - 1]


def pattern_partition(array, k, pivot_first, s):
    """Selection by partitioning. PRECONDITION: pivot choice must not coincide with input order."""
    a, left, right = list(array), 0, len(array) - 1
    while left < right:
        p = left if pivot_first else (left + right) // 2
        a[p], a[right] = a[right], a[p]
        pivot, i = a[right], left
        for j in range(left, right):
            s.count()
            if a[j] < pivot:
                a[i], a[j] = a[j], a[i]
                i += 1
        a[i], a[right] = a[right], a[i]
        if k - 1 == i:
            return a[i]
        if k - 1 < i:
            right = i - 1
        else:
            left = i + 1
    return a[left]


print("length  input     pivot      diverging/40  pattern   oracle    ratio")
for length in (12, 60):
    K = corpus(20260218, 40, length)
    for gad, prepare in (("unsorted", list), ("sorted  ", sorted)):
        for pad, pivot_first in (("first value", True), ("middle val ", False)):
            diverging, pk, ok = 0, 0, 0
            for array in K:
                d = prepare(array)
                s1, s2 = Counter(), Counter()
                a = pattern_partition(d, length // 2, pivot_first, s1)
                b = oracle_kth(d, length // 2, s2)
                pk, ok = pk + s1.step, ok + s2.step
                diverging += (a != b)
            print(f"{length:6d}  {gad}  {pad}  {diverging:10d}  {pk:5d}"
                  f"  {ok:6d}  {ok / pk:6.2f}")
```

```
length  input     pivot      diverging/40  pattern   oracle    ratio
    12  unsorted  first value           0    943    2640    2.80
    12  unsorted  middle val            0   1073    2640    2.46
    12  sorted    first value           0   2040    2640    1.29
    12  sorted    middle val            0    473    2640    5.58
    60  unsorted  first value           0   6726   70800   10.53
    60  unsorted  middle val            0   7346   70800    9.64
    60  sorted    first value           0  53400   70800    1.33
    60  sorted    middle val            0   3407   70800   20.78
```

Eight of eight rows give zero diverging inputs. Selection by partitioning gives the correct
answer regardless of pivot; this pattern's precondition has nothing to do with correctness.

The step column is striking on 60-value sorted input: choosing the first value as pivot
spends **53,400** steps, choosing the middle value spends **3407**. A single-line choice
multiplies the step count by **15.7 times** and drops the pattern's ratio from 20.78 to
**1.33** — the pattern becomes nearly as expensive as the oracle.

This row is another face of the topic's second claim: **a broken precondition does not always
mean a wrong answer.** Sometimes it is only the step count that explodes, and it does not
require broken data to explode — here the input is **sorted**, that is, in its most orderly
state. What breaks the pattern is not the data's disorder, it is the pivot rule
**coinciding** with that order.

## Three Numbers

| Metric | Oracle | Pattern | Diverging input |
|---|---|---|---|
| Heap, k-th element (k=6) | 2640 steps | 1348 steps | **0/40** |
| Heap, k-th distinct value (k=6) | 2640 steps | 1503 steps | **27/40** |
| Partitioning, 60 values, unsorted, middle pivot | 70,800 steps | 7346 steps | **0/40** |
| Partitioning, 60 values, sorted, first pivot | 70,800 steps | 53,400 steps | **0/40** |

The first two rows show that correctness depends on the question's definition; the last two
show that performance depends on the pivot rule. In none of the four rows does the step
column signal the diverging-input column: the row with the lowest step count is correct, the
row with the second-lowest step count is wrong on 27 inputs.

## Summary

- The k-th element question generalizes the median; keeping a k-sized heap gives the answer
  without placing the whole array.
- The heap pattern matches the oracle on 40 of 40 inputs at all four k values; the ratio
  falls between 1.69 and 2.04.
- On duplicate values, "the k-th element" and "the k-th distinct value" are separate
  questions; the second diverges from the oracle on **27 inputs** for k=6, and the difference
  is a single line of code.
- On a duplicate-stripped control corpus, diverging inputs are zero on all four measurements;
  the source is not the pattern, it is the question's definition.
- Selection by partitioning is correct with any pivot, but on 60-value sorted input, choosing
  the first value as pivot raises the step count from 3407 to 53,400 and drops the ratio from
  20.78 to 1.33.

## Next Step

All seven of this topic's patterns so far worked on one-dimensional data: an array, a stream,
a successor chain. The last pattern handles data in **two dimensions**. In a grid, connected
groups of cells are searched for, and the traversal is done with the Data Structures course's
breadth-first and depth-first search — those two procedures are not repeated, they are called
directly. The precondition is again a choice of definition: **what connectivity means.** The
next lesson counts how many different answers two connectivity definitions produce on the
same grid.