DSA interview question

Search a 2D Matrix

Medium · Algorithms · Topics: binary search, matrix

The problem

A spreadsheet app stores a large table where each row is sorted and each row starts after the previous row ends, so reading the rows left to right, top to bottom gives one long sorted sequence. The "find" feature must say whether a value exists in O(log(m·n)). The trick is not to search row by row: treat the whole matrix as a single sorted array of length m·n, and convert a 1D index into a row and column with division and modulo.

Example: [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target 3 → true.

Function signature

bool searchMatrix(const vector<vector<int>>& matrix, int target);

Test cases

Input `(matrix, target)`	Output	Explanation
`([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 3)`	true
`([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 13)`	false	Would sit between 11 and 16
`([[1]], 1)`	true
`([[1]], 2)`	false
`([[1, 3]], 3)`	true	A single row
`([[1], [3]], 3)`	true	A single column

(Confirm: every row is sorted and each row's first element is greater than the previous row's last element.)

How interviewers phrase it

"Search a 2D matrix" (LeetCode 74).
Often followed by the harder variant where only rows and columns are sorted independently (LeetCode 240, S.No 131).

Clarifying questions to ask

Is the matrix sorted row by row, with each row starting after the previous row ends?
Return a boolean or the position?
Can the matrix be empty?

Follow-ups to expect

"How do you map a 1D index to the matrix?"
"What's the complexity?"
"Could you do two binary searches instead?"
"What if only rows and columns are sorted separately?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview