What is the brute force approach and complexity for Search a 2D Matrix?

Scan all m · n cells and compare each one with target with time complexity O(m · n) and space complexity O(1).

What is the optimal approach and complexity for Search a 2D Matrix?

Treat the grid as one sorted array of m · n cells; map idx → (idx / n, idx % n) with optimal time complexity O(log(m · n)) and space complexity O(1).

How do you identify the pattern for Search a 2D Matrix?

Look for key signals in the prompt: "each row sorted" indicates Sorted data → binary search is possible.; "first of each row > last of previous row" indicates The rows continue each other → the whole grid is ONE sorted array.; "O(log(m · n))" indicates One binary search over all m · n cells..

Search a 2D Matrix

Medium·LeetCode #74Basic Anchor

LeetCode

Jump:

30-Second Mental ModelBinary Search (2D grid as a flat sorted array)

Complexity:O(m · n)→O(log(m · n))

Key Insight

Read row by row, the grid is one sorted array of length m · n. We do not need to build that array. Give each cell a number idx from 0 to m·n − 1 in reading order. Since every row has n cells, cell idx is at row idx / n, column idx % n. Now run the ordinary binary search on idx.

Core Validity Invariant

Read row by row, the grid is one sorted array of m · n numbers, and flat position idx is the cell matrix[idx / n][idx % n].

Problem

You are given a grid matrix with m rows and n columns. It has two promises:

Every row is sorted from left to right.
The first number of each row is bigger than the last number of the row above it.

Given a number target, return true if it appears anywhere in the grid, and false otherwise. Your solution must run in O(log(m · n)) time.

Input

A 2D integer array matrix (m rows, n columns) with the two promises above, and an integer target.

Output

true if target is in the matrix, otherwise false.

Example 1

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

Output: true

3 is in the first row, at column 1.

Example 2

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

Output: false

13 would have to sit between 11 and 16 in the middle row, but it is not there.

Constraints

• 1 ≤ m, n ≤ 100 (m rows, n columns)
• −10^4 ≤ matrix[i][j], target ≤ 10^4
• Each row is sorted in non-decreasing order.
• The first number of each row is greater than the last number of the previous row.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I read the grid row by row, left to right, what does the sequence of numbers look like?
2.
What does the second promise (each row starts bigger than the previous row ends) add on top of "each row is sorted"?
3.
Can I tell which row the target must be in just by looking at the first number of each row?
4.
If I number the cells 0, 1, 2, … in reading order, how do I get back the row and column of cell number k?
5.
Is O(log m + log n) really different from O(log(m · n))?

Brute force approach

Idea

Loop over every row and every column. If any cell equals target, return true. If the loops finish, return false.

Thinking process

1
The simplest way to know if a number is in a grid is to look at every cell.
2
Two nested loops: rows outside, columns inside.
3
This never uses the fact that the grid is sorted, so it is clearly wasting information.

Code & Implementation

brute.cpp

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // Look at every cell, row by row. Ignores the sorting completely.
        for (auto& row : matrix) {
            for (int x : row) {
                if (x == target) return true;
            }
        }
        return false;
    }
};

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // Look at every cell, row by row. Ignores the sorting completely.
        for (int[] row : matrix) {
            for (int x : row) {
                if (x == target) return true;
            }
        }
        return false;
    }
}

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        # Look at every cell, row by row. Ignores the sorting completely.
        for row in matrix:
            for x in row:
                if x == target:
                    return True
        return False

export function searchMatrix(matrix: number[][], target: number): boolean {
    // Look at every cell, row by row. Ignores the sorting completely.
    for (const row of matrix) {
        for (const x of row) {
            if (x === target) return true;
        }
    }
    return false;
}

Complexity

Time O(m · n)Space O(1)

At most 100 · 100 = 10,000 cells, so it passes on LeetCode, but the problem asks for O(log(m · n)). That is about 14 checks instead of 10,000.

Better approach

Why brute force is slow

Brute force checks every cell even though the grid is sorted in reading order.

What repeated work are we doing?

One comparison with a row's first number already tells us whether the whole row (and every row above or below it) can be skipped. Brute force throws that information away and checks those cells one by one.

What information can we reuse?

Use the sorted first column to jump straight to the only possible row, then use that row's sorting to jump to the only possible column.

New approach

Idea

Only one row can contain target: the last row whose first number is ≤ target. (The next row starts with something bigger than target.) Find that row with one binary search over the first column, then do a normal binary search inside that row.

Thinking process

1
Rows are in order too: every number in row 1 is bigger than every number in row 0.
2
So I can decide which row target belongs to by comparing it with the rows' first numbers.
3
The first column is sorted, so I can binary search it: find the last row with first number ≤ target.
4
If no row qualifies, target is smaller than everything — return false.
5
Inside the chosen row, the numbers are sorted, so a second binary search finishes the job.

Code & Implementation

better.cpp

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();

        // Search 1: find the last row whose FIRST element is <= target.
        // Only that row can contain target (the next row starts bigger).
        int lo = 0, hi = m - 1, row = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (matrix[mid][0] <= target) {
                row = mid;        // candidate; maybe a later row also fits
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        if (row == -1) return false;   // target is smaller than everything

        // Search 2: classic binary search inside that one row.
        lo = 0, hi = n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (matrix[row][mid] == target) return true;
            if (matrix[row][mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return false;
    }
};

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;

        // Search 1: find the last row whose FIRST element is <= target.
        // Only that row can contain target (the next row starts bigger).
        int lo = 0, hi = m - 1, row = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (matrix[mid][0] <= target) {
                row = mid; // candidate; maybe a later row also fits
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        if (row == -1) return false; // target is smaller than everything

        // Search 2: classic binary search inside that one row.
        lo = 0;
        hi = n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (matrix[row][mid] == target) return true;
            if (matrix[row][mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return false;
    }
}

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])

        # Search 1: find the last row whose FIRST element is <= target.
        # Only that row can contain target (the next row starts bigger).
        lo, hi, row = 0, m - 1, -1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if matrix[mid][0] <= target:
                row = mid  # candidate; maybe a later row also fits
                lo = mid + 1
            else:
                hi = mid - 1

        if row == -1:
            return False  # target is smaller than everything

        # Search 2: classic binary search inside that one row.
        lo, hi = 0, n - 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if matrix[row][mid] == target:
                return True
            if matrix[row][mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1

        return False

export function searchMatrix(matrix: number[][], target: number): boolean {
    const m = matrix.length;
    const n = matrix[0].length;

    // Search 1: find the last row whose FIRST element is <= target.
    // Only that row can contain target (the next row starts bigger).
    let lo = 0;
    let hi = m - 1;
    let row = -1;
    while (lo <= hi) {
        const mid = Math.floor(lo + (hi - lo) / 2);
        if (matrix[mid][0] <= target) {
            row = mid; // candidate; maybe a later row also fits
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    if (row === -1) return false; // target is smaller than everything

    // Search 2: classic binary search inside that one row.
    lo = 0;
    hi = n - 1;
    while (lo <= hi) {
        const mid = Math.floor(lo + (hi - lo) / 2);
        if (matrix[row][mid] === target) return true;
        if (matrix[row][mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

Complexity

Time O(log m + log n)Space O(1)

Be honest about this: log m + log n = log(m · n). So this is already as fast as the optimal in big-O. The optimal is not faster; it is simpler — one loop instead of two, and no "which row?" special cases.

Optimized approach

Idea

Start from brute force

Brute force looks at all m · n cells one by one and never uses the sorting.

Find the repeated work

One comparison with a sorted array's middle tells us that a whole half can't hold the target. Brute force checks those cells anyway. And the grid is a sorted array — it is just folded into rows.

Define the state — what variables do I need?

lo, hi: Flat indexes. The target, if it exists, is somewhere in positions lo … hi (inclusive).
mid: The flat position we check this step, halfway between lo and hi.
row = mid / n, col = mid % n: Where flat position mid lives in the grid. n is the number of columns (the length of one row).

Define validity

Read row by row, the grid is one sorted array of m · n numbers, and flat position idx is the cell matrix[idx / n][idx % n].

Define the transitions — when does each pointer move, and why is it safe?

matrix[mid / n][mid % n] == target

return true

We found it.

matrix[mid / n][mid % n] < target

lo = mid + 1

In the flattened order, everything at or before mid is ≤ this value, which is already too small. The target can only be to the right.

matrix[mid / n][mid % n] > target

hi = mid − 1

Everything at or after mid is ≥ this value, which is already too big. The target can only be to the left.

What does the current window add to the answer?

Each comparison throws away half of the remaining cells. After about log₂(m · n) steps the range is empty, and if we never hit target it isn't there.

Code & Implementation

optimal.cpp

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();

        // Pretend the matrix is one sorted array of m * n cells.
        // Flat index idx lives at row idx / n, column idx % n (n = number of COLUMNS).
        int lo = 0, hi = m * n - 1;
        while (lo <= hi) {                 // loop style: lo <= hi, hi = mid - 1
            int mid = lo + (hi - lo) / 2;
            int value = matrix[mid / n][mid % n];
            if (value == target) return true;
            if (value < target) lo = mid + 1;   // answer is right of mid
            else hi = mid - 1;                  // answer is left of mid
        }
        return false;
    }
};

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;

        // Pretend the matrix is one sorted array of m * n cells.
        // Flat index idx lives at row idx / n, column idx % n (n = number of COLUMNS).
        int lo = 0, hi = m * n - 1;
        while (lo <= hi) { // loop style: lo <= hi, hi = mid - 1
            int mid = lo + (hi - lo) / 2;
            int value = matrix[mid / n][mid % n];
            if (value == target) return true;
            if (value < target) lo = mid + 1; // answer is right of mid
            else hi = mid - 1; // answer is left of mid
        }
        return false;
    }
}

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])

        # Pretend the matrix is one sorted array of m * n cells.
        # Flat index idx lives at row idx // n, column idx % n (n = number of COLUMNS).
        lo, hi = 0, m * n - 1
        while lo <= hi:  # loop style: lo <= hi, hi = mid - 1
            mid = lo + (hi - lo) // 2
            value = matrix[mid // n][mid % n]
            if value == target:
                return True
            if value < target:
                lo = mid + 1  # answer is right of mid
            else:
                hi = mid - 1  # answer is left of mid

        return False

export function searchMatrix(matrix: number[][], target: number): boolean {
    const m = matrix.length;
    const n = matrix[0].length;

    // Pretend the matrix is one sorted array of m * n cells.
    // Flat index idx lives at row idx / n, column idx % n (n = number of COLUMNS).
    let lo = 0;
    let hi = m * n - 1;
    while (lo <= hi) { // loop style: lo <= hi, hi = mid - 1
        const mid = Math.floor(lo + (hi - lo) / 2);
        const value = matrix[Math.floor(mid / n)][mid % n];
        if (value === target) return true;
        if (value < target) lo = mid + 1; // answer is right of mid
        else hi = mid - 1; // answer is left of mid
    }
    return false;
}

Complexity

Time O(log(m · n))Space O(1)

Same big-O as the better approach. We prefer it because it is a single, standard binary search with nothing new to get wrong except the / n and % n.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Scan all m · n cells and compare each one with target	O(m · n)	O(1)
Better	Binary search the rows by their first number, then binary search inside that row	O(log m + log n)	O(1)
Optimal	Treat the grid as one sorted array of m · n cells; map idx → (idx / n, idx % n)	O(log(m · n))	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“each row sorted”Sorted data → binary search is possible.
“first of each row > last of previous row”The rows continue each other → the whole grid is ONE sorted array.
“O(log(m · n))”One binary search over all m · n cells.

Rows sorted+rows continue each other+grid = one sorted array of m · n→Binary Search (2D grid as a flat sorted array)

This is the anchor of the 2D and partition sub-pattern: it is the classic binary search in disguise. The only new skill is turning a flat index into (row, col). The next question, Search a 2D Matrix II, looks almost the same but drops the "rows continue each other" promise — and then flattening breaks.

Don't make this mistake

Dividing by the number of rows instead of columns

✗ int value = matrix[mid / m][mid % m];

✓ int value = matrix[mid / n][mid % n]; // n = matrix[0].size()

Each row holds n cells (the number of columns), so that is what you divide by. With a square grid both work, which hides the bug. Try the 3×4 example: flat index 5 is the value 11 at (1, 1). 5 / 4 = 1, 5 % 4 = 1 ✓. Using m = 3 gives (1, 2) = 16 ✗.

Using this trick on Search a 2D Matrix II

Pattern-confusion trap. In LC 240 each row and column is sorted, but a row does not start after the previous row ends. Example: [[1,4],[2,5]] read row by row is 1, 4, 2, 5 — not sorted. Binary search on that line gives wrong answers. Flattening only works when the second promise holds.

Picking the row with < instead of <=

✗ if (matrix[mid][0] < target) row = mid, lo = mid + 1;

✓ if (matrix[mid][0] <= target) row = mid, lo = mid + 1;

In the two-search approach, if target equals the first number of a row, < skips that row and you search the row above it, which can't contain target. Using <= keeps the row that starts with target.

Mixing loop styles

✗ while (lo < hi) { ... hi = mid - 1; ... }

✓ while (lo <= hi) { ... hi = mid - 1; ... }

With hi = mid − 1 the range lo == hi still holds one unchecked cell, so the loop must be lo <= hi. With lo < hi you never check that last cell; on a 1×1 matrix you'd return false without looking.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Binary Search translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Order Book Price Level Matching

std::lower_bound lookup in sorted price ticks for limit orders.

Explore Track

C++ Internals

CPU Branch Prediction & Cache Efficiency

Branch mispredictions in binary search and branchless mid-point arithmetic.

Explore Track

Search a 2D Matrix II