Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach 1: By using a one-dimensional array
2.1.
Algorithm
2.2.
Code
2.3.
Sample Input
2.4.
Sample Output
2.5.
Complexity Analysis
2.5.1.
Time Complexity
2.5.2.
Space Complexity
3.
Approach 2: By using an inbuilt Priority Queue in C++
3.1.
Algorithm
3.2.
Code
3.3.
Sample Input
3.4.
Sample Output
3.5.
Time and Space Complexities
4.
Approach 3: By using Binary Search Technique
4.1.
Methodology
4.2.
Algorithm
4.3.
Dry Run
4.4.
Code
4.5.
Sample Input
4.6.
Sample Output
4.7.
Complexity Analysis
4.7.1.
Time Complexity
4.7.2.
Space Complexity
5.
Frequently Asked Questions
5.1.
How do you find the kth element in a sorted matrix?
5.2.
How do you find the kth smallest element in a 2D array?
5.3.
How do you find the smallest number in a matrix?
5.4.
What are the different strategies that can be used to find Kth smallest element in a row-wise and column-wise sorted 2D array?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Kth Smallest Element in a Row-Wise and Column-Wise sorted 2D Array

gp-icon
Competitive programming
Free guided path
16 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

Arrays are one of the most elementary data structures. They are probably one of the first data structures that everybody learns when they begin their programming journey. There are a lot of popular problems formulated on the concepts that require knowledge of arrays and some popular Algorithms as well. In this article, we are going to discuss one such problem.

kth smallest element in a sorted matrix

The Kth Smallest Element in a Sorted Matrix is pretty much self-explanatory. It means we have to find a number greater than or equal to exactly the K-1 elements of the matrix.

 

Example

Input Matrix

This matrix is row-wise and column-wise sorted, and if we take K=8, then the Kth smallest element here will be 13.

Because there are exactly 7 (K-1) numbers that are less than or equal to 13, i.e., (1, 5, 9, 10, 11, 12, 13).
 

For the task of finding Kth smallest element in a row-wise and column-wise sorted 2D array, I’ll explain three different approaches in this blog post.

  1. By using a one-dimensional array
  2. By using an inbuilt priority queue or a HashMap
  3. By using Binary Search Technique

 

Let’s explore these, one by one!!

Recommended: Do try the Problem yourself first before moving on to the Solution

Also read, Euclid GCD Algorithm

Approach 1: By using a one-dimensional array

Algorithm

The simplest method for finding the Kth smallest element in a row-wise and column-wise sorted 2D array is to store all the matrix elements in an array and sort the array.

After sorting the array, the Kth element of the array (or the element at (K-1) index of the array) will be the answer.,

(Also see 2-D Array)

Code

#include<bits/stdc++.h>

using namespace std;



// Finding Kth smallest element in a row-wise and column-wise sorted 2D array

int kthSmallest(int **input, int n, int m, int k) {

    int arr[n*m];

    int idx=0;

    

    // Storing elements in an array

    for(int i=0; i<n; i++){

        for(int j=0; j<m; j++){

            arr[idx++] = input[i][j];

        }

    }

    sort(arr, arr+idx);

    return arr[k-1];

}

int main(){

    

    // n is number of rows & m is number of columns in array

    int n,m;

    cin>>n>>m;

    

    // Taking matrix as input

    int **arr = new int*[n];

    for(int i=0; i<n; i++){

        arr[i] = new int[m];

        for(int j=0; j<m; j++){

            cin>>arr[i][j];

        }

    }

    int k;

    cin>>k;

    

    // Function that takes input matrix, rows, columns and k as parameter & returns kth smallest element

    cout<<k<<"th smallest element in the matrix is: "<<kthSmallest(arr, n, m, k);



    return 0;

}

Sample Input

3 3

1 5 9

10 11 13

12 13 15

8

Sample Output

8th smallest element in the matrix is: 13

Complexity Analysis

Time Complexity

The time complexity of the above approach for finding the Kth smallest element in a row-wise and column-wise sorted 2D array is O(n*m), where n is the number of rows and m is the number of columns in the matrix.

Space Complexity

The space complexity of the above approach is O(n*m) because the array takes n*m space.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 2: By using an inbuilt Priority Queue in C++

Algorithm

Priority queues can be considered the best choice for the problems when asked to find the smallest or largest number from a set of numbers.

C++ has an inbuilt priority queue data structure (by default, it is the maximum priority queue).

 

Priority queues are implemented using heaps, and in maximum priority queues, the maximum element is always at the top of the heap.
 

We can solve this problem with a simple approach:

  • First, we’ll store all the elements of the 2-D matrix in the priority queue.
  • By default, the maximum element will be at the top of the heap.
  • When we use the pop function in maximum priority queues, the element with the maximum value gets removed, and the element with the second-largest value comes at the top of the heap.
  • If we are asked to find the Kth smallest element, we can keep popping the elements from the priority queue for n*m - k times (where n is the number of rows and m is the number of columns in the matrix).
  • Now, the element at the top of the heap will be our answer.

 

The basic idea behind the approach is to store all elements in a maximum priority queue and then remove all the greater elements than our Kth element.

 

Code

#include<bits/stdc++.h>

using namespace std;



// Finding Kth smallest element in a row-wise and column-wise sorted 2D array

int kthSmallest(int **input, int n, int m, int k) {

    // Inbuilt max priority queue

    priority_queue<int> pq;

    

    for(int i=0; i<n; i++){

        for(int j=0; j<m; j++){

            pq.push(input[i][j]);

        }

    }

    

    // Removing all the greater elements from Kth smallest element in priority queue

    for(int i=0; i<n*m-k; i++){

        pq.pop();

    }

    

    // Now the element at the top is Kth smallest element in a row-wise and column-wise sorted 2D array

    return pq.top();

}

int main(){

    

    // n is number of rows & m is number of columns in array

    int n,m;

    cin>>n>>m;

    

    // Taking matrix as input

    int **arr = new int*[n];

    for(int i=0; i<n; i++){

        arr[i] = new int[m];

        for(int j=0; j<m; j++){

            cin>>arr[i][j];

        }

    }

    int k;

    cin>>k;

    

    // Function that takes input matrix, rows, columns and k as parameter & returns kth smallest element

    cout<<k<<"th smallest element in the matrix is: "<<kthSmallest(arr, n, m, k);

    return 0;

}

Sample Input

3 3

1 5 9

10 11 13

12 13 15

6

Sample Output

6th smallest element in the matrix is: 12

Time and Space Complexities

The time and space complexity for this approach to find the Kth smallest element in a row-wise and column-wise sorted 2D array are the same as the 1st approach that is O(n*m) and O(n*m), respectively, because storing all elements in the priority queue takes n*m time and n*m space.

NOTE: Instead of priority queues, we can also use Ordered HashMaps here. Since ordered HashMaps, store the keys in ascending order.

In HashMaps, we will store the elements as keys and their count as values. The keys will be in ascending order so we can subtract their values from k till k<=0.

When k <= 0, the answer will be the current key in HashMap.

Approach 3: By using Binary Search Technique

Methodology

Until now, we didn’t use the information that the given matrix is row-wise and column-wise sorted. We can utilize this given information with the help of the Binary Search technique to improve the time complexity of our code.

The idea behind the Binary Search approach to finding the Kth Smallest Element in a Sorted Matrix is that: we’ll divide the matrix into two parts using a middle element as a reference. We’ll then count the number of elements in the matrix that are less than or equal to the middle element, if the count is smaller than ‘k’ then the Kth Smallest Element will be in the second half, and if the count is greater than ‘k’ then the Kth Smallest Element will be in the first half.

Algorithm

  • Initialize two integers, low and high, which will initially contain the minimum element of the matrix and maximum element of the matrix, respectively.
  • Iterate, while low is less than high.
  • Calculate the middle integer (it might or might not be in the matrix) with the help of low and high.
  • Count the number of elements in the arrays that are less than or equal to the middle.
  • If the count is less than k, then the Kth smallest element will be in the second half, so we change low to middle+1.
  • But if the count is greater than or equal to k, then the Kth smallest element will be in the first half, so we change high to mid.
  • Finally, we return low.

 

Dry Run

Input Matrix

We are asked to find the Kth smallest element in the given row-wise and column-wise sorted matrix.

Let K = 8

 

Loop starts



Initially low = 1, high = 15 and mid = 8

count = 2 (because 2 elements are less than 8 in the matrix)



since count < K

low = mid+1 = 9, high = 15 and mid = 12

count = 6 (because 6 elements are less than or equal to 12 in the matrix)



since count < K

low = mid+1 = 13, high = 15 and mid = 14

count = 8 (because 8 elements are less than or equal to 14 in the matrix)



now since count >= K

high = mid = 14, low = 13 and mid = 13

count = 8



now since count >= K

high = mid = 13, low = 13 and mid = 13



Loop ends



Return low (which is 13)

 

ANSWER: The 8th smallest element for the given matrix is 13.

 

Code

#include<bits/stdc++.h>

using namespace std;



// Finding Kth smallest element in a row-wise and column-wise sorted 2D array

int kthSmallest(int **input, int n, int m, int k) {

    

    int low=input[0][0];

    int high=input[n-1][m-1];

    

    while(low<high){

        // Hypothetically splitting matrix into 2 halves: low to mid & mid+1 to high

        int mid=low + (high-low)/2;

        

        // Count of elements lesser than or equal to mid

        int count=0;

        for(int i=0;i<n;i++){

            count += upper_bound(input[i] ,input[i]+m, mid) - input[i];

        }

        

        // If the count is less than k, then Kth smallest element will be in the second half

        if(count<k){

            low=mid+1;

        }

        

        // Else if the count is greater than or equal to k, then Kth smallest element will be in the first half

        else{

            high=mid;

        }

    }

    

    return low;

}

int main(){

    

    // n is number of rows & m is number of columns in array

    int n,m;

    cin>>n>>m;

    

    // Taking matrix as input

    int **arr = new int*[n];

    for(int i=0; i<n; i++){

        arr[i] = new int[m];

        for(int j=0; j<m; j++){

            cin>>arr[i][j];

        }

    }

    int k;

    cin>>k;

    

    // Function that takes input matrix, rows, columns and k as parameter & returns kth smallest element

    cout<<k<<"th smallest element in the matrix is: "<<kthSmallest(arr, n, m, k);

    return 0;

}

Sample Input

4 4

1 2 3 4

3 8 10 12

6 12 14 18

10 16 17 20

11

Sample Output

11th smallest element in the matrix is: 12

Complexity Analysis

Time Complexity

The time complexity for this approach is better than the above-discussed 1st and 2nd approaches. With Binary Search, we can find the Kth smallest element in a row-wise and column-wise sorted 2D array in O(p*n*logm) time.

Where n is the number of rows,

m is the number of columns, and

p is the log of the absolute difference between the minimum element (input[0][0]) and maximum element (input[n-1][m-1]).

Space Complexity

Space required to get the Kth Smallest Element in a Sorted Matrix with Binary Search is constant i.e., the Space Complexity is O(1)

Frequently Asked Questions

How do you find the kth element in a sorted matrix?

Use a priority queue. Iterate over the matrix and keep adding elements to the priority queue. If the size of the priority queue grows more than k, remove the top element as we only need to consider the k smallest elements. Return the top element at the end.

How do you find the kth smallest element in a 2D array?

Initialise a new 1d array. Iterate over the 2d array and append all its elements to the 1d array. Then sort the 1d array. After sorting, the element present at the index k-1 ( in the case of a 0-indexed array) and k(in the case of a 1-indexed array) is the answer.

How do you find the smallest number in a matrix?

Create a new variable (let's say 'minValue') and initialise it to INT_MAX. Iterate over the matrix and keep replacing the minValue with the current element if the current element is smaller than the minValue. Once you are done iterating through the matrix, return the minValue.

What are the different strategies that can be used to find Kth smallest element in a row-wise and column-wise sorted 2D array?

There are different ways to solve this problem: Converting the 2d array to a sorted 1d array and returning the kth element, Using a priority Queue to keep track of k smallest elements and printing the element on top, or using binary search.

Conclusion

Well done!! Today you learned how to find Kth smallest element in a sorted matrix.

Whenever you are given the problem of finding Kth smallest or Kth largest element from a set of numbers, priority queues can be thought of as a first approach because it works most of the time.

There can be multiple approaches to this task, but we have seen that the Binary Search technique works best here because it has less time complexity and constant space requirement.

Recommended Problems:

 

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Thank you

Previous article
Priority Queue of Pairs In C++ with Ordering
Next article
Connect N ropes with minimum cost
Guided path
Free
gridgp-icon
Competitive programming
16 chapters
217+ Problems
gp-badge
Earn badges and level up
Live masterclass