Definition
- Globally sorted matrix – rows are sorted left to right and the first element of each row exceeds the last element of the previous row.
- Flattened view – the matrix is conceptually one sorted array of length m * n, folded into rows.
- Index mapping – convert a 1D index to 2D:
row = mid / colsandcol = mid % cols. - Single binary search – search the range [0, m*n - 1] in O(log(m*n)) time.
- Top-right elimination – an alternative for row-sorted-only matrices, walking from the top-right corner in O(m + n) time.
Imagine the National Bank of India prints a giant ledger where every page has transaction amounts sorted smallest to largest, and the last amount on page one is always smaller than the first amount on page two. Rajesh wants to know if an amount of exactly fifty thousand rupees appears anywhere. Instead of reading every page, he treats all pages as one long sorted list, jumps to the middle, and decides whether to look in the earlier half or the later half.
Understanding the Concepts
What is the problem?
Given an m x n matrix where each row is sorted left to right and the first element of each row is greater than the last element of the previous row, determine if a target value exists in the matrix. The solution should run in O(log(m*n)) time.
package com.bank.search;
public class SearchMatrix {
public static boolean searchMatrix(int[][] matrix, int target) {
int rows = matrix.length;
if (rows == 0) return false;
int cols = matrix[0].length;
int low = 0, high = rows * cols - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int row = mid / cols;
int col = mid % cols;
int value = matrix[row][col];
if (value == target) return true;
if (value < target) low = mid + 1;
else high = mid - 1;
}
return false;
}
public static void main(String[] args) {
int[][] ledger = {
{10000, 20000, 30000, 40000},
{50000, 60000, 70000, 80000},
{90000, 100000, 110000, 120000}
};
System.out.println("Find 70000: " + searchMatrix(ledger, 70000));
System.out.println("Find 55000: " + searchMatrix(ledger, 55000));
}
}
Find 70000: true
Find 55000: false
How does the index mapping work?
The matrix has m rows and n columns. A flattened index mid maps to row mid / n and column mid % n. For example, in a 3x4 matrix, flattened index 6 maps to row 6 / 4 = 1 and column 6 % 4 = 2, which is matrix[1][2].
package com.bank.search;
public class IndexMapping {
public static void main(String[] args) {
int rows = 3, cols = 4;
System.out.println("Flattened index -> (row, col):");
for (int i = 0; i < rows * cols; i++) {
System.out.println(" " + i + " -> (" + i / cols + ", " + i % cols + ")");
}
}
}
Flattened index -> (row, col):
0 -> (0, 0)
1 -> (0, 1)
2 -> (0, 2)
3 -> (0, 3)
4 -> (1, 0)
5 -> (1, 1)
6 -> (1, 2)
7 -> (1, 3)
8 -> (2, 0)
9 -> (2, 1)
10 -> (2, 2)
11 -> (2, 3)
Why must the matrix be globally sorted?
The flattened binary search assumes reading row by row gives a non-decreasing sequence. If only each row is sorted but rows do not chain together (the first element of a row is not necessarily greater than the last of the previous row), the flattened approach gives wrong results. For such matrices, use top-right elimination instead.
package com.bank.search;
public class GlobalVsRowSorted {
public static void main(String[] args) {
// Globally sorted: flattened binary search works
int[][] global = {
{10, 20, 30},
{40, 50, 60},
{70, 80, 90}
};
System.out.println("Global sorted, find 50: " + searchFlattened(global, 50));
// Row-sorted only: flattened search may fail
int[][] rowOnly = {
{10, 20, 30},
{15, 25, 35}, // 15 < 30: rows don't chain
{28, 40, 50}
};
System.out.println("Row-sorted, find 25: " + searchTopRight(rowOnly, 25));
}
static boolean searchFlattened(int[][] m, int t) {
int r = m.length, c = m[0].length;
int lo = 0, hi = r * c - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int v = m[mid / c][mid % c];
if (v == t) return true;
if (v < t) lo = mid + 1; else hi = mid - 1;
}
return false;
}
static boolean searchTopRight(int[][] m, int t) {
int row = 0, col = m[0].length - 1;
while (row < m.length && col >= 0) {
if (m[row][col] == t) return true;
if (m[row][col] < t) row++; else col--;
}
return false;
}
}
Global sorted, find 50: true
Row-sorted, find 25: true
What is the top-right corner elimination approach?
For matrices where each row and each column is sorted but rows do not chain together, start at the top-right corner. If the current value equals the target, return true. If it is less than the target, move down (the current row's values are all too small). If it is greater, move left (the current column's values are all too large). This eliminates one row or one column per step, giving O(m + n) time.
package com.bank.search;
public class TopRightElimination {
public static boolean search(int[][] matrix, int target) {
if (matrix.length == 0) return false;
int row = 0, col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
int val = matrix[row][col];
if (val == target) return true;
if (val < target) row++; // eliminate row
else col--; // eliminate column
}
return false;
}
public static void main(String[] args) {
int[][] ledger = {
{1000, 4000, 7000, 11000},
{2000, 5000, 8000, 12000},
{3000, 6000, 9000, 16000},
{10000, 13000, 14000, 17000}
};
System.out.println("Find 5000: " + search(ledger, 5000));
System.out.println("Find 15000: " + search(ledger, 15000));
}
}
Find 5000: true
Find 15000: false
How do the two approaches compare?
| Feature | Flattened Binary Search | Top-Right Elimination |
|---|---|---|
| Matrix type | Globally sorted | Row-sorted + column-sorted |
| Time | O(log(m * n)) | O(m + n) |
| Space | O(1) | O(1) |
| Approach | Single binary search | Walk from corner |
| Better when | Matrix is globally sorted | Matrix is only row and column sorted |
What about the overflow-safe midpoint?
On a very large grid, m * n can be large. The midpoint must be computed as low + (high - low) / 2 to avoid overflow. For a banking audit grid with millions of entries, this is not a theoretical concern.
package com.bank.search;
public class OverflowSafe {
public static void main(String[] args) {
int rows = 50000, cols = 50000;
long total = (long) rows * cols; // 2.5 billion: overflows int
System.out.println("Total cells: " + total);
System.out.println("Fits in int? " + (total <= Integer.MAX_VALUE));
System.out.println("Use long for high index on very large grids.");
}
}
Total cells: 2500000000
Fits in int? false
Use long for high index on very large grids.
What are common mistakes?
- The two most common mistakes:
- Using the flattened approach on a matrix that is only row-sorted, not globally sorted.
- Confusing the number of columns with the number of rows when computing
row = mid / colsandcol = mid % cols.
package com.bank.search;
public class MappingBug {
public static void main(String[] args) {
int rows = 3, cols = 4;
int mid = 7;
// CORRECT
System.out.println("Correct: (" + mid / cols + ", " + mid % cols + ")");
// WRONG: swapped rows and cols
System.out.println("Wrong: (" + mid / rows + ", " + mid % rows + ")");
}
}
Correct: (1, 3)
Wrong: (2, 1)
How is this used in a banking scenario?
At the National Bank of India, the end-of-day settlement report is stored as a globally sorted grid of settled amounts. The compliance officer needs an instant check for whether a specific amount has settled. The flattened binary search gives that answer in a handful of comparisons even on grids with millions of entries.
package com.bank.search;
public class SettlementGrid {
public static void main(String[] args) {
// Simulate a 1000x1000 globally sorted grid
int rows = 1000, cols = 1000;
int[][] grid = new int[rows][cols];
int val = 1;
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
grid[r][c] = val++;
int target = 500_000;
long start = System.nanoTime();
boolean found = searchMatrix(grid, target);
long elapsed = System.nanoTime() - start;
System.out.println("Found " + target + ": " + found);
System.out.println("Time: " + elapsed + " ns");
}
static boolean searchMatrix(int[][] m, int t) {
int r = m.length, c = m[0].length;
int lo = 0, hi = r * c - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int v = m[mid / c][mid % c];
if (v == t) return true;
if (v < t) lo = mid + 1; else hi = mid - 1;
}
return false;
}
}
Found 500000: true
Time: 1500 ns
Visual Overview
Globally Sorted Matrix (3x4): ┌───────┬───────┬───────┬───────┐ │ 10000 │ 20000 │ 30000 │ 40000 │ row 0 ├───────┼───────┼───────┼───────┤ │ 50000 │ 60000 │ 70000 │ 80000 │ row 1 ├───────┼───────┼───────┼───────┤ │ 90000 │100000 │110000 │120000 │ row 2 └───────┴───────┴───────┴───────┘ Flattened: [10K, 20K, 30K, 40K, 50K, 60K, 70K, 80K, 90K, 100K, 110K, 120K] Index: 0 1 2 3 4 5 6 7 8 9 10 11 Search for 70000: Step 1: mid=5 -> row=5/4=1, col=5%4=1 -> 60000 < 70000 -> low=6 Step 2: mid=8 -> row=8/4=2, col=8%4=0 -> 90000 > 70000 -> high=7 Step 3: mid=6 -> row=6/4=1, col=6%4=2 -> 70000 == 70000 -> FOUND
Key Takeaway
Searching a sorted 2D matrix exploits the fact that a globally sorted matrix is just a sorted array folded into rows. Because reading row by row gives one long non-decreasing sequence, a single binary search over the conceptual flattened array of length m * n finds any value in O(log(m*n)) time.
The technique that makes this work is the index mapping: a 1D midpoint converts to row = mid / cols and col = mid % cols. The rest is standard binary search with the overflow-safe midpoint form.
For matrices where each row and column is sorted but rows do not chain together, the flattened approach does not work. Instead, start from the top-right corner and eliminate one row or column per step, giving O(m + n) time.
In a banking system at the National Bank of India, the end-of-day settlement report stored as a globally sorted grid benefits from the flattened binary search, answering compliance queries in a handful of comparisons even on grids with millions of entries.
Remember one sentence: a globally sorted matrix is a folded sorted array, so map 1D indices to 2D with division and modulo and run one binary search.
---