Kth Smallest Element in a Sorted Matrix

Medium
367.

Kth Smallest Element in a Sorted Matrix

Kth Smallest Element in a Sorted Matrix is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google, Meta and Uber interviews.

Given an n × n matrix where each row and each column is sorted in ascending order, return the k-th smallest element in the matrix.

Note this is the k-th smallest in sorted order, counting duplicates separately — not the k-th distinct value.

Example 1

Input
matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output
13
Explanation
Sorted, the matrix reads 1,5,9,10,11,12,13,13,15.

Example 2

Input
matrix = [[-5]], k = 1
Output
-5

Example 3

Input
matrix = [[1,2],[1,3]], k = 2
Output
1

Constraints

  • 1 <= matrix.length <= 8
  • matrix[i].length == matrix.length
  • -1000 <= matrix[i][j] <= 1000
  • 1 <= k <= n²

Follow-up: Flattening and sorting is O(n² log n). Can you do it in O(n log(max - min)) using binary search on the answer?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(matrix, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Kth Smallest Element in a Sorted Matrix — Problem & Solution

Kth Smallest Element in a Sorted Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Kth Smallest Element in a Sorted Matrix is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google, Meta and Uber interviews.

Problem statement

Given an n × n matrix where each row and each column is sorted in ascending order, return the k-th smallest element in the matrix.

Note this is the k-th smallest in sorted order, counting duplicates separately — not the k-th distinct value.

Example 1

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: Sorted, the matrix reads 1,5,9,10,11,12,13,13,15.

Example 2

Input: matrix = [[-5]], k = 1
Output: -5

Example 3

Input: matrix = [[1,2],[1,3]], k = 2
Output: 1

Constraints

  • 1 <= matrix.length <= 8
  • matrix[i].length == matrix.length
  • -1000 <= matrix[i][j] <= 1000
  • 1 <= k <= n²

Follow-up: Flattening and sorting is O(n² log n). Can you do it in O(n log(max - min)) using binary search on the answer?

Hints for Kth Smallest Element in a Sorted Matrix

  1. Hint 1

    Flattening and sorting is correct and simple — start there.

  2. Hint 2

    A min-heap seeded with the first column pops the smallest element k times in O(k log n).

  3. Hint 3

    Best: binary search on the value, counting how many entries are at most the midpoint using the row/column sortedness.

How to solve Kth Smallest Element in a Sorted Matrix

Flatten and sort, then index k - 1.

Approach

  1. Collect all n² values.
  2. Sort and return the (k-1)-th.

Why it works

The k-th smallest counting duplicates is by definition position k - 1 in the sorted multiset.

Complexity

  • Time — O(n² log n)
  • Space — O(n²)

Pitfalls

  • A min-heap seeded with the first column pops k times in O(k log n); binary search on the value with a staircase count is O(n log(range)).

Reference solution

Python

def kthSmallest(matrix, k: int) -> int:
    flat = [v for row in matrix for v in row]
    flat.sort()
    return flat[k - 1]

Java

public static int kthSmallest(int[][] matrix, int k) {
    int n = matrix.length;
    int[] flat = new int[n * n];
    int idx = 0;
    for (int[] row : matrix) {
        for (int v : row) flat[idx++] = v;
    }
    Arrays.sort(flat);
    return flat[k - 1];
}

C++

int kthSmallest(vector<vector<int>>& matrix, int k) {
    vector<int> flat;
    for (const auto& row : matrix) {
        for (int v : row) flat.push_back(v);
    }
    sort(flat.begin(), flat.end());
    return flat[k - 1];
}

JavaScript

var kthSmallest = function(matrix, k) {
    const flat = [];
    for (let r = 0; r < matrix.length; r++) {
        for (let c = 0; c < matrix[r].length; c++) flat.push(matrix[r][c]);
    }
    flat.sort(function(a, b) { return a - b; });
    return flat[k - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms