1.
Introduction
1.1.
Sample Examples
2.
Naive Approach
2.1.
Steps of Algorithm
2.2.
Pseudo Code
2.3.
Implementation in C++
2.3.1.
Complexity Analysis
3.
Optimized Approach(Greedy)
3.1.
Steps of Algorithm
3.2.
Pseudo Code
3.3.
Implementation in C++
3.3.1.
Complexity Analysis
4.
FAQs
5.
Key takeaways
Last Updated: Mar 27, 2024

# Search in a 2-D Matrix which is sorted row-wise and column-wise.

Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

## Introduction

The problem states we are given a number, X, and a row-wise and column-wise sorted matrix. We need to check if the given number X is present in this matrix or not; if it is present, then print the position of the X, print â€śNot Foundâ€ť if it is not present in the matrix.

### Sample Examples

Example 1:

``````Input : matrix[4][4] = 	{ {1,  2, 3,  4},
{5,  6, 7,  8},
{9, 10, 11, 12},
{13, 14, 15, 16} }
X = 7.
Output: Found at 2,3.

Explanation:7 is present in the 2nd row, 3rd column, so the position is 2,3.  ``````

Example 2:

``````Input : matrix[3][5] = { {1,  2, 3,  4, 5},
{ 6, 7,  8, 9 , 10},
{11, 12, 13, 14, 15} }
X = 21.

Explanation: 21 is not present in the given matrix, so Output will be â€śNot Foundâ€ť. ``````

## Naive Approach

We can traverse the complete row-wise and column-wise sorted matrix and search for the given element in the Naive approach. If found, then print its location.

### Steps of Algorithm

1. Run Nested For loop, outer for loop for a row, and inner for loop for the column.
2. Compare Every Element with X; if both are equal, print â€śFound at:â€ť row, column number.
3. If an element is not present in the matrix, print â€śNot Found.â€ť

### Pseudo Code

FindPosition(n,m, mat,X)

1. i = 0, j = 0
2. For i to n
1. For j to m:
1. If mat[i][j] == X, return â€śfoundâ€ť.

### Implementation in C++

``````// C++ Code to find element in row-wise and column-wise sorted matrix
#include<bits/stdc++.h>
using namespace std;
// Function to find position of number X
void FindPosition(int mat[4][4], int X){
int n = 4, m = 4;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
// If X is found, print its position
if(mat[i][j]==X){
cout << "Found At " << i+1 << "," << j+1;
return;
}
}
}
}
int main(){
// given matrix
int matrix[4][4] =  { {1,  2, 3,  4},
{5,  6, 7,  8},
{9,10,11,12},
{13,14,15,16} };
// number to be found
int X = 7;
// Calling the function to find the position of Element X.
FindPosition(matrix, X);
}``````

Output:

``Output: Found At 2,3 ``

#### Complexity Analysis

Time Complexity: O(N*M)

Explanation: N is the number of rows, and M is the number of columns of this row-wise and column-wise sorted matrix. Since we are traversing the whole array, Time complexity is O(N*M).

Space ComplexityO(1)

Explanation: No extra Space is required.

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

## Optimized Approach(Greedy)

The idea is to eliminate rows or columns in each comparison until we find the required number or out of the range. We will start from the top right corner of the matrix. There can be three possible Cases.

1. If Element X is greater than the current number. In that case, it means that all elements in the current row are smaller than X(because the row is already sorted and we are at the right most position), so we can eliminate the current row and move to the next row to find the number X.
2. If Element X is smaller than the current number. In that case, it means that all elements in the current column(column is sorted, and we are at the smallest position) are greater than X, so we can eliminate the current column and move to the previous column to find the number.
3. If Element X is equal to the current number, print â€śFound atâ€ť row number, column number, and this will end our search.
4. In this way, we can optimally search in row-wise and column-wise sorted matrix.

### Steps of Algorithm

1. Let the element to be found be X.
2. Create two variables i = 0, j = m-1, denote 0th row and last column.
3. Run the loop until i!= n, where n is the number of rows or j<0.
4. Check if the current number is greater than X, then decrease j; otherwise, if the current number is smaller than X, then increase i.
5. If the element is found, print i and j.

### Pseudo Code

FindPosition(n,m, mat,X)

1. Go to last element in first row, i = 0, j = n-1.
2. For (i to n) and (j to 0) :
1. If mat[i][j]==X, return â€śfoundâ€ť.
2. Else if X<matrix[i][j] :
1. j = j - 1
3. Else
1. i = i + 1

### Implementation in C++

``````// / C++ Code to find element in row-wise and column-wise sorted matrix
#include<bits/stdc++.h>
using namespace std;
// Function to find position of number X
void FindPosition(int mat[4][4], int x, int n,int m){
int i = 0, j = m-1;
// running the loop in the boundary conditions
while(i!=n && j>0){
if(mat[i][j]==x){
cout << "Found At " << i+1 << "," << j+1;
return;
}
// if the element is greater, then move to previous column
if(mat[i][j]>x){
j--;
continue;
}
// if element is smaller, then move to next row
if(mat[i][j]<x){
i++;
continue;
}
}
return;
}
int main(){
// given matrix
int matrix[4][4] =  { {1,  2, 3,  4},
{5,  6, 7,  8},
{9,10,11,12},
{13,14,15,16} };
// number to be found
int X = 7;
// Calling the function to find the position of Element X.
FindPosition(matrix, X, 4, 4);
}``````

Output:

``Found At 2,3 ``

#### Complexity Analysis

Time Complexity: O(N+M)

Explanation: N is the number of rows, and M is the number of columns of this row-wise and column-wise sorted matrix. Since we are traversing at most one row and one column, the worst-case Time complexity is O(N+M).

Space ComplexityO(1)

Explanation: No extra Space is required.

Check out this problem - First And Last Occurrences Of X

## FAQs

1. Which sorting algorithm is used when we sort using STL?
The sorting algorithm used in STL sort() is IntroSort. Introsort is a hybrid sorting algorithm that uses three sorting algorithms to minimize the running time. These algorithms are quicksort, Heapsort, and Insertion Sort.

2. What is the greedy approach?
It is an algorithm to get the optimal solution for the problem. In this algorithm, we always choose the next best solution that seems optimal at that step. We build solutions piece by piece to reach the optimal solution.

3. What is the worst, average, and best case time complexity of merge sort?
Merge sort always have O(NlogN) in all the cases because we always divide the array into maximum LogN parts and then again merge them in O(N) time complexity, so overall time complexity is constant, i.e., O(NlogN).

## Key takeaways

In this article, we discussed the problem of checking if the given number is present in the row-wise and column-wise sorted matrix. We discussed the two approaches, i.e., brute force and optimized approach using maths. We hope you understand the problem and solution properly. Now you can do more similar questions.

If you are a beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free!