Day 3 - Search in a Row-Column sorted matrix.md

Difficulty	Source	Tags
Easy	160 Days of Problem Solving	Searching Matrix

🚀 Day 3. Search in a Row-Column Sorted Matrix 🧠

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

💡 Problem Description:

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 determine whether element x is present in the matrix.

🔍 Example Walkthrough:

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^9$
• $1<= x <= 10^9$

🎯 My Approach:

1. Search in Sorted Matrix:

   • The matrix is sorted both row-wise and column-wise, meaning the smallest element is at the top-left and the largest is at the bottom-right.
   • The key observation is that you can eliminate either a row or a column at each step depending on the value of x.
   • Start from the top-right corner of the matrix:
     • If the current element is equal to x, return true.
     • If the current element is greater than x, move left (decrease the column index).
     • If the current element is less than x, move down (increase the row index).
   • This approach takes advantage of the sorted property to reduce the search space efficiently.

2. Steps:

   • Initialize a pointer at the top-right corner of the matrix.
   • Traverse the matrix by comparing the current element with x and adjust the row or column pointer based on the comparison.
   • If you find x, return true; otherwise, continue until you exhaust the matrix.

🕒 Time and Auxiliary Space Complexity

• Expected Time Complexity: O(n + m), where n is the number of rows and m is the number of columns in the matrix. We make at most n + m steps (moving either left or down).
• Expected Auxiliary Space Complexity: O(1), as we only use a constant amount of extra space for the row and column pointers.

📝 Solution Code

Code (Cpp)

class Solution {
public:
    bool matSearch(vector<vector<int>>& mat, int x) {
        int r = 0, c = mat[0].size() - 1;
        while (r < mat.size() && c >= 0) {
            if (mat[r][c] == x) return true;
            else if (mat[r][c] > x) c--;
            else r++;
        }
        return false;
    }
};

Code (Java)

class Solution {
    public boolean matSearch(int[][] mat, int x) {
        int r = 0, c = mat[0].length - 1;
        while (r < mat.length && c >= 0) {
            if (mat[r][c] == x) return true;
            else if (mat[r][c] > x) c--;
            else r++;
        }
        return false;
    }
}

Code (Python)

class Solution:
    def matSearch(self, mat, x):
        r, c = 0, len(mat[0]) - 1
        while r < len(mat) and c >= 0:
            if mat[r][c] == x: return True
            elif mat[r][c] > x: c -= 1
            else: r += 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