Kth Smallest Element in a Sorted Matrix

Problem#

An n x n matrix where each row and each column is sorted ascending. Return the kth smallest element.

Examples#

matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 → 13

Constraints#

1 <= n <= 300, 1 <= k <= n^2.

Approach#

K-way merge — push first column into a min-heap, pop k times. O(k log n).

Binary search on value — counting elements ≤ mid in O(n) per probe via staircase walk. O(n log(max - min)). Often faster in practice.

Solution#

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int lo = matrix[0][0], hi = matrix[n - 1][n - 1];
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int count = 0, c = n - 1;
            for (int r = 0; r < n; ++r) {
                while (c >= 0 && matrix[r][c] > mid) --c;
                count += c + 1;
            }
            if (count < k) lo = mid + 1; else hi = mid;
        }
        return lo;
    }
};

func kthSmallest(matrix [][]int, k int) int {
    n := len(matrix)
    lo, hi := matrix[0][0], matrix[n-1][n-1]
    for lo < hi {
        mid := lo + (hi-lo)/2
        count, c := 0, n-1
        for r := 0; r < n; r++ {
            for c >= 0 && matrix[r][c] > mid {
                c--
            }
            count += c + 1
        }
        if count < k {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

from typing import List

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)
        lo, hi = matrix[0][0], matrix[n - 1][n - 1]
        while lo < hi:
            mid = lo + (hi - lo) // 2
            count, c = 0, n - 1
            for r in range(n):
                while c >= 0 and matrix[r][c] > mid:
                    c -= 1
                count += c + 1
            if count < k:
                lo = mid + 1
            else:
                hi = mid
        return lo

function kthSmallest(matrix, k) {
    const n = matrix.length;
    let lo = matrix[0][0], hi = matrix[n - 1][n - 1];
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        let count = 0, c = n - 1;
        for (let r = 0; r < n; r++) {
            while (c >= 0 && matrix[r][c] > mid) c--;
            count += c + 1;
        }
        if (count < k) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int lo = matrix[0][0], hi = matrix[n - 1][n - 1];
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int count = 0, c = n - 1;
            for (int r = 0; r < n; r++) {
                while (c >= 0 && matrix[r][c] > mid) c--;
                count += c + 1;
            }
            if (count < k) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}

function kthSmallest(matrix: number[][], k: number): number {
    const n = matrix.length;
    let lo = matrix[0][0], hi = matrix[n - 1][n - 1];
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        let count = 0, c = n - 1;
        for (let r = 0; r < n; r++) {
            while (c >= 0 && matrix[r][c] > mid) c--;
            count += c + 1;
        }
        if (count < k) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

Editorial#

Binary search on the value space: the answer is the smallest value v such that at least k matrix entries are ≤ v. Counting ≤ v uses the staircase walk: start at top-right; if the current entry > v, go down; else add the column count and step left. The walk is O(n).

Complexity#

Time: O(n log(max - min)).
Space: O(1).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#