Search a 2D Matrix

Asked byFacebookAmazonMicrosoftBloombergAppleAdobe

Problem

Given an m x n matrix where each row is sorted ascending and the first number of each row is greater than the last number of the previous row, determine whether a target value exists in the matrix, in O(log(m·n)) time.

Examples

Example 1

Input:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

Output:true

Example 2

Input:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

Output:false

Constraints

1 <= m, n <= 100

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Binary Search pattern

Repeatedly halve the search space by comparing the middle element to a target, turning an O(n) scan into O(log n). It works on more than sorted arrays — any "answer space" that's monotonic (true…true…false…false) can be binary searched.

Look for this pattern when

The input is sorted, or partially sorted (like a rotated sorted array).
You're minimizing or maximizing a value where "is X feasible?" is easy to check and feasibility is monotonic.

Read the full Binary Search guide →

Video walkthroughs

Original problem on LeetCode ↗