Search a 2D Matrix

Medium~15 min

Given an m x n matrix of integers where:

  • Each row is sorted in ascending order from left to right
  • The first element of each row is greater than the last element of the previous row

And a target integer, return true if target exists in the matrix, or false otherwise.

You must write a solution with O(log(m * n)) time complexity.

Examples

Example 1
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Explanation: 3 is found at row 0, column 1.
Example 2
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Explanation: 13 does not exist in the matrix.
Example 3
Input: matrix = [[1]], target = 1
Output: true
Explanation: The single element matches the target.

Constraints

  • 1 <= m, n <= 100
  • -10^4 <= matrix[i][j], target <= 10^4
  • Each row is sorted in ascending order
  • The first element of each row is greater than the last element of the previous row
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run