Search a 2D Matrix

MediumBinary Searchbinary search

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 that satisfies two ordering properties: - Within every individual row, the values are sorted in strictly increasing order from left to right. - The first value of each row is strictly greater than the last value of the row directly above it. Given an integer target, return true if target appears somewhere in matrix, and false otherwise. Because of the two properties above, the matrix behaves like one long sorted list when read row by row. Your solution should take advantage of this and run in O(log(m * n)) time rather than scanning every cell.

Examples

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 16
Output: true
The value 16 sits in the second row, third column, so it exists in the matrix.
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
13 would fall between 11 and 16 in the second row but is not present, so it is absent from the matrix.
Input: matrix = [[1]], target = 1
Output: true
The single cell equals the target.

Constraints

  • `m == matrix.length`
  • `n == matrix[i].length`
  • `1 <= m, n <= 100`
  • `-10^4 <= matrix[i][j], target <= 10^4`
  • Each row is sorted ascending, and the first element of each row exceeds the last element of the previous row.

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 binary search problems