Search an element in a matrix
Problem
Return true if target is in the matrix. There are two common variants: (a) each row is sorted and each row starts after the previous row ends (fully sorted in row-major order); (b) every row and every column is sorted on its own.
Example 1
Input: [[1,3,5,7], [10,11,16,20], [23,30,34,60]], target = 3 Output: true
Also asked as: Search an element in a matriix
Test cases
Case 1
Input: [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], 5 Expected: [1,1]
Case 2
Input: [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], 20 Expected: null
Case 3
Input: [[1]], 1 Expected: [0,0]
View solutionHide solution2 approaches
1. Staircase search (rows & columns sorted)
Time O(R + C)Space O(1)
Start at the top-right. If it is bigger than target move left, if smaller move down. Each step eliminates a row or column.
function searchMatrix(m, target) { let r = 0, c = m[0].length - 1; while (r < m.length && c >= 0) { if (m[r][c] === target) return [r, c]; m[r][c] > target ? c-- : r++; } return null;}2. Binary search (fully sorted, row-major)
Time O(log(R·C))Space O(1)
Treat the R·C cells as one sorted array; map index → (row, col).
function searchMatrix(m, target) { const R = m.length, C = m[0].length; let lo = 0, hi = R * C - 1; while (lo <= hi) { const mid = (lo + hi) >> 1; const v = m[Math.floor(mid / C)][mid % C]; if (v === target) return true; v < target ? (lo = mid + 1) : (hi = mid - 1); } return false;}