Search in a row-wise sorted matrix

JavaView on GFG

Problem Overview

Search in matrix where each row is sorted independently.

Intuition

Search in matrix where each row is sorted independently. Binary search on each row.

Algorithm

1For each row: binary search for target. Return true if found in any row.

Common Pitfalls

• O(m log n). If rows are also connected (end of row < start of next): treat as flat sorted array and binary search O(log mn).

Search in a row-wise sorted matrix.java

Java

// Approach: Binary search within each row, or binary search treating matrix as 1D using (mid/cols, mid%cols).
// Time: O(n log m) Space: O(1)
class Solution {
    // Function to search a given number in row-column sorted matrix.
    public boolean searchRowMatrix(int[][] mat, int x) {
        int n = mat.length;
        for (int i = 0; i < n; i++) {
            if (mat[i][0] <= x && mat[i][mat[0].length - 1] >= x) {
                if (search(mat[i], x))
                    return true;
            }
        }

        return false;
    }

    boolean search(int arr[], int k) {
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (arr[mid] == k)
                return true;
            else if (arr[mid] > k)
                r = mid - 1;
            else
                l = mid + 1;
        }
        return false;
    }
}

Was this solution helpful?