74. Search a 2D Matrix (Medium)

Problem

You are given an m × n integer matrix with two properties:

1. Each row is sorted in ascending order.
2. The first integer of each row is greater than the last integer of the previous row.

Return true if target is in the matrix.

Example

• matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 → true
• Same matrix, target = 13 → false

LeetCode 74 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, linear scan

Scan every cell.

Python

def search_matrix(matrix: list[list[int]], target: int) -> bool:
    for row in matrix:          # L1: iterate over m rows
        if target in row:       # L2: O(n) linear scan per row
            return True
    return False

TypeScript

function searchMatrix(matrix: number[][], target: number): boolean {
    for (const row of matrix) {          // L1: iterate over m rows
        if (row.includes(target)) return true;  // L2: O(n) linear scan per row
    }
    return false;
}

Go

func searchMatrix(matrix [][]int, target int) bool {
    for _, row := range matrix {      // L1: iterate over m rows
        for _, x := range row {       // L2: O(n) linear scan per row
            if x == target {
                return true
            }
        }
    }
    return false
}

Swift

final class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        matrix.contains { row in row.contains(target) }
    }
}

Where the time goes, line by line

Variables: m = number of rows, n = number of columns.

Line	Per-call cost	Times executed	Contribution
L1 (row loop)	$O(1)$	m	$O(m)$
L2 (scan row)	$O(n)$	m	$O(m · n)$ ← dominates

Complexity

• Time: $O(m · n)$, driven by L2 (scanning every cell in the worst case).
• Space: $O(1)$.

Approach 2: Binary search per row

Use row ordering: binary-search each row in turn. A small improvement: skip rows whose range can’t contain the target.

Python

from bisect import bisect_left

def search_matrix(matrix: list[list[int]], target: int) -> bool:
    for row in matrix:                          # L1: iterate over m rows
        if row[0] <= target <= row[-1]:         # L2: O(1) range check
            i = bisect_left(row, target)        # L3: O(log n) binary search
            if i < len(row) and row[i] == target:
                return True
    return False

TypeScript

function searchMatrix(matrix: number[][], target: number): boolean {
    for (const row of matrix) {                              // L1: iterate over m rows
        if (row[0] <= target && target <= row[row.length - 1]) {  // L2: O(1) range check
            let lo = 0, hi = row.length - 1;
            while (lo <= hi) {                               // L3: O(log n) binary search
                const mid = (lo + hi) >> 1;
                if (row[mid] === target) return true;
                if (row[mid] < target) lo = mid + 1;
                else hi = mid - 1;
            }
        }
    }
    return false;
}

Go

func searchMatrix(matrix [][]int, target int) bool {
    for _, row := range matrix {                       // L1: iterate over m rows
        n := len(row)
        if row[0] <= target && target <= row[n-1] {   // L2: O(1) range check
            lo, hi := 0, n-1
            for lo <= hi {                             // L3: O(log n) binary search
                mid := (lo + hi) / 2
                if row[mid] == target {
                    return true
                }
                if row[mid] < target {
                    lo = mid + 1
                } else {
                    hi = mid - 1
                }
            }
        }
    }
    return false
}

Swift

final class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        for row in matrix {
            guard target >= row[0] && target <= row[row.count - 1] else { continue }
            var low = 0
            var high = row.count - 1
            while low <= high {
                let middle = low + (high - low) / 2
                if row[middle] == target { return true }
                if row[middle] < target {
                    low = middle + 1
                } else {
                    high = middle - 1
                }
            }
            return false
        }
        return false
    }
}

Where the time goes, line by line

Variables: m = number of rows, n = number of columns.

Line	Per-call cost	Times executed	Contribution
L1 (row loop)	$O(1)$	m	$O(m)$
L2 (range check)	$O(1)$	m	$O(m)$
L3 (bisect)	$O(log n)$	m	$O(m · log n)$ ← dominates

The range check at L2 prunes rows that can’t contain the target, but in the worst case (all rows could contain it) we still do m binary searches.

Complexity

• Time: $O(m · log n)$, driven by L3 (binary search per row).
• Space: $O(1)$.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Flatten to a single sorted array (optimal)

The two invariants imply the concatenation of rows is a single sorted sequence of length m · n. Binary-search it directly, treating the 1D index as (row, col) via divmod.

Python

def search_matrix(matrix: list[list[int]], target: int) -> bool:
    m, n = len(matrix), len(matrix[0])
    lo, hi = 0, m * n - 1               # L1: O(1) treat matrix as 1D array of size m*n
    while lo <= hi:                       # L2: loop, O(log(m*n)) iterations
        mid = (lo + hi) // 2             # L3: O(1) midpoint
        r, c = divmod(mid, n)            # L4: O(1) decode 1D index to (row, col)
        if matrix[r][c] == target:        # L5: O(1) compare
            return True
        if matrix[r][c] < target:
            lo = mid + 1                  # L6: O(1) narrow right
        else:
            hi = mid - 1                  # L7: O(1) narrow left
    return False

TypeScript

function searchMatrix(matrix: number[][], target: number): boolean {
    const m = matrix.length, n = matrix[0].length;
    let lo = 0, hi = m * n - 1;                   // L1: treat matrix as 1D of size m*n
    while (lo <= hi) {                              // L2: loop, O(log(m*n)) iterations
        const mid = (lo + hi) >> 1;                // L3: O(1) midpoint
        const r = Math.floor(mid / n), c = mid % n; // L4: decode 1D index to (row, col)
        if (matrix[r][c] === target) return true;  // L5: O(1) compare
        if (matrix[r][c] < target) lo = mid + 1;  // L6: O(1) narrow right
        else hi = mid - 1;                         // L7: O(1) narrow left
    }
    return false;
}

Go

func searchMatrix(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])
    lo, hi := 0, m*n-1               // L1: O(1) treat matrix as 1D array of size m*n
    for lo <= hi {                    // L2: loop, O(log(m*n)) iterations
        mid := (lo + hi) / 2        // L3: O(1) midpoint
        r, c := mid/n, mid%n        // L4: O(1) decode 1D index to (row, col)
        if matrix[r][c] == target {  // L5: O(1) compare
            return true
        }
        if matrix[r][c] < target {
            lo = mid + 1             // L6: O(1) narrow right
        } else {
            hi = mid - 1             // L7: O(1) narrow left
        }
    }
    return false
}

Swift

final class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        let rowCount = matrix.count
        let columnCount = matrix[0].count
        var low = 0
        var high = rowCount * columnCount - 1

        while low <= high {
            let middle = low + (high - low) / 2
            let value = matrix[middle / columnCount][middle % columnCount]
            if value == target { return true }
            if value < target {
                low = middle + 1
            } else {
                high = middle - 1
            }
        }
        return false
    }
}

Where the time goes, line by line

Variables: m = number of rows, n = number of columns.

Line	Per-call cost	Times executed	Contribution
L1 (init)	$O(1)$	1	$O(1)$
L2-L5 (loop body)	$O(1)$	log(m · n)	$O(log(m · n)$) ← dominates
L6 or L7 (narrow)	$O(1)$	log(m · n)	$O(log(m · n)$)

The matrix’s two structural properties (sorted rows, each row’s first element exceeds the previous row’s last) mean that reading the elements in row-major order gives a sorted sequence of length m · n. A single binary search over that conceptual 1D array uses log(m · n) = log m + log n steps.

Complexity

• Time: $O(log(m · n)$) = $O(log m + log n)$, driven by L2 (single binary search over m · n elements).
• Space: $O(1)$.

Two-binary-search alternative

Pick the row first with binary search on the first column ($O(log m)$), then binary-search that row ($O(log n)$). Same total complexity, one more index calculation to get wrong.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift notes

[[Int]] is an array of row arrays, not one contiguous flat buffer. The optimal Swift approach maps a virtual flat index back to matrix[index / columns][index % columns]. It gets the binary-search view without allocating or copying a flattened matrix.

Summary

Approach	Time	Space
Linear scan	$O(m · n)$	$O(1)$
Per-row binary search	$O(m · log n)$	$O(1)$
Flattened 1D binary search	$O(log(m · n)$)	$O(1)$

If the problem becomes 240 (Search a 2D Matrix II), rows and columns sorted independently, this approach no longer applies. Use a staircase walk from the top-right in $O(m + n)$.

Test cases

Python

# Quick smoke tests - paste into a REPL or save as test_074.py and run.
# Uses the optimal Approach 3 implementation.

def search_matrix(matrix: list, target: int) -> bool:
    m, n = len(matrix), len(matrix[0])
    lo, hi = 0, m * n - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        r, c = divmod(mid, n)
        if matrix[r][c] == target:
            return True
        if matrix[r][c] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

def _run_tests():
    m = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
    assert search_matrix(m, 3) == True
    assert search_matrix(m, 13) == False
    assert search_matrix([[1]], 1) == True              # 1x1 hit
    assert search_matrix([[1]], 2) == False             # 1x1 miss
    assert search_matrix([[1, 3]], 3) == True           # single row, last element
    assert search_matrix([[1], [3]], 1) == True         # single col, first element
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function searchMatrix(matrix: number[][], target: number): boolean {
    const m = matrix.length, n = matrix[0].length;
    let lo = 0, hi = m * n - 1;
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        const r = Math.floor(mid / n), c = mid % n;
        if (matrix[r][c] === target) return true;
        if (matrix[r][c] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

const mat = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]];
console.assert(searchMatrix(mat, 3) === true);
console.assert(searchMatrix(mat, 13) === false);
console.assert(searchMatrix([[1]], 1) === true);              // 1x1 hit
console.assert(searchMatrix([[1]], 2) === false);             // 1x1 miss
console.assert(searchMatrix([[1, 3]], 3) === true);           // single row, last element
console.assert(searchMatrix([[1], [3]], 1) === true);         // single col, first element
console.log("all tests pass");

Go

package main

import "fmt"

func searchMatrix(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])
    lo, hi := 0, m*n-1
    for lo <= hi {
        mid := (lo + hi) / 2
        r, c := mid/n, mid%n
        if matrix[r][c] == target {
            return true
        }
        if matrix[r][c] < target {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return false
}

func main() {
    mat := [][]int{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}}
    if !searchMatrix(mat, 3)                          { panic("test 1") }
    if searchMatrix(mat, 13)                          { panic("test 2") }
    if !searchMatrix([][]int{{1}}, 1)                 { panic("test 3") } // 1x1 hit
    if searchMatrix([][]int{{1}}, 2)                  { panic("test 4") } // 1x1 miss
    if !searchMatrix([][]int{{1, 3}}, 3)              { panic("test 5") } // single row, last element
    if !searchMatrix([][]int{{1}, {3}}, 1)            { panic("test 6") } // single col, first element
    fmt.Println("all tests pass")
}

Related data structures

• Arrays, row-major layout; index arithmetic with divmod

Related concepts

• Binary Search, the halving tactic for ordered spaces where one side can be discarded.
• Array Scans, the linear pass habit of carrying just enough state while reading each item once.