Search in a Row-Column sorted matrix

JavaView on GFG

Time: O(n+m)

Space: O(1)

Problem Overview

Search in matrix where each row and column is sorted.

See our study guide for structured GFG and LeetCode practice.

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?