# Selection in Sorted Matrix

# 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.

```id="ssm1"
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.

```id="ssm2"
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

```id="ssm3"
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
```

```id="ssm4"
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
}
```