Search a 2D Matrix 20 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

Given an m × n matrix where each row is sorted and the first element of each row is greater than the last element of the previous row, determine if a target value exists.

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

Key insight: treat the 2D matrix as a single sorted array. If there are m rows and n columns, index i maps to matrix[i // n][i % n].

Then run standard binary search on indices 0 to m*n - 1. Time: O(log(m*n)).

📋 Instructions

Implement `search_matrix(matrix, target)` using binary search. Test with the matrix above and targets 3 and 13. Print both results.

Total elements = rows * cols. Binary search on [0, total-1]. Convert mid to row = mid // cols, col = mid % cols.

🧪 Test Cases

Input

search_matrix(matrix, 3)

Expected

True

Boolean check

Input

search_matrix(matrix, 13)

Expected

False

Boolean check

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›