101
0/276
Loading content...
In the previous pages, we explored matrices where rows and columns are independently sorted—a structure that enables O(m + n) staircase search. But what if the matrix has an even stronger property? What if the entire matrix, when read row by row, forms a single sorted sequence?
This is the fully sorted matrix: the last element of each row is less than or equal to the first element of the next row. This seemingly simple additional constraint transforms the 2D search problem into a disguised 1D binary search, achieving O(log(m × n)) time complexity.
This page teaches you to recognize fully sorted matrices, understand the 1D-2D coordinate transformation, and implement the classic binary search approach that treats the matrix as a virtual linear array.
By the end of this page, you will understand what makes a matrix 'fully sorted,' derive the mathematical transformation between 1D indices and 2D coordinates, implement O(log(m × n)) binary search for fully sorted matrices, and distinguish when to use this approach versus staircase search.
A fully sorted matrix (also called a row-wise sorted matrix or strictly sorted matrix) has elements that, when read left-to-right and top-to-bottom, form a non-decreasing sequence.
Formal Definition:
A matrix M of dimensions m × n is fully sorted if and only if:
For all positions (i₁, j₁) and (i₂, j₂):
If (i₁ < i₂) OR (i₁ == i₂ AND j₁ < j₂):
M[i₁][j₁] ≤ M[i₂][j₂]
Equivalently, this means:
i is less than or equal to the first element of row i+1This second condition is the key differentiator from row-and-column-sorted matrices.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849
# Fully sorted matrix example# Reading left-to-right, top-to-bottom gives: 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 50 fully_sorted = [ [1, 3, 5, 7], # Row 0: 1 ≤ 3 ≤ 5 ≤ 7 [10, 11, 16, 20], # Row 1: 10 ≤ 11 ≤ 16 ≤ 20, and 7 ≤ 10 (row boundary) [23, 30, 34, 50] # Row 2: 23 ≤ 30 ≤ 34 ≤ 50, and 20 ≤ 23 (row boundary)] # Key observation: row 0 ends with 7, row 1 starts with 10 → 7 ≤ 10 ✓# row 1 ends with 20, row 2 starts with 23 → 20 ≤ 23 ✓ def is_fully_sorted(matrix): """ Verify if a matrix is fully sorted. Checks both intra-row ordering and inter-row boundary conditions. """ if not matrix or not matrix[0]: return True m, n = len(matrix), len(matrix[0]) # Check intra-row ordering for i in range(m): for j in range(n - 1): if matrix[i][j] > matrix[i][j + 1]: return False # Check inter-row boundary (last element ≤ first of next row) for i in range(m - 1): if matrix[i][n - 1] > matrix[i + 1][0]: return False return True # Compare with row-and-column-sorted (not fully sorted)row_column_sorted = [ [1, 4, 7, 11], [2, 5, 8, 12], # 2 < 11 from previous row! [3, 6, 9, 16]] print(f"Fully sorted matrix: {is_fully_sorted(fully_sorted)}") # Trueprint(f"Row-column sorted matrix: {is_fully_sorted(row_column_sorted)}") # False # The row-column sorted matrix fails because:# Row 0 ends with 11, Row 1 starts with 2 → 11 > 2, violates full sortingNot every row-and-column-sorted matrix is fully sorted! In a row-and-column-sorted matrix, M[1][0] ≤ M[0][n-1] is NOT guaranteed. Fully sorted requires the additional constraint that reading row-by-row produces a sorted sequence. Always verify which structure the problem provides.
The key insight is that a fully sorted m × n matrix is isomorphic to a sorted 1D array of length m × n. We just need a bijection between:
k where 0 ≤ k < m × nThe Transformations:
1D → 2D (given k, find row and col):
row = k // n (integer division by column count)
col = k % n (remainder gives column position)
2D → 1D (given row and col, find k):
k = row × n + col
This is simply the standard row-major indexing used in most programming languages.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960
def to_2d(k, n): """ Convert 1D index to 2D (row, col) coordinates. Args: k: 1D index (0 to m*n - 1) n: Number of columns in the matrix Returns: (row, col) tuple """ row = k // n col = k % n return (row, col) def to_1d(row, col, n): """ Convert 2D (row, col) to 1D index. Args: row: Row index col: Column index n: Number of columns in the matrix Returns: 1D index """ return row * n + col # Example: 3×4 matrix (12 elements)# Index layout:# [ 0 1 2 3] (row 0)# [ 4 5 6 7] (row 1)# [ 8 9 10 11] (row 2) m, n = 3, 4 # Test: 1D → 2Dfor k in range(m * n): row, col = to_2d(k, n) print(f"k={k:2} → ({row}, {col})") print() # Test: 2D → 1Dfor row in range(m): for col in range(n): k = to_1d(row, col, n) print(f"({row}, {col}) → k={k:2}") # Verify round-trip consistencyfor k in range(m * n): row, col = to_2d(k, n) k_recovered = to_1d(row, col, n) assert k == k_recovered, f"Round-trip failed for k={k}" print("\nAll round-trip conversions verified!")Visual Mapping:
1D Index: 0 1 2 3 4 5 6 7 8 9 10 11
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
2D Matrix: [a₀ a₁ a₂ a₃] [a₄ a₅ a₆ a₇] [a₈ a₉ a₁₀ a₁₁]
└── Row 0 ──┘ └── Row 1 ──┘ └── Row 2 ──┘
For n=4 columns:
- k=5 → row = 5//4 = 1, col = 5%4 = 1 → position (1,1)
- k=9 → row = 9//4 = 2, col = 9%4 = 1 → position (2,1)
This transformation allows us to run standard binary search using 1D indices while accessing elements using 2D coordinates.
The transformation works because a fully sorted matrix IS a 1D sorted array that happens to be stored with a line break every n elements. The matrix structure is just a presentation choice—the underlying sorted sequence is linear. Binary search operates on the linear sequence; we just need to translate indices when accessing elements.
With the index transformation in hand, implementing binary search is straightforward. We perform standard binary search on the 1D index range [0, m×n - 1], converting to 2D coordinates only when we need to access matrix elements.
Algorithm:
Input: Fully sorted m×n matrix M, target value T
Output: (row, col) if T found, (-1, -1) otherwise
1. left = 0, right = m × n - 1
2. While left ≤ right:
a. mid = (left + right) // 2
b. (row, col) = to_2d(mid, n)
c. current = M[row][col]
d. If current == T: return (row, col)
e. If current < T: left = mid + 1
f. If current > T: right = mid - 1
3. Return (-1, -1)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
def search_fully_sorted_matrix(matrix, target): """ Binary search in a fully sorted matrix. Treats the matrix as a virtual 1D sorted array and performs standard binary search with 1D-to-2D coordinate conversion. Time Complexity: O(log(m × n)) Space Complexity: O(1) Args: matrix: Fully sorted 2D matrix (row-major sorted) target: Value to search for Returns: (row, col) if found, (-1, -1) if not found """ if not matrix or not matrix[0]: return (-1, -1) m, n = len(matrix), len(matrix[0]) # Binary search on virtual 1D array left, right = 0, m * n - 1 while left <= right: mid = (left + right) // 2 # Convert 1D index to 2D coordinates row = mid // n col = mid % n current = matrix[row][col] if current == target: return (row, col) # Found! elif current < target: left = mid + 1 # Target in right half else: right = mid - 1 # Target in left half return (-1, -1) # Not found # Test with fully sorted matrixmatrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]] # Test various targetstest_cases = [3, 10, 50, 13, 0, 100] for target in test_cases: result = search_fully_sorted_matrix(matrix, target) if result != (-1, -1): row, col = result print(f"Target {target}: Found at ({row}, {col}), value = {matrix[row][col]}") else: print(f"Target {target}: Not found") # Output:# Target 3: Found at (0, 1), value = 3# Target 10: Found at (1, 0), value = 10# Target 50: Found at (2, 3), value = 50# Target 13: Not found# Target 0: Not found# Target 100: Not foundFor a 1000×1000 matrix, staircase search makes at most 2000 comparisons. Binary search on a fully sorted matrix makes at most log₂(1,000,000) ≈ 20 comparisons. When the fully sorted property holds, binary search is dramatically faster!
Let's trace through a complete example to solidify understanding.
Matrix (3 × 4):
[1 3 5 7 ] indices 0-3
[10 11 16 20] indices 4-7
[23 30 34 50] indices 8-11
Searching for target = 16:
| Iteration | left | right | mid | (row, col) | value | Comparison | Action |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 11 | 5 | (1, 1) | 11 | 11 < 16 | left = 6 |
| 2 | 6 | 11 | 8 | (2, 0) | 23 | 23 > 16 | right = 7 |
| 3 | 6 | 7 | 6 | (1, 2) | 16 | 16 == 16 | FOUND! |
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849
def search_with_trace(matrix, target): """ Binary search with detailed trace output. """ if not matrix or not matrix[0]: return (-1, -1) m, n = len(matrix), len(matrix[0]) left, right = 0, m * n - 1 iteration = 0 print(f"Matrix dimensions: {m}×{n} = {m*n} elements") print(f"Searching for target: {target}") print("-" * 70) print(f"{'Iter':>4} {'left':>5} {'right':>5} {'mid':>5} {'(r,c)':>8} {'value':>6} {'action':<15}") print("-" * 70) while left <= right: iteration += 1 mid = (left + right) // 2 row, col = mid // n, mid % n current = matrix[row][col] if current == target: print(f"{iteration:>4} {left:>5} {right:>5} {mid:>5} ({row},{col}):>8 {current:>6} {'FOUND!':<15}") return (row, col) elif current < target: print(f"{iteration:>4} {left:>5} {right:>5} {mid:>5} ({row},{col}):>8 {current:>6} {'left = mid+1':<15}") left = mid + 1 else: print(f"{iteration:>4} {left:>5} {right:>5} {mid:>5} ({row},{col}):>8 {current:>6} {'right = mid-1':<15}") right = mid - 1 print(f"{'':>4} {left:>5} {right:>5} {'':>5} {'':>8} {'':>6} {'NOT FOUND':<15}") return (-1, -1) # Example matrixmatrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]] # Trace several searchesfor target in [16, 1, 50, 13]: print(f"\n{'='*70}") result = search_with_trace(matrix, target) print(f"Result: {result}")For a 3×4 matrix (12 elements), we needed only 3 comparisons to find target 16. For a 100×100 matrix (10,000 elements), we'd need at most ⌈log₂(10000)⌉ = 14 comparisons. The search space halves with each comparison.
A production-ready implementation must handle various edge cases gracefully:
Edge Cases:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
def search_matrix_robust(matrix, target): """ Production-ready binary search for fully sorted matrix. Handles all edge cases and potential pitfalls. """ # Edge case 1: Null or empty matrix if not matrix: return False # Or return (-1, -1) depending on requirements if not matrix[0]: return False m, n = len(matrix), len(matrix[0]) total = m * n # Edge case 2: Quick rejection if outside range if target < matrix[0][0] or target > matrix[m-1][n-1]: return False left, right = 0, total - 1 while left <= right: # Edge case 3: Overflow-safe mid calculation # For very large matrices, (left + right) might overflow in some languages # This is safe in Python (arbitrary precision), but good practice mid = left + (right - left) // 2 # Convert to 2D row = mid // n col = mid % n current = matrix[row][col] if current == target: return True # Or return (row, col) elif current < target: left = mid + 1 else: right = mid - 1 return False # Comprehensive test suitedef run_tests(): # Test 1: Empty matrix assert search_matrix_robust([], 5) == False assert search_matrix_robust([[]], 5) == False print("✓ Empty matrix handled") # Test 2: Single element assert search_matrix_robust([[5]], 5) == True assert search_matrix_robust([[5]], 3) == False print("✓ Single element handled") # Test 3: Single row assert search_matrix_robust([[1, 3, 5, 7]], 3) == True assert search_matrix_robust([[1, 3, 5, 7]], 4) == False print("✓ Single row handled") # Test 4: Single column assert search_matrix_robust([[1], [3], [5]], 3) == True assert search_matrix_robust([[1], [3], [5]], 2) == False print("✓ Single column handled") # Test 5: Standard matrix matrix = [[1, 3, 5], [10, 11, 16], [23, 30, 34]] assert search_matrix_robust(matrix, 5) == True assert search_matrix_robust(matrix, 16) == True assert search_matrix_robust(matrix, 13) == False print("✓ Standard matrix handled") # Test 6: Boundary targets assert search_matrix_robust(matrix, 1) == True # First element assert search_matrix_robust(matrix, 34) == True # Last element print("✓ Boundary elements handled") # Test 7: Outside range assert search_matrix_robust(matrix, 0) == False # Below minimum assert search_matrix_robust(matrix, 100) == False # Above maximum print("✓ Out of range handled") # Test 8: Duplicates matrix_dups = [[1, 1, 1], [2, 2, 2], [3, 3, 3]] assert search_matrix_robust(matrix_dups, 2) == True print("✓ Duplicates handled") print("\nAll tests passed!") run_tests()In languages like Java or C++, computing mid = (left + right) / 2 can overflow for large arrays. Always use mid = left + (right - left) / 2 instead. Python handles arbitrary precision integers, but it's good practice to use the safe form universally.
Choosing between staircase search and 1D binary search depends on the matrix structure. Using the wrong algorithm for the given structure can lead to incorrect results.
Decision Framework:
| Matrix Property | Best Algorithm | Time Complexity | Notes |
|---|---|---|---|
| Fully sorted (row ends ≤ next row start) | Binary search (1D) | O(log(m×n)) | Optimal; treat as 1D array |
| Row-and-column sorted (no inter-row guarantee) | Staircase search | O(m + n) | 1D binary search would fail! |
| Row-sorted only | Binary search per row | O(m × log n) | Or binary search on first column, then row |
| Column-sorted only | Binary search per column | O(n × log m) | Symmetric to row-sorted |
| Unsorted | Linear scan | O(m × n) | No structure to exploit |
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132
def detect_matrix_type(matrix): """ Analyze matrix structure and recommend appropriate search algorithm. """ if not matrix or not matrix[0]: return "empty", None m, n = len(matrix), len(matrix[0]) # Check row-sorted row_sorted = True for i in range(m): for j in range(n - 1): if matrix[i][j] > matrix[i][j + 1]: row_sorted = False break if not row_sorted: break # Check column-sorted col_sorted = True for j in range(n): for i in range(m - 1): if matrix[i][j] > matrix[i + 1][j]: col_sorted = False break if not col_sorted: break # Check fully-sorted (row-sorted + inter-row ordering) fully_sorted = row_sorted if fully_sorted: for i in range(m - 1): if matrix[i][n - 1] > matrix[i + 1][0]: fully_sorted = False break # Recommend algorithm if fully_sorted: return "fully_sorted", "binary_search_1d" elif row_sorted and col_sorted: return "row_column_sorted", "staircase_search" elif row_sorted: return "row_sorted_only", "binary_search_per_row" elif col_sorted: return "column_sorted_only", "binary_search_per_column" else: return "unsorted", "linear_scan" def smart_search(matrix, target): """ Automatically select and apply the best search algorithm. """ matrix_type, algorithm = detect_matrix_type(matrix) if algorithm == "binary_search_1d": return binary_search_1d(matrix, target) elif algorithm == "staircase_search": return staircase_search(matrix, target) elif algorithm == "binary_search_per_row": return binary_search_rows(matrix, target) else: return linear_search(matrix, target) def binary_search_1d(matrix, target): """Binary search for fully sorted matrix.""" m, n = len(matrix), len(matrix[0]) left, right = 0, m * n - 1 while left <= right: mid = left + (right - left) // 2 val = matrix[mid // n][mid % n] if val == target: return (mid // n, mid % n) elif val < target: left = mid + 1 else: right = mid - 1 return (-1, -1) def staircase_search(matrix, target): """Staircase search for row-and-column sorted matrix.""" m, n = len(matrix), len(matrix[0]) row, col = 0, n - 1 while row < m and col >= 0: if matrix[row][col] == target: return (row, col) elif matrix[row][col] > target: col -= 1 else: row += 1 return (-1, -1) def binary_search_rows(matrix, target): """Binary search each row for row-sorted-only matrix.""" for i, row in enumerate(matrix): left, right = 0, len(row) - 1 while left <= right: mid = (left + right) // 2 if row[mid] == target: return (i, mid) elif row[mid] < target: left = mid + 1 else: right = mid - 1 return (-1, -1) def linear_search(matrix, target): """Linear scan for unsorted matrix.""" for i, row in enumerate(matrix): for j, val in enumerate(row): if val == target: return (i, j) return (-1, -1) # Demonstratematrices = [ ([[1, 3], [5, 7]], "fully_sorted"), ([[1, 4], [2, 5]], "row_column_sorted"), ([[5, 6], [1, 2]], "row_sorted_only"),] for mat, expected in matrices: detected, algorithm = detect_matrix_type(mat) print(f"Matrix: {mat}") print(f" Detected: {detected}, Algorithm: {algorithm}") print()In interviews, always clarify: 'Is the matrix fully sorted (each row ends before the next row starts), or is it sorted by rows AND columns independently?' This question shows sophistication and determines which algorithm to apply.
Let's examine the two classic LeetCode problems that distinguish these matrix types:
LeetCode 74: Search a 2D Matrix
Problem statement specifies:
This is a fully sorted matrix! Use O(log(m×n)) binary search.
LeetCode 240: Search a 2D Matrix II
Problem statement specifies:
This is a row-and-column-sorted matrix (NOT fully sorted). Use O(m+n) staircase search.
1234567891011121314151617181920212223242526
# LeetCode 74: Search a 2D Matrix# FULLY SORTED - Use Binary Search def searchMatrix(matrix, target): """ Time: O(log(m*n)) Space: O(1) """ if not matrix or not matrix[0]: return False m, n = len(matrix), len(matrix[0]) left, right = 0, m * n - 1 while left <= right: mid = left + (right - left) // 2 val = matrix[mid // n][mid % n] if val == target: return True elif val < target: left = mid + 1 else: right = mid - 1 return False12345678910111213141516171819202122232425
# LeetCode 240: Search a 2D Matrix II# ROW-AND-COLUMN SORTED - Staircase def searchMatrix(matrix, target): """ Time: O(m + n) Space: O(1) """ if not matrix or not matrix[0]: return False m, n = len(matrix), len(matrix[0]) row, col = 0, n - 1 while row < m and col >= 0: val = matrix[row][col] if val == target: return True elif val > target: col -= 1 else: row += 1 return FalseUsing staircase search for LeetCode 74 works correctly but is suboptimal (O(m+n) instead of O(log(m×n))). Using binary search for LeetCode 240 is WRONG—it may produce incorrect results because the matrix isn't fully sorted. Know the difference!
An alternative approach for fully sorted matrices uses two separate binary searches:
Stage 1: Binary search on the first column to find which row contains the target.
Stage 2: Binary search within that specific row to find the target.
This approach has the same O(log m + log n) = O(log(m×n)) complexity but may be easier to understand for some as it separates the vertical and horizontal search phases.
Caveat: This only works for fully sorted matrices where row boundaries are respected. It does NOT work for row-and-column-sorted matrices.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120
def search_two_stage(matrix, target): """ Two-stage binary search for fully sorted matrix. Stage 1: Binary search first column to find the row Stage 2: Binary search within the identified row Time: O(log m + log n) = O(log(m*n)) Space: O(1) """ if not matrix or not matrix[0]: return False m, n = len(matrix), len(matrix[0]) # Quick rejection if target < matrix[0][0] or target > matrix[m-1][n-1]: return False # STAGE 1: Find the row # We want the last row where first element ≤ target row_left, row_right = 0, m - 1 target_row = 0 while row_left <= row_right: mid = row_left + (row_right - row_left) // 2 if matrix[mid][0] <= target: target_row = mid # This row could contain target row_left = mid + 1 # Check if a later row also qualifies else: row_right = mid - 1 # First element too large, go earlier # target_row now contains the row where target might be # (it's the last row whose first element ≤ target) # Verify target is within this row's range if target > matrix[target_row][n-1]: return False # Target is between rows (gap) # STAGE 2: Binary search within the row col_left, col_right = 0, n - 1 while col_left <= col_right: mid = col_left + (col_right - col_left) // 2 if matrix[target_row][mid] == target: return True # Found! elif matrix[target_row][mid] < target: col_left = mid + 1 else: col_right = mid - 1 return False # Not in this row # Testmatrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]] for target in [3, 16, 50, 13, 0, 100]: result = search_two_stage(matrix, target) print(f"Target {target}: {'Found' if result else 'Not found'}") # Trace exampledef search_two_stage_trace(matrix, target): """With detailed tracing.""" if not matrix or not matrix[0]: return False m, n = len(matrix), len(matrix[0]) print(f"\nSearching for {target} in {m}×{n} matrix") # Stage 1 print("\nSTAGE 1: Binary search on first column to find row") row_left, row_right = 0, m - 1 target_row = 0 while row_left <= row_right: mid = row_left + (row_right - row_left) // 2 print(f" [{row_left}, {row_right}] mid={mid}, matrix[{mid}][0]={matrix[mid][0]}", end="") if matrix[mid][0] <= target: target_row = mid print(f" ≤ {target}, target_row={target_row}, search later") row_left = mid + 1 else: print(f" > {target}, search earlier") row_right = mid - 1 print(f" → Target row: {target_row}") # Stage 2 print(f"\nSTAGE 2: Binary search within row {target_row}: {matrix[target_row]}") col_left, col_right = 0, n - 1 while col_left <= col_right: mid = col_left + (col_right - col_left) // 2 val = matrix[target_row][mid] print(f" [{col_left}, {col_right}] mid={mid}, value={val}", end="") if val == target: print(f" == {target}, FOUND!") return True elif val < target: print(f" < {target}, search right") col_left = mid + 1 else: print(f" > {target}, search left") col_right = mid - 1 print(" → NOT FOUND") return False search_two_stage_trace(matrix, 16)Both the single binary search and two-stage approach achieve O(log(m×n)) complexity. The single approach is more elegant; the two-stage approach may be easier to reason about. Choose based on personal preference—interviewers accept either.
We've explored the most efficient search approach for fully sorted matrices—treating them as virtual 1D arrays.
What's Next:
Now that we've covered both staircase search and 1D binary search approaches, the final page brings everything together with a comprehensive time complexity analysis comparing all 2D matrix search methods. We'll derive complexity formulas, compare them mathematically, and provide clear guidelines for choosing the optimal approach for any given matrix structure.
You've mastered the 1D binary search approach for fully sorted matrices. You understand the critical distinction between fully sorted and row-and-column sorted structures, can implement the index transformation, and know when each approach applies. This knowledge is essential for matrix search problems in interviews and real-world applications.