Search in a sorted Matrix

JavaView on GFG

Time: O(log(n*m))

Space: O(1)

Intuition

Search in matrix where each row is sorted and first element of row > last of previous. Binary search treating as 1D.

Algorithm

1Treat m x n matrix as sorted array of m*n elements. Binary search with index mapping: row=mid/n, col=mid%n.

Common Pitfalls

•Same as LC 74. 1D binary search with 2D index conversion. O(log(m*n)).

Search in a sorted Matrix.java

Java

// Approach: Binary search on the flattened virtual 1D array. Index i maps to (i/cols, i%cols).
// Time: O(log(n*m)) Space: O(1)
class Solution {
    // Function to search a given number in row-column sorted matrix.
    public boolean searchMatrix(int[][] mat, int x) {
        int m = mat.length; // Number of rows
        int n = mat[0].length; // Number of columns

        // Start from top-right corner
        int i = 0; // Row index
        int j = n - 1; // Column index

        while (i < m && j >= 0) {
            if (mat[i][j] == x)
                return true; // Found the element
            else if (mat[i][j] > x)
                j--; // Move left if the current element is larger
            else
                i++; // Move down if the current element is smaller
        }

        return false; // Element not found
    }
}

Was this solution helpful?