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.

Purchase Premium to Access

This article is only available to Premium users.

Purchase Premium

The best mocks on the market.

Now up to 15% off

Learn More

Reading Progress

On This Page

Building Intuition

Approach 1: Brute Force (Flatten and Sort)

Can We Use Binary Search?

Observation

Binary Search on the Value

Counting Elements ≤ mid

Putting It Together

Walkthrough

Solution

Why Does This Work?

Alternate Solution: Min-Heap

Binary Search

Kth Smallest Element in a Sorted Matrix

DESCRIPTION (inspired by Leetcode.com)

Purchase Premium to Access

This article is only available to Premium users.

The best mocks on the market.

Questions

Learn

Links

Legal

Contact