K-th Element

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.

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.

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.

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.