Search in a sorted Matrix

Given a strictly sorted 2D matrix mat[][] of size n x m anda number x. Find whether the number x is present in the matrix or not.
Note: In a strictly sorted matrix, each row is sorted in strictly increasing order, and the first element of the i^th row (i!=0) is greater than the last element of the (i-1)^th row.

Examples:

Input: mat[][] = [[1, 5, 9], [14, 20, 21], [30, 34, 43]], x = 14
Output: true
Explanation: 14 is present in the matrix, so output is true.

Input: mat[][] = [[1, 5, 9, 11], [14, 20, 21, 26], [30, 34, 43, 50]], x = 42
Output: false
Explanation: 42 is not present in the matrix.

Input: mat[][] = [[87, 96, 99], [101, 103, 111]], x = 101
Output: true
Explanation: 101 is present in the matrix.

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

Approach 01:

class Solution {
public:
    // Function to search a given number in a row-column sorted matrix.
    bool searchMatrix(vector<vector<int>> &matrix, int target) {
        int numRows = matrix.size();
        for (int row = 0; row < numRows; row++) {
            if (matrix[row][0] <= target && target <= matrix[row][matrix[row].size() - 1]) {
                for (int col = 0; col < matrix[row].size(); col++) {
                    if (matrix[row][col] == target) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
};

class Solution:
    # Function to search a given number in a row-column sorted matrix.
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        numRows = len(matrix)
        for row in range(numRows):
            if matrix[row][0] <= target <= matrix[row][-1]:
                for col in range(len(matrix[row])):
                    if matrix[row][col] == target:
                        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. 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 matrix is given as input, requiring \( O(m \times n) \) space.
• Auxiliary Variables:
  • The variables numRows, row, col, and target use \( O(1) \) space.
• Overall Space Complexity:

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