Code Logo

Search a 2D Matrix

Published at24 Jul 2026
Created by
Medium 0 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
Recommendation Algorithm Flow for Search a 2D Matrix

Solution Approach

Treat matrix as flattened sorted array. Binary search with index-to-coordinate conversion.

function solution(matrix, target) {
  var m = matrix.length, n = matrix[0].length;
  var lo = 0, hi = m * n - 1;
  while (lo <= hi) {
    var mid = Math.floor((lo + hi) / 2);
    var r = Math.floor(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;
}

Time O(log(m*n)), Space 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;
    }
}