Introduction
The problem states we are given a number, X, and a rowwise and columnwise 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.
Output: Not Found.
Explanation: 21 is not present in the given matrix, so Output will be â€śNot Foundâ€ť.
Also Read About, Array Implementation of Queue and Rabin Karp Algorithm
Naive Approach
We can traverse the complete rowwise and columnwise sorted matrix and search for the given element in the Naive approach. If found, then print its location.
Steps of Algorithm
 Run Nested For loop, outer for loop for a row, and inner for loop for the column.
 Compare Every Element with X; if both are equal, print â€śFound at:â€ť row, column number.
 If an element is not present in the matrix, print â€śNot Found.â€ť
Pseudo Code
FindPosition(n,m, mat,X)
 i = 0, j = 0

For i to n

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

For j to m:
 Return â€śnot foundâ€ť.
Implementation in C++
// C++ Code to find element in rowwise and columnwise 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;
}
}
}
// if X is not found
cout << "Not Found" << endl;
}
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 rowwise and columnwise sorted matrix. Since we are traversing the whole array, Time complexity is O(N*M).
Space Complexity: O(1)
Explanation: No extra Space is required.