Search a 2D Matrix

This question hands you a grid instead of a flat list. It looks new. But the interviewer is checking one thing. Can you see that a sorted grid is really just a sorted list folded into rows? Once you see that, binary search works just like before.

🎯 The Problem

You search a sorted grid for a target number. The rules:

• A grid is a table of rows and columns, also called a matrix.
• Each row goes left to right from small to big.
• The first number of every row is bigger than the last number of the row above it.
• You get one target number.
• Return true if the target is in the grid, and false if it is not.

Let us say the grid is [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]] and the target is 16. The number 16 sits in the second row. So the answer is true.

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

Explanation: 16 is in the second row of the grid

Because of those two rules, if you read the grid row by row, the numbers come out in perfect sorted order. That is the secret.

Here is the grid. Read it left to right, top to bottom, and the values only go up.

🐢 Approach 1: Check Every Cell (Brute Force)

Visit each cell and compare it with the target.

The idea:

• Walk through each row.
• Inside each row, walk through each number.
• Return true on a match. Return false if the whole grid has none.

How it works:

• This is a linear scan over the grid.
• A linear scan visits every cell one after another.
• It works on any grid, even an unsorted one.

Why it is weak:

• Our grid is sorted, but this idea ignores that.
• With m rows and n columns, you might check all m times n cells.
• Time is O(m times n). Slow on a big grid.

Here is the brute-force code for that idea:

def search_matrix(matrix, target):
    for row in matrix:
        for value in row:
            if value == target:
                return True
    return False

⚡ Approach 2: Treat the Grid as One Sorted List (Best)

Read the grid as one long sorted list and binary search it.

The idea:

• The rows join up in order, so the whole grid behaves like one long sorted list.
• Run a single binary search across all the cells, as if laid out in a straight line.

How it works:

• There are m times n cells. Give each a flat number from 0 to m times n minus 1.
• Keep lo at 0 and hi at the last cell number. Pick the middle mid.
• Turn mid into a real cell: the row is mid divided by n with whole-number division, the column is the remainder mid mod n.
• Read the value at that row and column.
• If it equals the target, return true.
• If it is smaller, move lo to mid + 1. If bigger, move hi to mid - 1.
• Stop when the window is empty and return false.

Why it is fast:

• Each step halves the cells.
• Time is O(log of m times n).
• Only a few variables, so space is O(1).

Here is a dry run searching for 16 in a grid with 3 rows and 4 columns, so 12 cells. Watch the flat lo, mid and hi narrow.

Steps to Solve

1. Read the number of rows m and columns n.
2. Set lo to 0 and hi to m times n minus 1.
3. While lo is less than or equal to hi, keep searching.
4. Find the middle cell number mid as lo + (hi - lo) / 2.
5. Turn mid into a row with mid / n and a column with mid % n, then read the value.
6. If the value equals the target, return true.
7. If the value is smaller, move lo to mid + 1. If bigger, move hi to mid - 1.
8. If the loop ends with no match, return false.

#include <stdio.h>
#include <stdbool.h>

#define ROWS 3
#define COLS 4

bool searchMatrix(int matrix[ROWS][COLS], int m, int n, int target) {
    int lo = 0, hi = m * n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;     // flat middle cell
        int value = matrix[mid / n][mid % n]; // row, column
        if (value == target) {
            return true;                  // found it
        } else if (value < target) {
            lo = mid + 1;                 // go right
        } else {
            hi = mid - 1;                 // go left
        }
    }
    return false;                          // not found
}

int main(void) {
    int matrix[ROWS][COLS] = {
        {1, 3, 5, 7},
        {10, 11, 16, 20},
        {23, 30, 34, 60}
    };
    int target = 16;
    printf("%s\n", searchMatrix(matrix, ROWS, COLS, target) ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <vector>
using namespace std;

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = (int)matrix.size();
    int n = (int)matrix[0].size();
    int lo = 0, hi = m * n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;        // flat middle cell
        int value = matrix[mid / n][mid % n]; // row, column
        if (value == target) {
            return true;                     // found it
        } else if (value < target) {
            lo = mid + 1;                    // go right
        } else {
            hi = mid - 1;                    // go left
        }
    }
    return false;                             // not found
}

int main() {
    vector<vector<int>> matrix = {
        {1, 3, 5, 7},
        {10, 11, 16, 20},
        {23, 30, 34, 60}
    };
    int target = 16;
    cout << (searchMatrix(matrix, target) ? "true" : "false") << endl;
    return 0;
}

true

public class SearchMatrix {
    public static boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int lo = 0, hi = m * n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;        // flat middle cell
            int value = matrix[mid / n][mid % n]; // row, column
            if (value == target) {
                return true;                     // found it
            } else if (value < target) {
                lo = mid + 1;                    // go right
            } else {
                hi = mid - 1;                    // go left
            }
        }
        return false;                             // not found
    }

    public static void main(String[] args) {
        int[][] matrix = {
            { 1, 3, 5, 7 },
            { 10, 11, 16, 20 },
            { 23, 30, 34, 60 }
        };
        int target = 16;
        System.out.println(searchMatrix(matrix, target));
    }
}

true

def search_matrix(matrix, target):
    m = len(matrix)
    n = len(matrix[0])
    lo, hi = 0, m * n - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2          # flat middle cell
        value = matrix[mid // n][mid % n]  # row, column
        if value == target:
            return True                    # found it
        elif value < target:
            lo = mid + 1                   # go right
        else:
            hi = mid - 1                   # go left
    return False                            # not found


matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
target = 16
print(search_matrix(matrix, target))

True

function searchMatrix(matrix, target) {
  const m = matrix.length;
  const n = matrix[0].length;
  let lo = 0;
  let hi = m * n - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);  // flat middle cell
    const value = matrix[Math.floor(mid / n)][mid % n]; // row, column
    if (value === target) {
      return true;     // found it
    } else if (value < target) {
      lo = mid + 1;    // go right
    } else {
      hi = mid - 1;    // go left
    }
  }
  return false;        // not found
}

const matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]];
const target = 16;
console.log(searchMatrix(matrix, target));

true

Let us walk through the Python version line by line, so the index trick makes sense.

The lines m = len(matrix) and n = len(matrix[0]) read the shape of the grid. m is the number of rows. n is the number of columns. We need n to convert a flat number back into a row and column.

The line lo, hi = 0, m * n - 1 sets the edges over the imaginary flat list. There are m times n cells. So the last cell number is m * n - 1.

The line while lo <= hi: keeps searching while the window holds at least one cell.

The line mid = lo + (hi - lo) // 2 picks the middle flat cell number. Same overflow-safe form as plain binary search.

The line value = matrix[mid // n][mid % n] is the heart of this problem. mid // n is the row, because every n cells fill one full row. mid % n is the column, because the remainder tells you how far into the row you are. With both, we read the real value at that cell.

The line if value == target: returns True the moment we land on the target.

The line elif value < target: means the middle value is too small, so the target is later in the flat list. We set lo = mid + 1.

The else branch means the middle value is too big, so we set hi = mid - 1.

If the loop ends with nothing found, return False says the target is not in the grid.

⏱️ Time and Space Complexity

The linear scan can touch every cell, so it is O(m times n). The binary search treats the grid as one sorted list and halves it each step, so it finishes in about log of m times n steps. Both use only a few variables, so the space is O(1).

🧩 Key Takeaways

• ✅ A sorted grid with joined-up rows behaves like one long sorted list.
• ✅ Give each cell a flat number from 0 to m times n minus 1.
• ✅ Turn a flat number into a row with mid / n and a column with mid % n.
• ✅ After that conversion, it is plain binary search on the cell values.
• ✅ The time is O(log of m times n), much faster than scanning every cell.

🚀 What’s Next?

• Binary Search
• Koko Eating Bananas