Search in a Row-Column sorted matrix

JavaView on GFG

Time: O(n+m)

Space: O(1)

Intuition

Search in matrix where each row and column is sorted. Start from top-right corner.

Algorithm

1Start at (0, n-1). If target == mat[r][c]: found. If target < mat[r][c]: c--. If target > mat[r][c]: r++.

Common Pitfalls

•Same as LC 240. O(m+n) staircase search. Each step eliminates a row or column.

Search in a Row-Column sorted matrix.java

Java

// Approach: Start from top-right corner. Move left if current > target, move down if current < target.
// Time: O(n+m) Space: O(1)
class Solution {
    public static boolean matSearch(int mat[][], int x) {
        for (int i = 0; i < mat.length; i++) {
            int low = 0, high = mat[i].length - 1;
            if (mat[i][low] <= x && mat[i][high] >= x) {

                while (low <= high) {
                    int mid = (low + high) / 2;
                    if (mat[i][mid] == x)
                        return true;
                    else if (mat[i][mid] > x)
                        high = mid - 1;
                    else
                        low = mid + 1;

                }
            }

        }
        return false;
    }
}

Was this solution helpful?