Code Logo

Search a 2D Matrix

Published at24 Jul 2026
Created by
Medium 4 views
Like0

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has two properties: each row is sorted in ascending order from left to right, and the first integer of each row is greater than the last integer of the previous row. These properties mean the matrix can be treated as a single flattened sorted array.

The straightforward approach scans the matrix in O(m * n) time. Binary search treats the 2D grid as a 1D sorted array of length m * n. Compute the mid index, then convert it to row and column coordinates:row = mid / n, col = mid % n. Compare the value at that position with the target and narrow the search range accordingly.

The coordinate conversion is the key insight. Division and modulus of the mid index by the number of columns maps the flat index back to the 2D grid. This works because all rows have the same length (n) and the matrix is strictly row-major sorted.

Edge cases include a 1x1 matrix, a single row (becomes standard binary search), a single column, and the target being smaller or larger than all elements.

The coordinate conversion formula (r = mid / n, c = mid % n) works because the matrix is stored in row-major order. The division gives the row index, and the remainder gives the column. This avoids the need for two separate binary searches (first find row, then column). The time complexity O(log(m*n)) is strictly better than O(m + log n) found in some row-first approaches.

Example Input & Output

Example 1
Input
[[1,2,3],[4,5,6],[7,8,9]], 8
Output
true
Explanation

Target 8 at row 2 col 1.

Example 2
Input
[[1,3,5,7],[10,11,16,20],[23,30,34,60]], 13
Output
false
Explanation

Target 13 is not in matrix.

Example 3
Input
[[1,3,5,7],[10,11,16,20],[23,30,34,60]], 3
Output
true
Explanation

Target 3 is at row 0 col 1.

Example 4
Input
[[1]], 1
Output
true
Explanation

Single element matrix.

Example 5
Input
[[1]], 2
Output
false
Explanation

Target larger than the only element.

Algorithm Flow

Recommendation Algorithm Flow for Search a 2D Matrix

Solution Approach

Search for a target value in a 2D matrix where each row is sorted and each row starts with a value greater than the previous row's last value. Treat the matrix as a flattened sorted array and use binary search. Convert the mid index to row and column coordinates: row = Math.floor(mid / cols), col = mid % cols. Compare the matrix value at those coordinates with the target and adjust the search range accordingly.

function searchMatrix(matrix, target) {
  var rows = matrix.length, cols = matrix[0].length;
  var left = 0, right = rows * cols - 1;
  while (left <= right) {
    var mid = Math.floor((left + right) / 2);
    var val = matrix[Math.floor(mid / cols)][mid % cols];
    if (val === target) return true;
    if (val < target) left = mid + 1;
    else right = mid - 1;
  }
  return false;
}

The index-to-coordinate conversion maps a linear mid to the correct row and column without flattening the matrix into a separate array. The sorted property of the matrix allows standard binary search to work across all rows.

Time complexity is O(log(m*n)), space complexity is O(1).

Best Answers

java
class Solution {
    public boolean solution(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 r = mid / n, c = mid % n;
            if (matrix[r][c] == target) return true;
            if (matrix[r][c] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return false;
    }
}