LeetCode · #74

Search a 2D Matrix Solution

Given an m × n matrix with sorted rows and each row's first element greater than the previous row's last, determine if a target exists.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #74

🏗️

Pattern

Binary Search — virtual flattening

Write an efficient algorithm that searches for a value target in an m × n integer matrix. Each row is sorted left-to-right, and each row's first integer is greater than the previous row's last integer.

Example

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

Constraints

• m == matrix.length, n == matrix[i].length
• 1 ≤ m, n ≤ 100
• -10⁴ ≤ matrix[i][j] ≤ 10⁴

Section Two · Approach 1

Brute Force — O(m · n)

Scan every element. A better approach: binary search the rows to find the right row, then binary search within it — O(log m + log n). But the cleanest optimal solution treats the entire matrix as a single sorted array.

Problem: The matrix is fully sorted when read left-to-right, top-to-bottom. A single binary search on indices 0 to m·n−1, mapping index to row/col, gives O(log(m·n)).

Section Three · Approach 2

Flattened Binary Search — O(log(m·n))

Treat the 2D matrix as a virtual 1D sorted array. Index k maps to matrix[k / n][k % n]. Run standard binary search on indices 0 to m·n − 1.

💡 Mental model: Imagine unrolling the matrix into a single line. Row 0 becomes indices 0..n-1, row 1 becomes n..2n-1, etc. You never physically unroll it — just use arithmetic: row = mid / cols, col = mid % cols. Binary search works on this virtual flat array.

Algorithm

Step 1: left = 0, right = m*n - 1.
Step 2: Compute mid. Map: row = mid / n, col = mid % n.
Step 3: Compare matrix[row][col] to target. Standard binary search logic.

🎯 Alternative — two binary searches:

First binary search rows to find which row the target belongs to (compare target to row's first and last element).
Then binary search within that row. Same O(log m + log n) = O(log(m·n)) complexity, but slightly more code.

Section Four · Trace

Visual Walkthrough

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

Virtual flat array — binary search with index mapping

Section Five · Implementation

Code — Java & Python

Java — Flattened Binary Search

class Solution {
  public boolean searchMatrix(int[][] matrix, int target) {
      int m = matrix.length, n = matrix[0].length;
      int left = 0, right = m * n - 1;

      while (left <= right) {
          int mid = left + (right - left) / 2;
          int val = matrix[mid / n][mid % n];

          if (val == target) return true;
          else if (val < target) left = mid + 1;
          else right = mid - 1;
      }

      return false;
  }
}
  

Python — Flattened Binary Search

class Solution:
  def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
      m, n = len(matrix), len(matrix[0])
      left, right = 0, m * n - 1

      while left <= right:
          mid = (left + right) // 2
          val = matrix[mid // n][mid % n]

          if val == target: return True
          elif val < target: left = mid + 1
          else: right = mid - 1

      return False
  

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute Force	O(m · n)	O(1)	Scans every element
Staircase (top-right)	O(m + n)	O(1)	Works for LC 240 too but slower
Flattened Binary Search ← optimal	O(log(m·n))	O(1)	Virtual 1D array via index math

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
1×1 matrix	`[[5]], target=5`	Single element → mid=0 → found.
Single row	`[[1,3,5]]`	Degenerates to standard 1D binary search.
Single column	`[[1],[3],[5]]`	n=1; mid/1=row, mid%1=0. Works correctly.
Not found	`target=4`	Falls between 3 and 5 → L crosses R → false.

⚠ Common Mistake: Using mid / m instead of mid / n for the row. The number of columns (n) determines how many indices fit per row. row = mid / n, col = mid % n. Swapping m and n gives wrong coordinates.

← Back to Binary Search problems

LearningTree

LC 74 · Search a 2D Matrix — Solution & Explanation | DSA Guide