Kth Smallest Element In A Sorted Matrix · Interview Problem

Back to problems

Leetcode

Medium

Arrays

Binary Search

Heaps

Matrices

Google

Microsoft

Kth Smallest Element In A Sorted Matrix

Find the $k$ th smallest value in an $n \times n$ matrix where each row and column is sorted in non-decreasing order.

Acceptance 100%

Start Practice

Problem Statement

Given an $n \times n$ matrix of integers, each row sorted from left to right and each column sorted from top to bottom, return the $k$ th smallest element in the matrix.

The matrix may contain duplicate values, and the $k$ th smallest element is counted by position in the sorted order, not by distinct value.

Input Format

A 2D integer matrix matrix of size n x n
An integer k

The matrix satisfies:

each row is sorted in non-decreasing order
each column is sorted in non-decreasing order

Output Format

Return the integer value of the $k$ th smallest element in the matrix.

Constraints

$1 \le n \le 300$
$1 \le k \le n^2$
$-10^9 \le matrix[i][j] \le 10^9$
Rows and columns are sorted in non-decreasing order

Examples

Sample cases returned by the problem API.

Example 1

Input

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

Output

Explanation

The sorted order is [1,5,9,10,11,12,13,13,15], so the 8th smallest value is 13.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress