Search 2D Matrix
Mahabharata — The Tablet of Laws — Finding a Number in the Sacred Grid
द्विमात्रीय तालिका — एकमात्रीय सारणी की तरह। mid/n पंक्ति, mid%n स्तम्भ — एकल खोज में॥
*Two-dimensional table — treat it as a one-dimensional array. Row=mid/n, col=mid%n — find in one search.*
The Story
A 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. Find the target.
For `matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,60]]`, target=3: return true (row 0, col 1).
**Key insight:** This matrix is essentially a sorted 1D array laid out in rows. The element at 1D index `i` is `matrix[i/n][i%n]`.
Apply standard binary search on [0, m×n-1]: ```java int left=0, right=m*n-1; while (left <= right) { int mid = (left+right)/2; int val = matrix[mid/n][mid%n]; if (val == target) return true; if (val < target) left=mid+1; else right=mid-1; } return false; ```
Trace for target=3: - m=3,n=4, l=0,r=11 - mid=5, matrix[5/4][5%4]=matrix[1][1]=11 > 3 → r=4 - mid=2, matrix[0][2]=5 > 3 → r=1 - mid=0, matrix[0][0]=1 < 3 → l=1 - mid=1, matrix[0][1]=3 == 3 → return true ✓
"The matrix's sorting property means the 1D interpretation is perfectly sorted," Krishna noted. "One binary search covers all m×n elements."
The Row-by-Row Scanner
Binary search each row: find the row using first-column binary search, then binary search within that row. O(log m + log n) = O(log(mn)).
public boolean searchMatrixBruteForce(int[][] matrix, int target) {
for (int[] row : matrix)
for (int val : row)
if (val == target) return true;
return false;
}Krishna's 2D-to-1D Mapping Wisdom
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;
if (val < target) left = mid + 1;
else right = mid - 1;
}
return false;
}Step-by-Step Walkthrough
[[1]], target=1 l=0,r=0,mid=0,matrix[0][0]=1==1→true ✅ [[1],[3]], target=2 m=2,n=1. l=0,r=1 mid=0,matrix[0][0]=1<2→l=1 mid=1,matrix[1][0]=3>2→r=0 l>r→false ✅
Deep Insight
**bs-19 vs bs-20:** Two different matrix search problems! - bs-19: rows fully sorted AND row[i][n-1] < row[i+1][0] → perfect 1D mapping → O(log mn) - bs-20: each row and column sorted individually → use staircase search → O(m+n)
The stronger guarantee in bs-19 enables the faster solution.
**Integer division trick:** `mid/n` gives the row (floor division), `mid%n` gives the column (remainder). This correctly maps any 1D index to 2D coordinates.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(mn) | O(1) | Scan all elements |
| Optimal | O(log(mn)) | O(1) | Single binary search on 1D representation |
Pattern Recognition
✅ Fully sorted matrix (each row sorted + row continuity) ✅ Treat as 1D array: matrix[mid/n][mid%n] ✅ Standard binary search template ✅ Distinct from bs-20 (weaker sorting guarantee) **LeetCode Trigger Phrases:** → "search a 2D matrix" (first integer of row > last of previous row) → Fully sorted 2D → 1D binary search → mid/n, mid%n coordinate mapping
Bhagavad Gita 18.78
यत्र योगेश्वरः कृष्णो यत्र पार्थो धनुर्धरः। तत्र श्रीर्विजयो भूतिर्ध्रुवा नीतिर्मतिर्मम॥
Wherever there is Krishna, the Lord of Yoga, and wherever there is Arjuna the archer — there will surely be prosperity, victory, wealth, and sound morality.
Connection: The 2D matrix appears complex — rows and columns, a two-dimensional challenge. But the algorithm reveals its hidden unity: beneath the two-dimensional appearance lies a single sorted sequence. Like Krishna's revelation that beneath all apparent diversity lies one unified truth, the 1D mapping collapses the matrix into a simple sorted array, and the familiar binary search finds its target with perfect certainty.