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

Kth Smallest Element in a Sorted Matrix

Explore how to identify the kth smallest element in an n by n sorted matrix by applying the K-way merge pattern. This lesson helps you develop a strategic approach to efficiently merge and sort multiple lists, deepening your understanding of solving coding interview problems involving sorted data structures.

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 main.go in the following coding playground. We have provided a useful code template in the other file that you may build on to solve this problem.

Go
usercode > main.go
package main



func kthSmallestElement(matrix [][]int, k int) int {

    

	// Replace this placeholder return statement with your code

    return -1

}
Kth Smallest Element in a Sorted Matrix