62. Search a 2D Matrix
🔗 LeetCode Problem: 74. Search a 2D Matrix
📊 Difficulty: Medium
🏷️ Topics: Array, Binary Search, Matrix
Problem Statement
You are given an m x n integer matrix matrix with the following two properties:
- Each row is sorted in non-decreasing order.
- 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 matrix or false otherwise.
You must write a solution in O(log(m * n)) time complexity.
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:
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -10^4 <= matrix[i][j], target <= 10^4
🎨 Visual Understanding
The Problem Visualized
Matrix:
[
[ 1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 60]
]
Properties:
1. Each row sorted: 1 < 3 < 5 < 7
10 < 11 < 16 < 20
23 < 30 < 34 < 60
2. First of row > last of previous row:
10 > 7 ✓
23 > 20 ✓
This means: If we "flatten" the matrix, it's FULLY SORTED!
Flattened: [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
Example 1: target = 3
Matrix:
[
[ 1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 60]
]
↑
Found at position (0, 1)
Answer: true
Example 2: target = 13
Matrix:
[
[ 1, 3, 5, 7], (all < 13, too small)
[10, 11, 16, 20], (11 < 13 < 16, not present)
[23, 30, 34, 60] (all > 13, too large)
]
13 would be between 11 and 16, but it's not there
Answer: false
🚨 CRITICAL INSIGHT - Treat as 1D Sorted Array!
The Key Pattern!
The special property:
"First of each row > last of previous row"
This means: The matrix is essentially a SORTED 1D array
wrapped into 2D format!
Visualization:
2D Matrix:
[1, 3, 5, 7]
[10, 11, 16, 20]
[23, 30, 34, 60]
↓ Think of it as ↓
1D Array:
[1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
0 1 2 3 4 5 6 7 8 9 10 11 (indices)
Key Insight:
We can use CLASSIC BINARY SEARCH on the "virtual" 1D array!
Just need conversion:
1D index → 2D coordinates
mid → (row, col)
Index Conversion Formulas
Given:
Matrix: m rows × n columns
1D index: mid (0 to m*n-1)
Convert 1D index to 2D coordinates:
row = mid / n
col = mid % n
Example: 3 rows × 4 columns (12 elements total)
Matrix indices:
(0,0) (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
1D indices:
0 1 2 3
4 5 6 7
8 9 10 11
Conversions:
mid = 0 → row = 0/4 = 0, col = 0%4 = 0 → (0,0)
mid = 5 → row = 5/4 = 1, col = 5%4 = 1 → (1,1)
mid = 11 → row = 11/4 = 2, col = 11%4 = 3 → (2,3)
Formula works for ANY matrix size!
Binary Search on Virtual 1D Array
Treat matrix as virtual 1D array:
left = 0
right = m * n - 1 (total elements - 1)
Binary search:
mid = left + (right - left) / 2
row = mid / n
col = mid % n
value = matrix[row][col]
Compare value with target:
If value == target: found!
If value < target: search right
If value > target: search left
Example: Find 16 in 3×4 matrix
Virtual array: [1,3,5,7,10,11,16,20,23,30,34,60]
↑
target = 16
Binary search:
left = 0, right = 11
mid = 5 → (1,1) → value = 11 < 16
Search right: left = 6
mid = 8 → (2,0) → value = 23 > 16
Search left: right = 7
mid = 6 → (1,2) → value = 16 == 16
Found! ✓
🎯 Approach 1: Linear Search (Brute Force)
The Most Natural Thinking 💭
Core Logic:
Check each element in the matrix:
If element equals target, return true
If reach end, return false
Implementation
public boolean searchMatrix(int[][] matrix, int target) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == target) {
return true;
}
}
}
return false;
}
⏰ Time: O(m × n) - Check every element
💾 Space: O(1) - Only variables
❌ Problem: Doesn't meet O(log(m×n)) requirement! Doesn't use sorted property!
🎯 Approach 2: Binary Search (Treat as 1D) ⭐
Better Approach 💡
🧠 The Core Insight
The matrix is fully sorted when viewed as 1D array!
Strategy:
1. Treat as virtual 1D array
2. Use classic binary search on indices [0, m*n-1]
3. Convert mid index to (row, col) coordinates
4. Compare and eliminate half
Time: O(log(m × n)) ✓
The Strategy:
Binary Search on Virtual 1D Array:
1. left = 0, right = m * n - 1
2. While left <= right:
a. mid = left + (right - left) / 2
b. row = mid / n, col = mid % n
c. value = matrix[row][col]
d. If value == target: return true
e. If value < target: left = mid + 1
f. If value > target: right = mid - 1
3. return false
Implementation
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return false;
}
int m = matrix.length; // number of rows
int n = matrix[0].length; // number of columns
int left = 0;
int right = m * n - 1; // total elements - 1
while (left <= right) {
int mid = left + (right - left) / 2;
// Convert 1D index to 2D coordinates
int row = mid / n;
int col = mid % n;
int midValue = matrix[row][col];
if (midValue == target) {
return true; // Found!
}
if (midValue < target) {
left = mid + 1; // Search right half
} else {
right = mid - 1; // Search left half
}
}
return false; // Not found
}
⏰ Time: O(log(m × n)) - Binary search
💾 Space: O(1) - Only variables
🔍 Dry Run
Example 1: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Matrix dimensions: 3 rows × 4 columns = 12 elements
Virtual 1D array:
[1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
0 1 2 3 4 5 6 7 8 9 10 11
Initial: left = 0, right = 11
Iteration 1:
mid = 0 + (11 - 0) / 2 = 5
row = 5 / 4 = 1
col = 5 % 4 = 1
matrix[1][1] = 11
11 > 3, search left
right = 4
Virtual: [1, 3, 5, 7, 10]
↑ ↑
left right
Iteration 2:
mid = 0 + (4 - 0) / 2 = 2
row = 2 / 4 = 0
col = 2 % 4 = 2
matrix[0][2] = 5
5 > 3, search left
right = 1
Virtual: [1, 3]
↑ ↑
left right
Iteration 3:
mid = 0 + (1 - 0) / 2 = 0
row = 0 / 4 = 0
col = 0 % 4 = 0
matrix[0][0] = 1
1 < 3, search right
left = 1
Virtual: [3]
↑
left/right
Iteration 4:
mid = 1 + (1 - 1) / 2 = 1
row = 1 / 4 = 0
col = 1 % 4 = 1
matrix[0][1] = 3
3 == 3 ✓ FOUND!
return true
Example 2: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Virtual: [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
Initial: left = 0, right = 11
Iteration 1:
mid = 5
matrix[1][1] = 11 < 13
Search right
left = 6
Iteration 2:
mid = 8
matrix[2][0] = 23 > 13
Search left
right = 7
Iteration 3:
mid = 6
matrix[1][2] = 16 > 13
Search left
right = 5
Iteration 4:
mid = 5
matrix[1][1] = 11 < 13
Search right
left = 6
Now left > right (6 > 5)
Loop ends
return false ✓
Example 3: Single row matrix = [[1,3,5,7]], target = 5
Virtual: [1, 3, 5, 7]
Initial: left = 0, right = 3
Iteration 1:
mid = 1
row = 1 / 4 = 0
col = 1 % 4 = 1
matrix[0][1] = 3 < 5
left = 2
Iteration 2:
mid = 2
row = 2 / 4 = 0
col = 2 % 4 = 2
matrix[0][2] = 5 == 5 ✓
return true
🎯 Why This Works - Deep Dive
The Virtual 1D Array Concept:
═══════════════════════════════════════════════════════════════
Matrix properties guarantee:
1. Each row sorted
2. First of row > last of previous row
This means: Reading left-to-right, top-to-bottom gives
a FULLY SORTED sequence!
So we can pretend it's a 1D sorted array:
Just use index arithmetic to access 2D positions
Index Conversion Math:
═══════════════════════════════════════════════════════════════
For m×n matrix with 1D index mid:
row = mid / n
Why? Each row has n elements
Dividing by n gives which row we're in
col = mid % n
Why? Remainder gives position within row
Example: 3×4 matrix, mid = 7
row = 7 / 4 = 1 (second row, 0-indexed)
col = 7 % 4 = 3 (fourth column, 0-indexed)
Verification:
Indices in 3×4 matrix:
Row 0: 0 1 2 3
Row 1: 4 5 6 7 ← index 7 is here
Row 2: 8 9 10 11
Position (1, 3) ✓
Why This Is Efficient:
═══════════════════════════════════════════════════════════════
Total elements: m × n
Binary search iterations: log₂(m × n)
Each iteration: O(1)
- Calculate mid: O(1)
- Convert to 2D: O(1)
- Compare: O(1)
Total: O(log(m × n)) ✓
Compare with linear search: O(m × n)
Example: 10×10 matrix (100 elements)
Linear: 100 comparisons
Binary: 7 comparisons
14× faster!
Edge Cases Handled:
═══════════════════════════════════════════════════════════════
Empty matrix:
m = 0 or n = 0
Check at start, return false
Single element:
m = 1, n = 1
left = 0, right = 0
One iteration
Works correctly ✓
Single row/column:
Degrades to 1D binary search
Works correctly ✓
Target not present:
Loop exits when left > right
return false ✓
Alternative: Two Binary Searches
// Alternative approach (less elegant but same complexity)
public boolean searchMatrix(int[][] matrix, int target) {
// First BS: find row
// Second BS: search in that row
// Time: O(log m + log n) = O(log(m*n))
}
// But the 1D approach is cleaner and more intuitive!
⚠️ Common Mistakes to Avoid
Mistake 1: Wrong index conversion
// ❌ WRONG - Swapped formula
int row = mid % n; // Wrong!
int col = mid / n; // Wrong!
// ✓ CORRECT
int row = mid / n; // Divide for row
int col = mid % n; // Modulo for column
Mistake 2: Not checking empty matrix
// ❌ WRONG - Will crash on empty matrix
int n = matrix[0].length; // Crash if matrix empty!
// ✓ CORRECT - Check first
if (matrix == null || matrix.length == 0) {
return false;
}
Mistake 3: Wrong right boundary
// ❌ WRONG
int right = m * n; // Should be m * n - 1
// ✓ CORRECT
int right = m * n - 1; // Last valid index
Mistake 4: Using wrong comparison
// ❌ WRONG - Checking row instead of value
if (row == target) { // Row is index, not value!
return true;
}
// ✓ CORRECT - Check the actual value
if (matrix[row][col] == target) {
return true;
}
Mistake 5: Integer overflow in mid
// ❌ WRONG - Can overflow
int mid = (left + right) / 2;
// ✓ CORRECT - Safe calculation
int mid = left + (right - left) / 2;
🎯 Pattern Recognition
Problem Type: Binary Search - 2D Matrix as 1D Array
Core Pattern: Coordinate Conversion with Binary Search
When to Apply:
✓ Matrix is FULLY SORTED (special property)
✓ First of row > last of previous row
✓ Need to find specific element
✓ Need O(log(m×n)) time
✓ Can treat as virtual 1D array
Recognition Keywords:
- "2D matrix"
- "Sorted rows"
- "First of row > last of previous"
- "Search" or "find element"
- O(log(m×n)) complexity
Similar Problems:
- Search a 2D Matrix II (LC 240) - Different properties
- Find Peak Element II (LC 1901)
- Kth Smallest Element in Sorted Matrix (LC 378)
Key Difference from 2D Matrix II:
┌────────────────────────────────────────────┐
│ This Problem (LC 74): │
│ - First of row > last of previous │
│ - FULLY sorted as 1D │
│ - Binary search on virtual 1D │
│ - O(log(m×n)) │
│ │
│ Matrix II (LC 240): │
│ - Each row sorted, each col sorted │
│ - NOT fully sorted as 1D │
│ - Staircase search │
│ - O(m + n) │
└────────────────────────────────────────────┘
The "first > last" property is KEY!
🧠 Interview Strategy
Step 1: "Matrix fully sorted → Treat as 1D array"
Step 2: "Use binary search on indices [0, m×n-1]"
Step 3: "Convert mid to (row, col) with row=mid/n, col=mid%n"
Step 4: "Standard binary search comparison"
Step 5: "Return true if found, false otherwise"
Key Points to Mention:
- Recognize special property: first > last
- Matrix is fully sorted when flattened
- Treat as virtual 1D sorted array
- Convert 1D index to 2D coordinates
- row = mid / n, col = mid % n
- Classic binary search logic
- Time: O(log(m×n)), Space: O(1)
- Handle edge cases: empty matrix
Why This Approach?
"The matrix has a special property where the first element of
each row is greater than the last element of the previous row.
This means if I read the matrix left-to-right, top-to-bottom,
I get a fully sorted sequence. So I can treat it as a virtual
1D sorted array and use classic binary search. The key is
converting the 1D index to 2D coordinates using row = mid / n
and col = mid % n. This gives me O(log(m×n)) time complexity."
Index Conversion Explanation:
"Since each row has n elements, dividing the 1D index by n
gives me which row I'm in. The remainder (modulo n) gives me
the column position within that row. For example, in a 3×4
matrix, index 7 converts to row 1, column 3, which is correct."
Edge Cases:
✓ Empty matrix
✓ Single element
✓ Single row (degrades to 1D binary search)
✓ Target not present
📝 Quick Revision Notes
🎯 Core Concept:
2D Matrix as 1D Array: Matrix fully sorted due to special property. Treat as virtual 1D array, use binary search on indices [0, m×n-1]. Convert: row = mid / n, col = mid % n. Classic BS logic! O(log(m×n))!
⚡ Quick Implementation:
class Test {
public boolean searchMatrix(int[][] a, int k) {
// key concept - treat it as a 1D matrix (0, m*n-1) and
// getting (row, col) from that long index.
int rows = a.length;
int cols = a[0].length;
int left = 0;
int right = rows * cols - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// check intuitively
// Assume indices matrix: [[0,1,2,3],[4,5,6,7],[8,9,10,11]]
// rows = 3, cols = 4
// For index 5 => (5/4, 5%4) => (1,1)
// For index 7 => (7/4, 7%4) => (1,3)
// For index 8 => (8/4, 8%4) => (2,0)
int row = mid / cols;
int col = mid % cols;
if(a[row][col] == k) {
return true;
} else if(a[row][col] < k) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
public static void main(String[] args) {
Test t = new Test();
System.out.println(t.searchMatrix(new int[][] {{1,3,5,7},{10,11,16,20},{23,30,34,60}}, 3));
System.out.println(t.searchMatrix(new int[][] {{1,3,5,7},{10,11,16,20},{23,30,34,60}}, 13));
}
}
🔑 Key Insights:
- Pattern: 2D Matrix Treated as Virtual 1D Array
- Special Property: First of row > last of previous
- Fully Sorted: When read left-to-right, top-to-bottom
- Index Range: [0, m × n - 1]
- Convert 1D to 2D:
row = mid / n,col = mid % n - Standard BS: Same as classic binary search
- Time: O(log(m × n)), Space: O(1)
🎪 Memory Aid:
"Matrix sorted? Flatten to 1D! Divide for row, modulo for column!"
Think: "Virtual 1D → row = mid/n, col = mid%n"
💡 The Key Insight:
Special property makes matrix fully sorted:
First of row > last of previous
→ Read sequentially → sorted sequence
→ Use binary search on virtual 1D
Index conversion:
row = mid / n (which row?)
col = mid % n (which column in that row?)
⚠️ Critical Details:
1. Check: Empty matrix first
2. Dimensions: m = rows, n = columns
3. Range: left = 0, right = m*n - 1
4. Convert: row = mid / n, col = mid % n
5. Value: matrix[row][col]
6. Compare: Standard binary search
🔥 Visualization:
Matrix:
[ 1, 3, 5, 7] row 0
[10, 11, 16, 20] row 1
[23, 30, 34, 60] row 2
Virtual 1D:
[1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
0 1 2 3 4 5 6 7 8 9 10 11
mid = 6:
row = 6 / 4 = 1
col = 6 % 4 = 2
matrix[1][2] = 16 ✓
💡 Why It Works:
Each row has n elements:
Row 0: indices 0 to n-1
Row 1: indices n to 2n-1
Row 2: indices 2n to 3n-1
...
So index mid belongs to:
Row: mid / n (integer division)
Column: mid % n (remainder)
Perfect mapping! ✓
🧪 Edge Cases
Case 1: Empty matrix
Input: matrix = [], target = 5
Output: false
Case 2: Single element - found
Input: matrix = [[5]], target = 5
Output: true
Case 3: Single element - not found
Input: matrix = [[5]], target = 3
Output: false
Case 4: Single row
Input: matrix = [[1, 3, 5, 7]], target = 3
Output: true
(Degrades to 1D binary search)
Case 5: Single column
Input: matrix = [[1], [3], [5], [7]], target = 5
Output: true
Case 6: Target at corners
Input: matrix = [[1,3],[5,7]], target = 1
Output: true (top-left)
Input: matrix = [[1,3],[5,7]], target = 7
Output: true (bottom-right)
Case 7: Large matrix
Input: 100×100 matrix, target present
Output: true
Only ~13 comparisons needed! ✓
All handled correctly! ✓
Related Patterns
- Search a 2D Matrix II (LC 240) - Different sorted property
- Find Peak Element II (LC 1901) - 2D peak finding
- Kth Smallest in Sorted Matrix (LC 378) - Multiple sorted sequences
Happy practicing! 🎯
Note: This is a beautiful example of reducing 2D to 1D! The index conversion formulas (row = mid/n, col = mid%n) are crucial - memorize them!