Interview Notes Search

This page uses the site's newer layout, so only the problem statement and the section outline survive in the public payload — open the original for the rest.

Binary Search

Kth Smallest Element in a Sorted Matrix

medium

DESCRIPTION (inspired by Leetcode.com)

You're given a square grid (n × n matrix) where each row is sorted in ascending order from left to right, and each column is also sorted in ascending order from top to bottom.

Given the matrix and an integer k, find the k-th smallest element among all elements in the matrix.

Note: k is 1-indexed, meaning k = 1 returns the smallest element.

Example 1 :

Input:

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

Output: 13

Explanation: The elements in sorted order are [1,5,9,10,11,12,13,13,15]. The 8th smallest element is 13.

Example 2 :

Input:

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

Output: -5

Explanation: The matrix has only one element, so it's the 1st smallest.

Building Intuition

Approach 1: Brute Force (Flatten and Sort)

Observation

Binary Search on the Value

Counting Elements ≤ mid

Putting It Together

Walkthrough

Solution

Why Does This Work?

Alternate Solution: Min-Heap