Search a 2D Matrix (LC 74)

Pattern: Binary Search (Virtual 1D Index on 2D Data)
Difficulty: Medium
Key Concept: Rows sorted + last of row < first of next row ⇒ the whole matrix is sorted in row-major order; map flat index mid to (row, col).

Problem Statement

You are given an m x n integer matrix with the following properties:

1. Every row is sorted in non-decreasing order.
2. The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in the matrix, otherwise false.

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

Input: int[][] matrix, int target
Output: boolean

---

1. Algorithm & Pseudocode

Brute force

for each row r:
    for each column c:
        if matrix[r][c] == target: return true
return false

Optimal — virtual sorted array

rows = matrix.length
cols = matrix[0].length
left = 0, right = rows * cols - 1
while left <= right:
    mid = left + (right - left) / 2
    r = mid / cols
    c = mid % cols
    val = matrix[r][c]
    if val == target: return true
    if val < target: left = mid + 1
    else: right = mid - 1
return false

Alternative (two-level binary search)

Binary search row: find last row whose first element <= target
If no such row: return false
Binary search within that row for target

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why the matrix behaves like one sorted array
   Condition (2) stitches rows together: everything in row i is less than everything in row i + 1. So reading row 0 left-to-right, then row 1, etc., is strictly non-decreasing.

2. Index mapping
   Flat index k corresponds to row = k / cols and col = k % cols (zero-based). That is standard row-major layout.

3. Why binary search works
   You can compare matrix[row][col] to target and eliminate half of the virtual index range [0, rows * cols - 1], just like a 1D sorted array.

4. Java 2D arrays
   matrix is an array of row arrays; cells are not necessarily contiguous in memory (unlike some C++ vector layouts). The logical order is still row-major, so the arithmetic mid / cols and mid % cols is valid.

5. Dimensions
   Use matrix.length for row count and matrix[0].length for column count (problem guarantees non-empty matrix).

---

3. The Dry Run

Matrix (3 rows × 4 columns):

	c0	c1	c2	c3
r0	1	3	5	7
r1	10	11	16	20
r2	23	30	34	60

rows = 3, cols = 4, n = 12, indices 0..11
Flat layout: [1,3,5,7,10,11,16,20,23,30,34,60]
Target: 3 → expect true (row 0, col 1 → flat index 1).

Step	left	right	mid	r	c	val	Action
init	0	11	—	—	—	—	enter loop
1	0	11	5	1	1	11	11 > 3 → right = 4
2	0	4	2	0	2	5	5 > 3 → right = 1
3	0	1	0	0	0	1	1 < 3 → left = 1
4	1	1	1	0	1	3	3 == 3 → return true

---

4. Java Solution

Brute Force

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int r = 0; r < matrix.length; r++) {
            for (int c = 0; c < matrix[r].length; c++) {
                if (matrix[r][c] == target) {
                    return true;
                }
            }
        }
        return false;
    }
}

Time: O(m × n). Space: O(1).

Optimal

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int left = 0;
        int right = rows * cols - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int r = mid / cols;
            int c = mid % cols;
            int val = matrix[r][c];
            if (val == target) {
                return true;
            }
            if (val < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

Time: O(log(m × n)). Space: O(1).

---

5. The “Java vs. Others” Edge

• Key expression: matrix[mid / cols][mid % cols] — same idea in any language; in Java pair with matrix.length and matrix[0].length.
• 2D storage: Java uses ragged possible rows in general; LC 74 assumes a full rectangle, so matrix[0].length is safe after the usual non-empty constraint.
• C++: A single vector<int> of size m*n would be physically contiguous; the logical mapping is identical.
• Alternative: Binary search on first column to pick a row, then binary search that row — still O(log m + log n).

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(m × n)	O(1)	Ignores global order.
Optimal (virtual 1D)	O(log(m × n))	O(1)	One BS on 0 .. m*n-1.
Row + in-row BS	O(log m + log n)	O(1)	Two binary searches; also acceptable where allowed.