Find a Value in a Matrix Sorted Like a Flattened Array

Medium15–20 min

Topics

ArrayMatrixBinary Search

Companies

AmazonMicrosoftGoogle

You're given an m × n matrix where every row is sorted in ascending order, and the first number of each row is greater than the last number of the previous row — so reading it row by row produces one fully sorted sequence. Given an integer target, return whether it exists anywhere in the matrix. Solve it in O(log(m × n)) time by binary-searching the matrix as if it were a single flattened, sorted array — no need to actually flatten it.

Test Case 1:

Input:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

Output:true

Explanation:3 sits at matrix[0][1].

Test Case 2:

Input:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

Output:false

Explanation:13 falls between 11 and 16, but never appears.

Test Case 3:

Input:matrix = [[1]], target = 1

Output:true

Explanation:A single-cell matrix that matches.

Constraints

◆1 ≤ matrix.length, matrix[0].length ≤ 100
◆-10⁴ ≤ matrix[i][j], target ≤ 10⁴
◆Every row is sorted in ascending order
◆The first integer of each row is greater than the last integer of the previous row

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

matrix (rows separated by ;) — 1-4 rows, 1-5 cols, row-major sortedtarget

1	class Solution {
2	public boolean searchMatrix(int[][] matrix, int target) {
3	int m = matrix.length, n = matrix[0].length;
4	int lo = 0, hi = m * n - 1;
5	while (lo <= hi) {
6	int mid = lo + (hi - lo) / 2;
7	int val = matrix[mid / n][mid % n];
8	if (val == target) {
9	return true;
10	} else if (val < target) {
11	lo = mid + 1;
12	} else {
13	hi = mid - 1;
14	}
15	}
16	return false;
17	}
18	}
19

↓lo

↓hi

Variables

m3

n4

lo0

hi11

INITIALIZE

Treat the matrix as one sorted array of 12 elements (indices 0-11) and binary-search it directly, mapping each flattened index back to a cell.

Step 1 / 5

Approach & Solutions

Brute Force — Scan Every Cell

Brute

Check every cell, row by row. It's correct on any matrix, sorted or not, but it ignores the very specific guarantee this problem gives you — that reading the matrix row by row produces one fully sorted sequence — which is what lets binary search skip almost the whole matrix.

TimeO(m × n)

SpaceO(1)

Java

Try it out

class Solution {
    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;
    }
}

Optimal — Binary Search on the Flattened Index

Optimal

Because every row continues where the previous one left off, reading the matrix row-major (left to right, top to bottom) produces one sorted array of m × n elements — you just never materialize it. Binary search that virtual array directly: a flattened index mid maps back to matrix[mid / n][mid % n].

TimeO(log(m × n))