Kth Smallest Element in a Sorted Matrix

Explore how to solve the problem of finding the kth smallest element in an n by n sorted matrix. Understand the K-way merge approach to handle sorted rows and columns efficiently, and implement the solution with practice exercises to strengthen your algorithmic skills.

We'll cover the following...

Statement
Examples
Test your understanding of the problem
Figure it out!
Try it yourself

Statement

Find the $k^{th}$ smallest element in an $(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 $k^{th}$ smallest element.

Constraints:

n $==$ matrix.length
n $==$ matrix[i].length
$1\leq$ n $\leq100$
$-10^3\leq$ matrix[i][j] $\leq10^3$
$1\leq$ k $\leq n^2$

Examples

JavaScript

usercode > Solution.js

import { MinHeap, MaxHeap } from "./Heap.js";

/* The following definition is for MinHeap.

  You can use the same methods for MaxHeap.
  class MinHeap {

    size();          // return number of elements
    peek();          // return top element without removing
    push(val);       // insert element
    pop();           // remove and return top element
  }
*/

function kthSmallestNumber(matrix, k){

    // Replace this placeholder return statement with your code
    return -1;
}

export {
    kthSmallestNumber
}

Kth Smallest Element in a Sorted Matrix

Kth Smallest Element in a Sorted Matrix

Statement

Examples

Test your understanding of the problem

Figure it out!

Try it yourself