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

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

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.

- By using a one-dimensional array
- By using an inbuilt priority queue or a HashMap
- 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 K^{th} 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.