Search a 2D Matrix — LeetCode 74

What does it solve?

Given an m × 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 whether a target value exists in the matrix.

Because of those two properties, if you flatten the matrix mentally, you get a single sorted array of m·n elements — perfect for binary search.

The algorithm

// Treat m×n matrix as flat sorted array
left = 0, right = m·n − 1
while left ≤ right:
  mid = (left + right) / 2
  row = mid / n
  col = mid % n
  if matrix[row][col] == target: ✓
  elif matrix[row][col] < target: left = mid+1
  else: right = mid−1
return false

💡 Key insight: The two matrix properties together guarantee that element at flat index k maps to matrix[k/cols][k%cols]. This turns a 2D problem into a textbook binary search. Each step eliminates half the remaining cells, giving O(log m·n) — far better than O(m·n) linear scan or O(m log n) row-by-row search.

Complexity

Time

O(log m·n)

Binary search over the flattened m·n element array — one comparison per step.

Space

O(1)

Only three pointers: left, right, mid. No extra matrix or array needed.

vs. Linear scan

8× faster

On a 100×100 matrix: log(10000) ≈ 13 steps vs. up to 10 000 comparisons.

Examples & edge cases

Live animation — Binary Search on Flattened Matrix

Left pointer Right pointer Mid cell (checking) Found! Eliminated

⏸ Waiting to start

Left (flat)

—

Right (flat)

—

Mid → (row, col)

—

Value at mid

—

Step — of —

Total steps

comparisons

Search space

—

cells remaining

Target

—

looking for

Result

—

at (—,—)

Select an example and press Play to begin.

✓ Found! ✗ Not Found

Speed Medium

Step-by-step table

Step	Left	Right	Mid	(Row, Col)	Value	Action

C++ implementation

search_2d_matrix.cpp · LeetCode 74

#include <bits/stdc++.h>
using namespace std;

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

        int left = 0, right = m * n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // Convert flat index → (row, col)
            int row = mid / n;
            int col = mid % n;
            int val = matrix[row][col];

            if (val == target) {
                return true;       // ✓ Found!
            } else if (val < target) {
                left = mid + 1;    // target in right half
            } else {
                right = mid - 1;   // target in left half
            }
        }

        return false;  // target not in matrix
    }
};

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars