DSA

Search in 2D matrix

Covers: Brute Force, Better, Optimal. Optimal — Time O(log(n * m), Space O(1).

August 8, 2026
DSAArraysLeetCodePracticeMatrix

Given a 2-D array mat where the elements of each row are sorted in non-decreasing order, and the first element of a row is greater than the last element of the previous row (if it exists), and an integer target, determine if the target exists in the given mat or not.

Brute Force#

Use 2 loops to find the target.

Time Complexity: O(n^2)

Space Complexity: O(1)

Better Approach#

For every row, use binary search to find the target, since the matrix is row wise sorted.

cpp
class Solution{
public:
    bool binarySearch(vector<int> &nums, int target){
        int low=0,high=nums.size()-1;

        while(low<=high){
            int mid = (low+high)/2;

            if(nums[mid]==target)
                return true;

            if(nums[mid]<target)
                low=mid+1;
            else
                high=mid-1;
        }
        return false;
    }

    bool searchMatrix(vector<vector<int>> &mat, int target){
        int n = mat.size();

        for(vector<int> nums: mat)
        {
            if(binarySearch(nums, target))
                return true;
        }
        return false;
    }
};

Time Complexity: O(n * log m) — binary search on each of n rows

Space Complexity: O(1)

Optimal Approach#

Treat the entire matrix as a flattened sorted array of size n*m and run a single binary search. Map any virtual index mid back to 2D coordinates: row = mid / m, col = mid % m.

This works because the property "first element of each row > last element of previous row" guarantees the whole matrix is globally sorted when read row by row.

cpp
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& mat, int target) {
        int n = mat.size(), m = mat[0].size();
        int low = 0, high = n * m - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            int val = mat[mid / m][mid % m];

            if (val == target) return true;
            if (val < target) low = mid + 1;
            else high = mid - 1;
        }
        return false;
    }
};

Time Complexity: O(log(n * m))

Space Complexity: O(1)

Related articles

DSARotate MatrixSimulation approach — transpose + row-reverse. Time O(n²), Space O(1).DSASpiral MatrixSimulation approach.DSASet Matrix ZerosCovers: Set, Greedy. Optimal — Time O(m*n), Space O(1).