Search in a Row-Column sorted matrix

Given a 2D integer matrix mat[][] of size n x m, where every row and column is sorted in increasing order and a number x,the task is to find whether element x is present in the matrix.

Examples:

Input: mat[][] = [[3, 30, 38],[20, 52, 54],[35, 60, 69]], x = 62
Output: false
Explanation: 62 is not present in the matrix, so output is false.

Input: mat[][] = [[18, 21, 27],[38, 55, 67]], x = 55
Output: true
Explanation: 55 is present in the matrix.

Input: mat[][] = [[1, 2, 3],[4, 5, 6],[7, 8, 9]], x = 3
Output: true
Explanation: 3 is present in the matrix.

Constraints:
1 <= n, m <=1000
1 <= mat[i][j] <= 10⁹
1<= x <= 10⁹

Approach 01:

#include <vector>
using namespace std;

class Solution {
public:
    bool matSearch(vector<vector<int>>& mat, int x) {
        for (int rowIndex = 0; rowIndex < mat.size(); ++rowIndex) {
            // Check if x could be in the current row based on the row's range
            if (mat[rowIndex][0] <= x && x <= mat[rowIndex][mat[rowIndex].size() - 1]) {
                // Search for x in the current row
                for (int colIndex = 0; colIndex < mat[rowIndex].size(); ++colIndex) {
                    if (mat[rowIndex][colIndex] == x) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
};

import collections

class Solution:
    def matSearch(self, mat, x):
        for rowIndex in range(len(mat)):
            # Check if x could be in the current row based on the row's range
            if mat[rowIndex][0] <= x <= mat[rowIndex][-1]:
                # Search for x in the current row
                for colIndex in range(len(mat[rowIndex])):
                    if mat[rowIndex][colIndex] == x:
                        return True
        return False

Time Complexity

• Row Iteration:
  • The outer loop iterates over all rows of the matrix. Let the number of rows be \( m \).
• Column Search:
  • For each row, the inner loop iterates over all columns to search for the target \( x \). Let the number of columns be \( n \).
  • In the worst case, all elements of the matrix are checked. Hence, the total time complexity is: \( O(m \times n) \)
• Overall Time Complexity:

  The total time complexity is: \( O(m \times n) \)

Space Complexity

• Input Storage:
  • The matrix mat is given as input, requiring \( O(m \times n) \) space.
• Auxiliary Variables:
  • The variables rowIndex, colIndex, and x use \( O(1) \) space.
• Overall Space Complexity:

  The total space complexity is: \( O(1) \) (excluding input storage).