Skip to main content
CodePeetCodePeet
CodePeet 250

Search a 2D Matrix

MEDIUMProblemSolveExternal Links

Description

You are given an m × n integer matrix where:

  1. Each row is sorted in non-decreasing order from left to right.
  2. The first integer of each row is greater than the last integer of the previous row.

Given an integer target, determine whether target exists anywhere in the matrix. Return true if found, false otherwise.

You must write a solution with O(log(m × n)) time complexity.

The key insight is that because of the two sorting properties, the entire matrix — when read left-to-right, top-to-bottom — forms a single sorted sequence. This opens the door to binary search.

Examples

Example 1

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

Output: true

Explanation: The value 3 is located in the first row at column index 1: matrix[0][1] = 3. Since 3 is present, we return true.

Example 2

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

Output: false

Explanation: The value 13 does not appear anywhere in the matrix. It would fall between 11 and 16 (both in row 1), but it is not present. We return false.

Example 3

Input: matrix = [[1]], target = 1

Output: true

Explanation: The matrix has a single element which equals the target. Return true.

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 ≤ m, n ≤ 100
  • -10^4 ≤ matrix[i][j], target ≤ 10^4

Editorial

Brute Force

Intuition

The simplest approach is to ignore the sorting properties entirely and check every single cell in the matrix. We scan row by row, column by column, comparing each element to the target.

Think of it like searching for a specific book on a bookshelf by checking every single book one by one, even though the books are already organized. It works, but it does not take advantage of the order.

Step-by-Step Explanation

Let's trace through with matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13:

Step 1: Start scanning from the top-left corner (0,0).

Step 2: Check row 0: elements 1, 3, 5, 7. None equals 13. Move on.

Step 3: Check (1,0) = 10. Not 13.

Step 4: Check (1,1) = 11. Not 13, but getting closer.

Step 5: Check (1,2) = 16. Not 13. We have passed where 13 would be (between 11 and 16), but brute force does not use this information — it must continue.

Step 6: Continue through remaining cells: 20, 23, 30, 34, 60. None is 13.

Step 7: After checking all 12 cells, return false. The target is not in the matrix.

Brute Force — Scanning Every Cell in the Matrix — Watch how brute force checks every cell one by one, unable to skip any element even though the matrix is sorted.

Algorithm

  1. For each row i from 0 to m-1:
    • For each column j from 0 to n-1:
      • If matrix[i][j] == target, return true
  2. If no match found after checking all cells, return false

Code

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == target)
                    return true;
            }
        }
        return false;
    }
};
class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        for row in matrix:
            for val in row:
                if val == target:
                    return True
        return False
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == target)
                    return true;
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(m × n)

We potentially visit every cell in the m × n matrix. Each comparison is O(1). In the worst case (target not found or in the last cell), we perform m × n comparisons.

With m, n up to 100, this is at most 10,000 comparisons — fast enough for the constraints, but far from optimal.

Space Complexity: O(1)

We use only a few index variables. No additional data structures.

Why This Approach Is Not Efficient

The brute force approach completely ignores that every row is sorted and that rows are ordered relative to each other. It treats the matrix as an unorganized collection of numbers.

The core problem: each comparison only eliminates one element from consideration. After checking matrix[i][j], we have only ruled out that single cell.

Key insight: Since each row is individually sorted, we can use binary search within a row to find the target (or confirm its absence) in O(log n) time instead of O(n). This reduces the work per row from n comparisons to log n comparisons.

Better Approach - Binary Search Per Row

Intuition

Since each row is sorted, we can apply binary search within each row instead of scanning linearly. Before searching a row, we can quickly check if the target falls within that row's range (between the first and last element). If not, we skip the row entirely.

Think of it like a library organized into shelves (rows), where each shelf has books sorted by number. Instead of checking every book, you first glance at the first and last book on each shelf to see if your target book could be there. When you find the right shelf, you use a quick halving strategy to find the exact book.

Step-by-Step Explanation

Let's trace with matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3:

Step 1: Start with row 0: [1, 3, 5, 7]. Check range: first = 1, last = 7.

Step 2: Is 1 ≤ 3 ≤ 7? Yes! Target 3 falls within row 0's range. Perform binary search.

Step 3: Binary search: low = 0, high = 3. Compute mid = (0 + 3) / 2 = 1.

Step 4: Check matrix[0][1] = 3. Compare with target 3.

Step 5: 3 == 3. Found! Return true.

Step 6: We checked only 1 row range and made only 1 binary search comparison. No need to examine rows 1 or 2.

Binary Search Per Row — Finding Target in the Correct Row — Watch how we first identify the candidate row by checking value ranges, then use binary search within that row to find the target efficiently.

Algorithm

  1. For each row in the matrix:
    • If target < row[0] or target > row[n-1], skip this row
    • Otherwise, perform binary search within this row:
      • Set low = 0, high = n - 1
      • While low ≤ high:
        • mid = (low + high) / 2
        • If row[mid] == target, return true
        • If row[mid] < target, set low = mid + 1
        • Else set high = mid - 1
  2. If no match found in any row, return false

Code

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] <= target && target <= matrix[i][n - 1]) {
                int lo = 0, hi = n - 1;
                while (lo <= hi) {
                    int mid = lo + (hi - lo) / 2;
                    if (matrix[i][mid] == target) return true;
                    else if (matrix[i][mid] < target) lo = mid + 1;
                    else hi = mid - 1;
                }
            }
        }
        return false;
    }
};
class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        for row in matrix:
            if row[0] <= target <= row[-1]:
                lo, hi = 0, len(row) - 1
                while lo <= hi:
                    mid = (lo + hi) // 2
                    if row[mid] == target:
                        return True
                    elif row[mid] < target:
                        lo = mid + 1
                    else:
                        hi = mid - 1
        return False
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] <= target && target <= matrix[i][n - 1]) {
                int lo = 0, hi = n - 1;
                while (lo <= hi) {
                    int mid = lo + (hi - lo) / 2;
                    if (matrix[i][mid] == target) return true;
                    else if (matrix[i][mid] < target) lo = mid + 1;
                    else hi = mid - 1;
                }
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(m × log n)

We iterate through at most m rows. For each row, we either skip it in O(1) (range check) or perform a binary search in O(log n). In the worst case, we might binary search one row and skip the rest, giving O(m + log n). However, the general bound is O(m × log n).

With m = 100 and n = 100, this is at most 100 × 7 ≈ 700 operations — much better than the brute force's 10,000.

Space Complexity: O(1)

We use only a constant number of variables (loop indices, binary search pointers). No extra data structures.

Why This Approach Is Not Efficient

The per-row binary search improves from O(m × n) to O(m × log n) by using binary search within each row. However, it still needs to iterate through rows linearly to find the correct one.

The fundamental limitation: we treat the matrix as m independent sorted arrays. But the problem guarantees something stronger — the first element of each row is greater than the last element of the previous row. This means the entire matrix, read left-to-right then top-to-bottom, forms a single sorted sequence.

Key insight: If the matrix is effectively one long sorted array of m × n elements, we can perform a single binary search over all m × n elements at once, achieving O(log(m × n)) time. The trick is mapping a 1D index back to 2D coordinates: row = index / n, col = index % n.

Optimal Approach - Flattened Binary Search

Intuition

Since the matrix has two sorting properties — rows are sorted AND each row starts after the previous row ends — the matrix is really just a sorted array laid out in 2D form.

Imagine unwinding the matrix into a single line: [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]. This is perfectly sorted! We can binary search this virtual array without actually creating it.

The key formula converts a 1D index to 2D coordinates:

  • row = index / n (integer division)
  • col = index % n (remainder)

For example, with n = 4 columns, virtual index 5 maps to row 5/4 = 1, col 5%4 = 1, which is matrix[1][1] = 11.

This lets us perform a single binary search over the entire m × n space in O(log(m × n)) time.

Step-by-Step Explanation

Let's trace with matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3. The matrix has m=3, n=4, so 12 total elements.

Step 1: Initialize: low = 0, high = 11 (= 3×4 - 1). We binary search over virtual indices 0 through 11.

Step 2: mid = (0 + 11) / 2 = 5. Map to 2D: row = 5/4 = 1, col = 5%4 = 1. matrix[1][1] = 11. Compare: 11 > 3 → search left half. Set high = 4.

Step 3: mid = (0 + 4) / 2 = 2. Map: row = 0, col = 2. matrix[0][2] = 5. Compare: 5 > 3 → search left. Set high = 1.

Step 4: mid = (0 + 1) / 2 = 0. Map: row = 0, col = 0. matrix[0][0] = 1. Compare: 1 < 3 → search right. Set low = 1.

Step 5: mid = (1 + 1) / 2 = 1. Map: row = 0, col = 1. matrix[0][1] = 3. Compare: 3 == 3 → Found!

Step 6: Return true. Found at matrix[0][1] in just 4 comparisons out of 12 possible elements. That is the power of O(log(m×n)).

Flattened Binary Search — Single Search Over Virtual 1D Array — Watch how we treat the 2D matrix as a single sorted array and perform one binary search. The search window halves at each step, converging on the target in O(log(m×n)) time.

Algorithm

  1. Set low = 0, high = m × n - 1
  2. While low ≤ high:
    • Compute mid = low + (high - low) / 2
    • Convert mid to 2D: row = mid / n, col = mid % n
    • If matrix[row][col] == target, return true
    • If matrix[row][col] < target, set low = mid + 1
    • Else set high = mid - 1
  3. Return false (target not found)

Code

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

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int val = matrix[mid / n][mid % n];

            if (val == target) return true;
            else if (val < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return false;
    }
};
class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        lo, hi = 0, m * n - 1

        while lo <= hi:
            mid = (lo + hi) // 2
            val = matrix[mid // n][mid % n]

            if val == target:
                return True
            elif val < target:
                lo = mid + 1
            else:
                hi = mid - 1

        return False
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int lo = 0, hi = m * n - 1;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int val = matrix[mid / n][mid % n];

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

Complexity Analysis

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

We perform a single binary search over m × n virtual elements. Each iteration halves the search space and does O(1) work (index conversion + comparison). The total iterations are at most log₂(m × n).

Since log(m × n) = log(m) + log(n), this is equivalent to O(log m + log n). With m = n = 100, this is at most log₂(10,000) ≈ 14 comparisons — dramatically fewer than the brute force's 10,000.

Space Complexity: O(1)

We use only three integer variables (lo, hi, mid) plus temporary variables for the index conversion. No additional data structures are needed — we access the matrix in-place using the conversion formula.