Kth Smallest Element in a Sorted Matrix

Medium Binary Search Binary Search on Answer Space Original on LeetCode

Reported atPhonePe

Kth Smallest Element in a Sorted Matrix is a medium binary search problem solved with the binary search on answer space pattern. The best approach, optimal (binary search on the value), runs in O(n log R) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (flatten and sort) up.

Problem

You get an n x n integer matrix whose rows are each sorted in non-decreasing order from left to right, and whose columns are each sorted in non-decreasing order from top to bottom. You also get an integer k.

Return the k-th smallest value among all n² entries, counting duplicates separately (it is the k-th value of the fully sorted list, not the k-th distinct value).

Try to use less than O(n²) extra memory.

Examples

Example 1

Input
matrix = [[2, 6, 9], [3, 8, 12], [7, 10, 15]], k = 5
Output
8
Why
In sorted order the values are 2, 3, 6, 7, 8, 9, 10, 12, 15; the fifth one is 8.

Example 2

Input
matrix = [[-4, -4], [-1, 3]], k = 2
Output
-4
Why
Duplicates count separately: the two smallest values are both -4.

Constraints

  • n == matrix.length == matrix[i].length, 1 <= n <= 300
  • -10^9 <= matrix[i][j] <= 10^9
  • Every row and every column is sorted in non-decreasing order.
  • 1 <= k <= n²

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (flatten and sort)O(n² log n)O(n²)
Min-heap k-way mergeO(k log n)O(n)
Optimal (binary search on the value)O(n log R)O(1)

1Brute force (flatten and sort)

TimeO(n² log n)Sorting n² values costs O(n² log n²) = O(n² log n).
SpaceO(n²)The flattened copy.

Copy all n² values into one array, sort it, and return the element at index k - 1.

  1. Copy every entry into a 1D array of size n².
  2. Sort the array.
  3. Return arr[k - 1].
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int[] all = new int[n * n];
        int idx = 0;
        for (int[] row : matrix) {
            for (int v : row) all[idx++] = v;
        }
        Arrays.sort(all);
        return all[k - 1];
    }
}

2Min-heap k-way merge

TimeO(k log n)k heap operations, each O(log n) because the heap never holds more than n entries.
SpaceO(n)At most one entry per row in the heap.

Treat each row as a sorted list and merge them with a min-heap, like merging k sorted lists. Seed the heap with the first element of each row. Pop the smallest k - 1 times, each time pushing the next element of the same row. The top of the heap is then the k-th smallest.

  1. Push (matrix[r][0], r, 0) for each row r < min(n, k).
  2. Repeat k - 1 times: pop (value, r, c); if c + 1 < n, push (matrix[r][c + 1], r, c + 1).
  3. Return the value at the top of the heap.
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        for (int r = 0; r < Math.min(n, k); r++) heap.add(new int[] { matrix[r][0], r, 0 });
        for (int i = 0; i < k - 1; i++) {
            int[] top = heap.poll();
            int r = top[1], c = top[2];
            if (c + 1 < n) heap.add(new int[] { matrix[r][c + 1], r, c + 1 });
        }
        return heap.peek()[0];
    }
}

3Optimal (binary search on the value)

TimeO(n log R)Each count is O(n) (at most 2n steps), and the binary search runs about log2(2 * 10^9) ≈ 31 times, where R is the value range.
SpaceO(1)Only a few variables.

The answer is a value between matrix[0][0] and matrix[n-1][n-1]. For a guess x, count the entries <= x with a staircase walk: start at the bottom-left; if the entry is <= x, the whole column above it is too, so add row + 1 and step right; otherwise step up. The count only grows as x grows, so binary search for the smallest x whose count is at least k. That smallest value is always an entry of the matrix. Use 64-bit bounds so lo + hi cannot overflow.

  1. lo = matrix[0][0], hi = matrix[n-1][n-1] (as 64-bit numbers).
  2. While lo < hi: mid = lo + (hi - lo) / 2; count entries <= mid with the staircase walk.
  3. If count >= k, set hi = mid; otherwise lo = mid + 1.
  4. Return lo.
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        long lo = matrix[0][0], hi = matrix[n - 1][n - 1];
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (countAtMost(matrix, mid) >= k) hi = mid;
            else lo = mid + 1;
        }
        return (int) lo;
    }

    private int countAtMost(int[][] matrix, long x) {
        int n = matrix.length;
        int row = n - 1, col = 0, count = 0;
        while (row >= 0 && col < n) {
            if (matrix[row][col] <= x) {
                count += row + 1;
                col++;
            } else {
                row--;
            }
        }
        return count;
    }
}

Edge cases to test

  • A 1 x 1 matrix
  • k = 1 (top-left corner) or k = n² (bottom-right corner)
  • Many duplicates, or every value equal
  • Values near -10^9 and 10^9, where (lo + hi) overflows a 32-bit int

Hints

Hint 1

The rows are sorted lists. How would you merge n sorted lists and stop after k values?

Hint 2

Instead of searching for a position, search over values: for a guess x, how many entries are <= x?

Hint 3

Counting entries <= x takes O(n) with a staircase walk from the bottom-left corner. Binary search for the smallest x whose count is at least k.

FAQ

What is the best time complexity for Kth Smallest Element in a Sorted Matrix?

Optimal (binary search on the value) runs in O(n log R) time and O(1) extra space. Each count is O(n) (at most 2n steps), and the binary search runs about log2(2 * 10^9) ≈ 31 times, where R is the value range.

Which pattern does Kth Smallest Element in a Sorted Matrix use?

It is a binary search problem that uses the binary search on answer space pattern. Other problems with the same pattern: Koko Eating Bananas, Minimum Number of Days to Make m Bouquets, Separate Squares I.

Is there a brute force solution for Kth Smallest Element in a Sorted Matrix?

Yes. Brute force (flatten and sort) takes O(n² log n) time and O(n²) space. Copy all n² values into one array, sort it, and return the element at index k - 1.

Which edge cases should I test for Kth Smallest Element in a Sorted Matrix?

A 1 x 1 matrix; k = 1 (top-left corner) or k = n² (bottom-right corner); Many duplicates, or every value equal; Values near -10^9 and 10^9, where (lo + hi) overflows a 32-bit int.