Search an element in a matrix

Medium

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}