Selection in Sorted Matrix

Selection in Sorted Matrix finds the k-th smallest value in a matrix where every row and every column is sorted in nondecreasing order.

The matrix ordering gives enough structure to count how many values are less than or equal to a candidate. This allows binary search over the value range.

Problem

Given an $m \times n$ matrix $A$ such that:

$$ A[i][j] \le A[i][j + 1] $$

and

$$ A[i][j] \le A[i + 1][j] $$

find the k-th smallest value, using 1-based rank.

Algorithm

Binary search over values between the smallest and largest matrix entries. For each midpoint, count how many entries are less than or equal to it.

selection_in_sorted_matrix(A, k):
    low = A[0][0]
    high = A[m - 1][n - 1]

    while low < high:
        mid = floor((low + high) / 2)
        count = count_less_equal(A, mid)

        if count < k:
            low = mid + 1
        else:
            high = mid

    return low

To count efficiently, start from the bottom-left corner.

count_less_equal(A, x):
    row = m - 1
    col = 0
    count = 0

    while row >= 0 and col < n:
        if A[row][col] <= x:
            count = count + row + 1
            col = col + 1
        else:
            row = row - 1

    return count

Example

Let:

$$ A = \begin{bmatrix} 1 & 5 & 9
10 & 11 & 13
12 & 13 & 15 \end{bmatrix} $$

For $k = 8$, the sorted order is:

$$ [1, 5, 9, 10, 11, 12, 13, 13, 15] $$

The 8-th smallest value is:

$$ 13 $$

Correctness

For any candidate value $x$, count_less_equal returns the number of matrix entries at most $x$. Because rows and columns are sorted, the set of entries less than or equal to $x$ forms a monotone region.

If fewer than $k$ values are at most $x$, then the answer must be greater than $x$. Otherwise, the answer is at most $x$. Binary search maintains this invariant until the smallest feasible value remains.

Complexity

part	cost
counting pass	$O(m + n)$
value binary search	$O(\log R)$
total time	$O((m + n)\log R)$
space	$O(1)$

Here $R$ is the numeric value range:

$$ R = A[m-1][n-1] - A[0][0] + 1 $$

When to Use

Use this method when:

• rows and columns are sorted
• values are numeric and bounded
• duplicates are allowed
• you need the k-th value, not the sorted list

For very large value ranges or non-integer keys, heap based k-way merging may be preferable.

Implementation

def count_less_equal(matrix, x):
    m = len(matrix)
    n = len(matrix[0])

    row = m - 1
    col = 0
    count = 0

    while row >= 0 and col < n:
        if matrix[row][col] <= x:
            count += row + 1
            col += 1
        else:
            row -= 1

    return count

def selection_in_sorted_matrix(matrix, k):
    low = matrix[0][0]
    high = matrix[-1][-1]

    while low < high:
        mid = (low + high) // 2

        if count_less_equal(matrix, mid) < k:
            low = mid + 1
        else:
            high = mid

    return low

func countLessEqual(matrix [][]int, x int) int {
	m := len(matrix)
	n := len(matrix[0])

	row := m - 1
	col := 0
	count := 0

	for row >= 0 && col < n {
		if matrix[row][col] <= x {
			count += row + 1
			col++
		} else {
			row--
		}
	}

	return count
}

func SelectionInSortedMatrix(matrix [][]int, k int) int {
	low := matrix[0][0]
	high := matrix[len(matrix)-1][len(matrix[0])-1]

	for low < high {
		mid := low + (high-low)/2

		if countLessEqual(matrix, mid) < k {
			low = mid + 1
		} else {
			high = mid
		}
	}

	return low
}