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

Kth Smallest Element in a Sorted Matrix

Explore solving the problem of finding the kth smallest element in an n by n matrix where each row and column is sorted. Understand how to apply the K-way merge pattern to efficiently merge sorted lists and develop a solution that handles constraints and duplicates. This lesson helps you implement and optimize your approach in Go, preparing you for coding interviews that test matrix and sorting skills.

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