Skip to content

Volume ITechnology

4.11.2 — Search a 2D Matrix ​

LeetCode 74 · Medium

The problem ​

You are given a grid of numbers, matrix, with m rows and n columns, and a number target. The grid has two properties.

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

Return true if target is in the grid. Your solution must run in O(\log(m \cdot n)) time.

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

target = 3   →  true
target = 13  →  false

The grid has between 1 and 100 rows, and between 1 and 100 columns.

What the problem is really asking ​

Read the second property again. Every row starts after the previous row ended. So if you read the grid like a book, left to right along row 0, then row 1, then row 2, the numbers come out in fully sorted order: 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60.

The grid is just a sorted list that has been chopped into rows. So the real question is: how do you binary search a sorted list when it is stored as rows?

The brute force, and where it wastes work ​

Check every cell.

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

That is O(m \cdot n), up to 10,000 checks for a 100 × 100 grid.

The waste in one sentence: it ignores that the grid is sorted, so one comparison could rule out half of the remaining cells.

The idea ​

Pretend the grid is one long list with positions 0 to m \cdot n - 1. Run the binary search from 4.11.1 over those pretend positions. Whenever you need the number at a pretend position, turn it back into a row and a column:

\text{row} = \left\lfloor \frac{\text{index}}{\text{cols}} \right\rfloor \qquad \text{col} = \text{index} \bmod \text{cols}

Read these as "row is the index divided by the number of columns, rounded down" and "column is the remainder left over from that division". The symbol \bmod means "the remainder after dividing".

Why does this work? Each row holds exactly cols numbers. So to reach pretend position 6 in a grid with 4 columns, you skip one full row of 4 (that is 6 \div 4 = 1, rounded down), and then go 2 more along the next row (that is the remainder, 6 \bmod 4 = 2). Position 6 is row 1, column 2.

This is the same arithmetic a computer uses to store a grid in memory as one flat list. See 4.2. It is also the reverse of the box-number formula in 4.4.8 Valid Sudoku.

Think of 12 people standing in one line, holding tickets numbered in order. Ask them to form 3 rows of 4. The person at position 6 in the line ends up in the second row, third place, because the first 4 people filled the first row.

The solution ​

python
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows, cols = len(matrix), len(matrix[0])        # (1)
        low, high = 0, rows * cols - 1                  # (2)

        while low <= high:                              # (3)
            mid = low + (high - low) // 2
            value = matrix[mid // cols][mid % cols]     # (4)

            if value == target:                         # (5)
                return True
            if value < target:
                low = mid + 1
            else:
                high = mid - 1

        return False                                    # (6)
ts
function searchMatrix(matrix: number[][], target: number): boolean {
  const rows = matrix.length, cols = matrix[0].length;  // (1)
  let low = 0, high = rows * cols - 1;                  // (2)

  while (low <= high) {                                 // (3)
    const mid = low + Math.floor((high - low) / 2);
    const value = matrix[Math.floor(mid / cols)][mid % cols];  // (4)

    if (value === target) return true;                  // (5)
    if (value < target) low = mid + 1;
    else high = mid - 1;
  }

  return false;                                         // (6)
}

Line by line ​

(1) The grid's size. The grid always has at least one row, so matrix[0] is safe.

(2) The pretend list runs from 0 to rows × cols − 1. A 3 × 4 grid has 12 cells, so its positions are 0 to 11.

(3) Shape A binary search from 4.11.1: both ends are real positions, so the loop runs while low <= high, and mid is computed the overflow-safe way.

(4) Turn the pretend position back into a cell. mid // cols is the row and mid % cols is the column. The divisor is the number of columns, not rows. Getting this backwards is the only real trap on this page. Check it on a corner: with 4 columns, position 5 should be row 1, column 1. 5 // 4 = 1 ✓ and 5 \bmod 4 = 1 ✓.

(5) The usual three-way comparison. Found it, or move low past mid, or move high before mid.

(6) The range is empty, so the target is not in the grid.

Trace ​

Take the 3 × 4 grid above and target = 3. low = 0, high = 11.

SteplowhighmidRow = mid // 4Col = mid % 4ValueAction
101151111too big, high = 4
2042025too big, high = 1
3010001too small, low = 1
4111013found, return true

Now target = 13.

SteplowhighmidRow, colValueAction
101151, 111too small, low = 6
261182, 023too big, high = 7
36761, 216too big, high = 5
end65empty, return false

Complexity, derived ​

Time. The pretend list has m \cdot n positions. Binary search halves it each step, so it takes about \log_2(m \cdot n) steps. Each step does one division, one remainder and one comparison, all constant work. So the time is O(\log(m \cdot n)). We never actually build the long list.

There is a neat fact here: \log(m \cdot n) = \log m + \log n. So this costs exactly the same as two binary searches, one to find the row and one to search inside it. The single search is not faster. It is just less code.

Space. A few numbers. So O(1).

Edge cases ​

  • A 1 × 1 grid. One position. The loop checks it once.
  • One row, or one column. The formula still works: with one column, mid // 1 is mid and mid % 1 is 0.
  • The target is smaller than the first number, or bigger than the last. The range empties and the answer is false.

The two-step version ​

You can also search in two steps: first find the row whose range could hold the target, then binary search inside that row.

python
top, bottom = 0, rows - 1
while top <= bottom:                      # find the right row
    r = (top + bottom) // 2
    if target > matrix[r][-1]:
        top = r + 1                       # target is below this row
    elif target < matrix[r][0]:
        bottom = r - 1                    # target is above this row
    else:
        break                             # target, if present, is in row r
else:
    return False                          # no row can hold it
# then a normal binary search on matrix[r]

The else attached to a while loop is a Python feature: it runs only if the loop ended without a break. Here that means no row could hold the target.

This is the same speed and more code. It has one real advantage outside interviews. If the rows are stored in different places in memory, this version settles on one row and stays there, which is kinder to the computer's memory cache.

The other version of this problem ​

Search a 2D Matrix II (LeetCode 240) looks almost the same, but it is a different problem. There, each row is sorted and each column is sorted, but a row does not have to start after the previous row ends. So reading row by row does not give a sorted list, and this page's trick is wrong.

The answer there is a staircase walk. Start at the top-right corner.

  • If the value is too big, move left. Everything below it in that column is even bigger, so that whole column is ruled out.
  • If the value is too small, move down. Everything to its left in that row is even smaller, so that whole row is ruled out.

Each step rules out a whole row or a whole column, so it takes at most m + n steps, which is O(m + n).

Being able to tell these two problems apart, and to name the one rule that separates them, is worth more than either solution.

What the interviewer will push on ​

"Why can you treat the grid as one list?" Because each row starts after the previous one ended, so reading row by row gives sorted order.

"Which number do you divide by?" The number of columns.

"Is O(\log(m \cdot n)) faster than two binary searches?" No. They are equal, because \log(m \cdot n) = \log m + \log n. Saying this shows you read the maths instead of assuming.

"What if the rows were sorted but did not chain together?" That is Matrix II: the staircase walk from the top-right corner, O(m + n).

One thing to volunteer: check the index formula on one corner, out loud, before running. It takes three seconds and it is the only thing here that can go wrong.

Next: 4.11.3 Koko Eating Bananas. The first problem with no sorted list at all, where you binary search the answer instead.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet