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

Kth Smallest Element in a Sorted Matrix

Understand how to identify the kth smallest element in a sorted n by n matrix where each row and column is in ascending order. Explore merging strategies to efficiently solve this problem and apply your knowledge with hands-on coding practice.

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 the following coding playground:

Java
usercode > KthSmallest.java
import java.util.*;
class KthSmallest {
    public static int kthSmallestElement(int[][] matrix, int k) {
        
        // Replace this placeholder return statement with your code
        return -1;
    }
        
}
Kth Smallest Element in a Sorted Matrix