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

Kth Smallest Element in a Sorted Matrix

Understand how to solve the problem of finding the kth smallest element in a sorted matrix where each row and column is ascending. This lesson guides you through the logic and implementation using a k-way merge approach, helping you grasp core problem-solving techniques essential for coding interviews.

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 is 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 KthSmallest.cpp in the following coding playground.

C++
usercode > KthSmallest.cpp
#include <iostream>
#include <vector>
#include <queue>
int KSmallestNumber(vector<vector<int>> matrix, int k)
{    
    // Replace this placeholder return statement with your code
    return -1;
}
Kth Smallest Element in a Sorted Matrix