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

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);
}

You can also try this code with Online C++ Compiler

Run Code

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 Complexity: O(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.