Kth Smallest Element in a Sorted Matrix

Explore how to identify the kth smallest element in an n by n matrix where each row and column is sorted. Learn to apply the K-way merge strategy to solve this problem efficiently and implement your solution in a coding environment.

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