Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in Python

Kth Smallest Element in a Sorted Matrix

Explore how to identify the kth smallest element in an n by n matrix where rows and columns are sorted. Understand the problem constraints and apply k-way merge techniques to solve efficiently. This lesson helps you practice logical problem solving and implement your solution in code.

We'll cover the following...

Statement

Find the kthk^{th} smallest element in an (n×n)(n \times n) matrix, where each row and column of the matrix is sorted in ascending order.

Although there can be repeating values in the matrix, each element is considered unique and, therefore, contributes to calculating the kthk^{th} smallest element.

Constraints:

  • n ==== matrix.length
  • n ==== matrix[i].length
  • 1≤1\leq n ≤100\leq100
  • −103≤-10^3\leq matrix[i][j] ≤103\leq10^3
  • 1≤1\leq k ≤n2\leq n^2

Examples

Test your understanding of the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

KthK^{th} Smallest Element in a Sorted Matrix

1.

What is the correct output if the following matrix and value of k are given as input?

matrix=[159101113121315]matrix = \begin{bmatrix} 1 & 5 & 9 \\ 10 & 11 & 13 \\ 12 & 13 & 15 \\ \end{bmatrix}

k=8k = 8

A.

1212

B.

1313

C.

1414

1 / 3

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4

Try it yourself

Implement your solution in main.py in the following coding playground.

Python
usercode > main.py
from heapq import *



def kth_smallest_element(matrix, k):



    # Replace this placeholder return statement with your code

    return -1
Kth Smallest Element in a Sorted Matrix