Search in a row wise and column wise sorted matrix

Determine the location of X in the matrix, if it exists, given a N X N matrix and an integer X. Print “Element not found” otherwise. The matrix’s rows and columns are arranged in ascending order.

Input: mat[4][4] = { {10, 20, 30, 40},  X = 29
                               {15, 25, 35, 45},
                               {27, 29, 37, 48},
                             {32, 33, 39, 50}}
 
Output: Found at (2, 1)
Explanation: Element at (2,1) is 29


Input : mat[4][4] = { {10, 20, 30, 40},   X = 100
                                {15, 25, 35, 45},
                               {27, 29, 37, 48},
                              {32, 33, 39, 50}};
     
Output: Element not found
Explanation: Element 100 does not exist in the matrix

Approaches to Search in row wise and column wise sorted matrix:

[Naive Approach] Traversing the Complete Matrix – O(N^2) Time and O(1) Space

Expected Approach] Removing row or column in each comparison – O(N) Time and O(1) Space

[Naive Approach] Traversing the Complete Matrix – O(N^2) Time and O(1) Space:

C++

// C++ program to search an element in row-wise
// and column-wise sorted matrix
#include <bits/stdc++.h>

using namespace std;

/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
int search(int mat[4][4], int n, int x)
{
    if (n == 0)
        return -1;

    // traverse through the matrix
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            // if the element is found
            if (mat[i][j] == x) {
                cout << "Element found at (" << i << ", "
                     << j << ")\n";
                return 1;
            }
    }

    cout << "n Element not found";
    return 0;
}

// Driver code
int main()
{
    int mat[4][4] = { { 10, 20, 30, 40 },
                      { 15, 25, 35, 45 },
                      { 27, 29, 37, 48 },
                      { 32, 33, 39, 50 } };

    // Function call
    search(mat, 4, 29);

    return 0;
}

C

// C program to search an element in row-wise
// and column-wise sorted matrix
#include <stdio.h>

/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
int search(int mat[4][4], int n, int x)
{
    if (n == 0)
        return -1;

    // traverse through the matrix
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            // if the element is found
            if (mat[i][j] == x) {
                printf("Element found at (%d, %d)\n", i, j);
                return 1;
            }
    }

    printf("Element not found");
    return 0;
}

// Driver code
int main()
{
    int mat[4][4] = { { 10, 20, 30, 40 },
                      { 15, 25, 35, 45 },
                      { 27, 29, 37, 48 },
                      { 32, 33, 39, 50 } };

    // Function call
    search(mat, 4, 29);

    return 0;
}

Java

// Java program to search an element in row-wise
// and column-wise sorted matrix

class GFG {
    static int search(int[][] mat, int n, int x)
    {
        if (n == 0)
            return -1;

        // traverse through the matrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                // if the element is found
                if (mat[i][j] == x) {
                    System.out.print("Element found at ("
                                     + i + ", " + j
                                     + ")\n");
                    return 1;
                }
        }

        System.out.print(" Element not found");
        return 0;
    }

    // Driver code
    public static void main(String[] args)
    {
        int mat[][] = { { 10, 20, 30, 40 },
                        { 15, 25, 35, 45 },
                        { 27, 29, 37, 48 },
                        { 32, 33, 39, 50 } };

        // Function call
        search(mat, 4, 29);
    }
}

Python

# Python program to search an element in row-wise
# and column-wise sorted matrix

# Searches the element x in mat[][]. If the
# element is found, then prints its position
# and returns true, otherwise prints "not found"
# and returns false


def search(mat, n, x):
    if(n == 0):
        return -1

    # Traverse through the matrix
    for i in range(n):
        for j in range(n):

            # If the element is found
            if(mat[i][j] == x):
                print(f"Element found at ({i}, {j})")
                return 1

    print(" Element not found")
    return 0


# Driver code
if __name__ == "__main__":
    mat = [[10, 20, 30, 40], [15, 25, 35, 45],
           [27, 29, 37, 48], [32, 33, 39, 50]]

    # Function call
    search(mat, 4, 29)

JS

// Java Script program to search an element in row-wise
// and column-wise sorted matrix

function search(mat, n, x) {
    if (n == 0)
        return -1;

    // traverse through the matrix
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++)
            // if the element is found
            if (mat[i][j] == x) {
                console.log("Element found at (" + i + ", " + j + ")");
                return 1;
            }
    }

    console.log(" Element not found");
    return 0;
}

let mat = [
    [10, 20, 30, 40],
    [15, 25, 35, 45],
    [27, 29, 37, 48],
    [32, 33, 39, 50]
];

search(mat, 4, 29);

Output

Element found at (2, 1)

Time Complexity: O(N²)
Auxiliary Space: O(1), since no extra space has been taken