Day 5 - Search in a sorted Matrix.md

Difficulty	Source	Tags
Medium	160 Days of Problem Solving	Searching Matrix

🚀 Day 5. Search in a sorted Matrix 🧠

The problem can be found at the following link: Problem Link

💡 Problem Description:

You are given a strictly sorted 2D matrix mat[][] of size n x m and a number x. Your task is to 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 ith row (i!=0) is greater than the last element of the (i-1)th row.

🔍 Example Walkthrough:

Input:
mat[][] = [[1, 5, 9], [14, 20, 21], [30, 34, 43]], x = 14
Output:
true
Explanation:
14 is present in the matrix, so the 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^9$
• $1 <= x <= 10^9$

🎯 My Approach:

Binary Search on a Flattened Matrix

This problem can be solved efficiently using binary search. Even though the matrix is 2D, its structure allows it to be treated as a sorted 1D array where:

• The element at position (i, j) in the matrix corresponds to the position i * m + j in the flattened array (where m is the number of columns).
• Using this, we can perform a binary search directly on the matrix as if it were a 1D array.

Steps:

1. Initialize two pointers, l = 0 (start) and r = n * m - 1 (end of the flattened matrix).
2. Use binary search to find the middle index, calculate the corresponding value in the matrix using:
   • row = mid / m
   • col = mid % m
3. Compare the middle value with x:
   • If equal, return true.
   • If less than x, move the left pointer l to mid + 1.
   • If greater than x, move the right pointer r to mid - 1.
4. If the loop ends without finding x, return false.

🕒 Time and Auxiliary Space Complexity

• Expected Time Complexity: O(log(n * m)), as we perform binary search on a virtual array of size n * m.
• Expected Auxiliary Space Complexity: O(1), as we only use a constant amount of additional space.

📝 Solution Code

Code (C++)

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& mat, int x) {
        int n = mat.size(), m = mat[0].size(), l = 0, r = n * m - 1;
        while (l <= r) {
            int mid = (l + r) / 2, val = mat[mid / m][mid % m];
            if (val == x) return true;
            val < x ? l = mid + 1 : r = mid - 1;
        }
        return false;
    }
};

Code (Java)

class Solution {
    public boolean searchMatrix(int[][] mat, int x) {
        int n = mat.length, m = mat[0].length, l = 0, r = n * m - 1;
        while (l <= r) {
            int mid = (l + r) / 2, val = mat[mid / m][mid % m];
            if (val == x) return true;
            if (val < x) l = mid + 1;
            else r = mid - 1;
        }
        return false;
    }
}

Code (Python)

class Solution:
    def searchMatrix(self, mat, x):
        n, m = len(mat), len(mat[0])
        l, r = 0, n * m - 1
        while l <= r:
            mid = (l + r) // 2
            val = mat[mid // m][mid % m]
            if val == x:
                return True
            if val < x:
                l = mid + 1
            else:
                r = mid - 1
        return False

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count