Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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. 
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 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”. 
  3. Return “not 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;
            }
        }
    }
    // 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 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.
  6. Otherwise, print “Not Found”. 

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  

Return “Not 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,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;
        }
    }
    // If the element is not found
    cout << "Not Found" << endl;
    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! 

Thank you for reading. 

Until then, Keep Learning and Keep Coding.

Previous article
Matrix probability problem
Next article
Size of all Connected Non-Empty Cell of Matrix
Live masterclass