Browse Categories
Choose your Categories to read

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

Akshat Chaturvedi
Oct 28, 2021

Introduction

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 K-1 elements of the matrix.

 

Example:

 

159
101113
121315

 

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!!
 

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.,

 

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

 

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.

 

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

 

Algorithm

Priority queues can be considered the best choice for the problems when asked to find some 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 by 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 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

159
101113
121315

 

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

 

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., O(1)

 

Frequently Asked Questions

 

Q1) What is a 2-D Array/matrix?

A1) A two-dimensional array (also known as a matrix) can be identified as a one-dimensional array that contains one-dimensional arrays as its elements.

In short, a 2-D array is an array of arrays. A two-dimensional array is a collection of linear arrays.

 

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

A2) We can find Kth smallest element in a row-wise and column-wise sorted 2D array by many techniques. Some of them that are discussed above are:

  1. By using a one-dimensional array.
  2. By using an inbuilt priority queue.
  3. By using ordered HashMaps.
  4. By using Binary Search Technique.

 

Q3) What things would change when finding Kth smallest vs. largest element in a row-wise and column-wise sorted 2D array?

A3) If we are using the first approach (by using a one-dimensional array), then for finding the Kth largest element in a row-wise and column-wise sorted 2D array. In that case, we’ll have to traverse our array from the back, or we’ll have to sort our array in decreasing order.

 

Q4) What are the most efficient time and space complexity that we could use while finding Kth smallest element in a row-wise and column-wise sorted 2D array?

A4) The most efficient way is to use the Binary Search technique where:

  • Time Complexity is O(p*n*logm), and
  • Space Complexity is constant O(1)

 

Q5) What are the worst-case time and space complexities of sorting 2-D arrays?

A5) The worst-case time complexity of sorting a 2-D array is O(n*m), where n is the number of rows and m is the number of columns.

The space complexity will be O(1).

 

Key Takeaways

 

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

 

Whenever you are given the problem to find 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.

 

Was this article helpful ?
0 upvotes