What pattern does Search a 2D Matrix use?

The Pattern: Modified Binary Search (Two-Level Search in Sorted Matrix) The Heuristic: When a 2D matrix has sorted rows and each row's first element is greater than the previous row's last, treat the matrix as a sorted list of rows and apply binary search twice: first to locate the candidate row, then to locate the target within that row.

Search a 2D Matrix — Modified Binary Search

Q: How do you solve Search a 2D Matrix?

Perform a binary search on the rows to find the row where the target could reside by comparing the target with the first and last elements of the middle row. Once the candidate row is identified, perform a binary search within that row to find the target. Return true if found, otherwise false.

Q: What is the time complexity of Search a 2D Matrix?

O(log m + log n). The algorithm performs two binary searches: one over m rows and one over n columns. Each binary search takes O(log m) and O(log n) respectively, resulting in O(log m + log n) total time.

Problem

Given an m x n matrix where each row is sorted in ascending order and the first integer of each row is greater than the last integer of the previous row, return true if target is in the matrix or false otherwise.

m == matrix.length
n == matrix[i].length
1 ≤ m, n ≤ 100
−10⁴ ≤ matrix[i][j], target ≤ 10⁴
Each row is sorted in ascending order.
The first integer of each row is greater than the last integer of the previous row.

Example

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

Output: true

The algorithm first performs a binary search over the rows to find the candidate row that could contain the target. For target = 3, it compares 3 with the last element of the middle row (row 1: 20). Since 3 < 20, it narrows the search to the top half. It then checks if 3 is greater than or equal to the first element of the candidate row. Once the candidate row is found (row 0), a second binary search is performed within that row. The target 3 is found at index 1, so the algorithm returns true.

Approach

Straightforward Solution

A brute-force approach would scan every element in the matrix, resulting in O(m*n) time complexity, which is inefficient for large matrices.

Core Observation

The matrix can be viewed as a sorted list of rows, each sorted internally, with the property that the first element of a row is greater than the last element of the previous row. This allows a two-level binary search: first to find the candidate row, then to find the target within that row.

Path to Optimal

Preview

The key recognition signals are 'sorted rows' and 'first integer of each row greater than last integer of previous row'…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Perform a binary search on the rows to find the row where the target could reside by comparing the target with the first and last elements of the middle row. Once the candidate row is identified, perform a binary search within that row to find the target…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(log m + log n)

The algorithm performs two binary searches: one over m rows and one over n columns. Each binary search takes O(log m) and O(log n) respectively, resulting in O(log m + log n) total time.

Space

O(1)

The algorithm uses only a fixed number of variables for indices and does not allocate additional data structures proportional to input size, resulting in constant auxiliary space.

Solution

Python

1class Solution:
  def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
      ROWS, COLS = len(matrix), len(matrix[0])
      top, bot = 0, ROWS - 1
5
      while top <= bot:
          row = (top + bot) // 2
          if target > matrix[row][-1]:
              top = row + 1
          elif target < matrix[row][0]:
              bot = row - 1
          else:
              break
      
      if not (top <= bot):
          return False
      
      row = (top + bot) // 2
      l, r = 0, COLS - 1
      while l <= r:
          m = (l + r) // 2
          if target > matrix[row][m]:
              l = m + 1
          elif target < matrix[row][m]:
              r = m - 1
          else:
              return True
      
      return False

Step-by-Step Solution

1

Locate Candidate Row Using Binary Search on Row Boundaries

3ROWS, COLS = len(matrix), len(matrix[0])
4top, bot = 0, ROWS - 1
6while top <= bot:
  row = (top + bot) // 2
  if target > matrix[row][-1]:
      top = row + 1
  elif target < matrix[row][0]:
      bot = row - 1
  else:
      break

Objective

To identify the row that could contain the target by comparing the target with the first and last elements of the middle row.

Key Insight

Because each row is sorted and the first element of each row is greater than the last element of the previous row, the target must lie within a single row whose first element is less than or equal to the target and last element is greater than or equal to the target. Binary searching over the rows using these boundary checks efficiently narrows down the candidate row in O(log m) time.

Interview Quick-Check

Core Logic

Binary search over rows compares the target with the first and last elements of the middle row to decide whether to move up or down the row range.

State & Boundaries

The loop continues while top <= bot, ensuring all candidate rows are considered.

Common Pitfalls & Bugs

Failing to check both the first and last elements of the row can lead to incorrect candidate row selection.

2

Confirm Candidate Row and Return False if None Found

To verify if a candidate row was found and return false immediately if the target cannot be in any row.

3

Perform Binary Search Within Candidate Row to Find Target

To locate the target within the identified candidate row using standard binary search.

4

Return False When Target is Not Found in Candidate Row

To return false after exhausting the binary search within the candidate row without finding the target.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 6 Critical lines interviewers watch for.

Line 27 Critical

return True

Return true when the target is found.

Finding the target confirms its presence in the matrix and ends the search immediately.

Line 13 Critical

break

Stop the row search once a candidate row is found.

Breaking preserves the identified candidate row for the second binary search.

Line 15 Critical

if not (top <= bot):

Check whether no candidate row was found.

If the row search ended without a candidate row, the target cannot be in the matrix.

Full line-by-line criticality + rationale for all 23 lines available on Pro.

Test Your Understanding

Why is it necessary to perform two separate binary searches instead of a single binary search treating the matrix as a flattened sorted array?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Search a 2D Matrix from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Search a 2D Matrix drill

or drill a free problem

1	`class Solution:`
2	`def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:`
3	`ROWS, COLS = len(matrix), len(matrix[0])`
4	`top, bot = 0, ROWS - 1`
5
6	`while top <= bot:`
7	`row = (top + bot) // 2`
8	`if target > matrix[row][-1]:`
9	`top = row + 1`
10	`elif target < matrix[row][0]:`
11	`bot = row - 1`
12	`else:`
13	`break`
14
15	`if not (top <= bot):`
16	`return False`
17
18	`row = (top + bot) // 2`
19	`l, r = 0, COLS - 1`
20	`while l <= r:`
21	`m = (l + r) // 2`
22	`if target > matrix[row][m]:`
23	`l = m + 1`
24	`elif target < matrix[row][m]:`
25	`r = m - 1`
26	`else:`
27	`return True`
28
29	`return False`

3	`ROWS, COLS = len(matrix), len(matrix[0])`
4	`top, bot = 0, ROWS - 1`
6	`while top <= bot:`
7	`row = (top + bot) // 2`
8	`if target > matrix[row][-1]:`
9	`top = row + 1`
10	`elif target < matrix[row][0]:`
11	`bot = row - 1`
12	`else:`
13	`break`