Search a 2D Matrix II

MediumBinary Searchtwo pointers

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an m x n integer grid matrix with two ordering guarantees: every row is sorted in non-decreasing order from left to right, and every column is sorted in non-decreasing order from top to bottom. Rows are **not** required to continue where the previous row ended, so the grid as a whole is not one sorted list. Return true if the integer target appears anywhere in matrix, and false otherwise. Aim for O(m + n) time. Scanning every cell works but ignores the structure the grid gives you.

Examples

Input: matrix = [[1,4,7,11],[2,5,8,12],[3,6,9,16],[10,13,14,17]], target = 9
Output: true
Start at the top-right `11` (too big, go left) to `7` (too small, go down) to `8` (too small, go down) to `9`, found at row 2, column 2.
Input: matrix = [[1,4,7,11],[2,5,8,12],[3,6,9,16],[10,13,14,17]], target = 15
Output: false
`15` would sit between `14` and `17` in the last row and between `12` and `16` in the last column, but no cell holds it.

Constraints

  • 1 <= m, n <= 300
  • -10^9 <= matrix[i][j], target <= 10^9
  • Each row is non-decreasing left to right
  • Each column is non-decreasing top to bottom

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More two pointers problems