PPractick

The problem

A heat-map tool stores sensor readings in a grid where every row increases left to right and every column increases top to bottom, but a row doesn't necessarily start after the previous one ends. So the grid isn't one sorted sequence, and flattening doesn't work. The elegant search starts at the top-right corner: everything to its left in the row is smaller, and everything below it in the column is larger. Each comparison eliminates an entire row or column, giving O(m + n).

Example: in the classic 5 × 5 grid below, target 5 → true, target 20 → false.

 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

Function signature

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

Test cases

Input (matrix, target)	Output	Explanation
(grid above, 5)	true
(grid above, 20)	false
([[1]], 1)	true
([[-5]], -10)	false
([[1, 1]], 2)	false	Duplicates are allowed

(Confirm: rows are sorted left to right and columns top to bottom (non-decreasing); the matrix is non-empty.)

How interviewers phrase it

• "Search a 2D matrix where each row and each column is sorted" (LeetCode 240).
• "Find an element in a matrix sorted row-wise and column-wise" (a classic).

Clarifying questions to ask

1. Are rows and columns both sorted in increasing order?
2. Does each row start after the previous one ends? (If yes, the simpler flattened search works.)
3. Return a boolean or the position?

Follow-ups to expect

1. "Why start at the top-right (or bottom-left)?"
2. "Why is it O(m + n)?"
3. "Could you binary-search each row?"
4. "What about divide and conquer?"
5. "How would you count the elements ≤ x?"

Related questions

• Search in a 2D matrix Medium
• Find Peak Element - II Medium
• Matrix Median Medium
• Swim in Rising Water Medium
• Find row with maximum 1's Easy
• Sort an array of 0's 1's and 2's Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in