LeetCode 74 - Search a 2D Matrix

This problem gives us a two dimensional matrix with two very important ordering properties: 1. Each row is sorted from left to right in non-decreasing order. 2. The first element of every row is greater than the last element of the previous row.

leetcodemediumarraybinary-searchmatrix

LeetCode Problem 74

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Matrix

Solution

LeetCode 74 - Search a 2D Matrix

Problem Understanding

This problem gives us a two dimensional matrix with two very important ordering properties:

  1. Each row is sorted from left to right in non-decreasing order.
  2. The first element of every row is greater than the last element of the previous row.

These two guarantees together mean the entire matrix behaves like one globally sorted list.

For example, this matrix:

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

can be viewed as:

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

The problem asks us to determine whether a given target value exists somewhere in the matrix.

The key requirement is that the algorithm must run in O(log(m * n)) time complexity, where:

  • m is the number of rows
  • n is the number of columns

This immediately suggests that a binary search based solution is expected, because binary search naturally operates in logarithmic time on sorted data.

The constraints are relatively small:

  • 1 <= m, n <= 100
  • Matrix values range from -10^4 to 10^4

Even though the matrix size is small enough for brute force to pass in practice, the problem explicitly requires logarithmic complexity, so we must use the matrix ordering efficiently.

Some important edge cases to keep in mind include:

  • A matrix containing only one element
  • A target smaller than the smallest element
  • A target larger than the largest element
  • A target located at the first or last position
  • Matrices with only one row
  • Matrices with only one column

The problem guarantees that every row exists and contains at least one element, so we do not need to handle jagged or malformed matrices.

Approaches

Brute Force Approach

The most straightforward solution is to scan every element in the matrix one by one.

We iterate through each row, then iterate through every value inside that row. If we find the target, we return True. If we finish scanning the entire matrix without finding it, we return False.

This approach is correct because it checks every possible location where the target could appear.

However, its time complexity is O(m * n) because every element may need to be visited. This does not satisfy the required O(log(m * n)) complexity.

Optimal Approach, Binary Search on a Virtual Sorted Array

The key observation is that the matrix is globally sorted when viewed row by row.

Because:

  • every row is sorted, and
  • the first element of each row is larger than the previous row's last element,

the matrix can be treated as a single sorted one dimensional array.

Instead of physically flattening the matrix, we can simulate this mapping mathematically.

If the matrix has n columns:

  • The row index becomes mid // n
  • The column index becomes mid % n

This lets us perform binary search directly on the matrix without extra space.

Since binary search cuts the search range in half each iteration, the runtime becomes O(log(m * n)).

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n) O(1) Checks every element sequentially
Optimal O(log(m * n)) O(1) Uses binary search on a virtual sorted array

Algorithm Walkthrough

  1. Determine the matrix dimensions.

We store:

  • rows = len(matrix)
  • cols = len(matrix[0])

These values are needed for index conversions between the virtual one dimensional array and the actual matrix coordinates. 2. Initialize binary search boundaries.

Since the matrix behaves like a sorted array of size rows * cols, the valid indices are:

  • left = 0
  • right = rows * cols - 1
  1. Compute the middle position.

During each iteration:

mid = (left + right) // 2

This represents the index inside the virtual flattened array. 4. Convert the virtual index into matrix coordinates.

We map the one dimensional index back into two dimensional coordinates:

row = mid // cols
col = mid % cols

This works because every row contains exactly cols elements. 5. Compare the matrix value with the target.

Retrieve:

value = matrix[row][col]

Then compare:

  • If value == target, return True
  • If value < target, search the right half
  • If value > target, search the left half
  1. Continue until the search space is exhausted.

If left becomes greater than right, the target does not exist in the matrix, so return False.

Why it works

The algorithm works because the matrix ordering guarantees that reading elements row by row produces a fully sorted sequence.

Binary search relies on one invariant: the remaining search range is always sorted. Since our virtual flattened array is sorted, each comparison allows us to safely discard half of the remaining elements.

The index conversion formulas correctly map virtual indices back into matrix positions, so every binary search step accesses the proper matrix element.

Python Solution

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows = len(matrix)
        cols = len(matrix[0])

        left = 0
        right = rows * cols - 1

        while left <= right:
            mid = (left + right) // 2

            row = mid // cols
            col = mid % cols

            value = matrix[row][col]

            if value == target:
                return True

            if value < target:
                left = mid + 1
            else:
                right = mid - 1

        return False

The implementation begins by computing the matrix dimensions. Since the matrix is guaranteed to contain at least one row and one column, accessing matrix[0] is safe.

The variables left and right define the search range over the virtual flattened array. Instead of building an actual one dimensional list, the code converts indices dynamically.

Inside the loop, the midpoint is calculated normally for binary search. The formulas:

row = mid // cols
col = mid % cols

translate the flattened index into actual matrix coordinates.

The value at that position is compared with the target. Depending on the comparison result, the algorithm discards half of the remaining search range.

If the target is found, the function immediately returns True. Otherwise, when the search interval becomes empty, the function returns False.

Go Solution

func searchMatrix(matrix [][]int, target int) bool {
    rows := len(matrix)
    cols := len(matrix[0])

    left := 0
    right := rows*cols - 1

    for left <= right {
        mid := (left + right) / 2

        row := mid / cols
        col := mid % cols

        value := matrix[row][col]

        if value == target {
            return true
        }

        if value < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return false
}

The Go implementation follows the exact same logic as the Python version.

Go uses integer division automatically for integer operands, so:

row := mid / cols

correctly computes the row index.

Slices in Go naturally represent the matrix rows, so accessing matrix[row][col] works similarly to Python lists.

The problem guarantees at least one row and one column, so no additional nil or empty checks are necessary.

Worked Examples

Example 1

Input:

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

target = 3

The virtual flattened array is:

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

Matrix dimensions:

rows = 3
cols = 4

Initial bounds:

left = 0
right = 11
Iteration left right mid row col value Action
1 0 11 5 1 1 11 Search left half
2 0 4 2 0 2 5 Search left half
3 0 1 0 0 0 1 Search right half
4 1 1 1 0 1 3 Found target

The algorithm returns True.

Example 2

Input:

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

target = 13

Initial bounds:

left = 0
right = 11
Iteration left right mid row col value Action
1 0 11 5 1 1 11 Search right half
2 6 11 8 2 0 23 Search left half
3 6 7 6 1 2 16 Search left half
4 6 5 - - - - Stop

The search space becomes empty, so the algorithm returns False.

Complexity Analysis

Measure Complexity Explanation
Time O(log(m * n)) Binary search halves the search space each iteration
Space O(1) Only a few variables are used

The matrix contains m * n total elements. Binary search performs at most log2(m * n) iterations because each step removes half of the remaining candidates.

No auxiliary data structures are created, so the algorithm uses constant extra memory.

Test Cases

sol = Solution()

# Provided examples
assert sol.searchMatrix(
    [[1, 3, 5, 7],
     [10, 11, 16, 20],
     [23, 30, 34, 60]], 3
) is True  # target exists

assert sol.searchMatrix(
    [[1, 3, 5, 7],
     [10, 11, 16, 20],
     [23, 30, 34, 60]], 13
) is False  # target missing

# Single element matrix
assert sol.searchMatrix([[5]], 5) is True  # single element found
assert sol.searchMatrix([[5]], 1) is False  # single element not found

# Single row matrix
assert sol.searchMatrix([[1, 2, 3, 4, 5]], 4) is True  # target in row
assert sol.searchMatrix([[1, 2, 3, 4, 5]], 6) is False  # target absent

# Single column matrix
assert sol.searchMatrix([[1], [3], [5], [7]], 5) is True  # target in column
assert sol.searchMatrix([[1], [3], [5], [7]], 2) is False  # target absent

# Target at boundaries
assert sol.searchMatrix(
    [[1, 3, 5],
     [7, 9, 11]], 1
) is True  # first element

assert sol.searchMatrix(
    [[1, 3, 5],
     [7, 9, 11]], 11
) is True  # last element

# Negative values
assert sol.searchMatrix(
    [[-10, -5, -2],
     [0, 3, 8]], -5
) is True  # negative target

assert sol.searchMatrix(
    [[-10, -5, -2],
     [0, 3, 8]], 4
) is False  # missing value

# Larger matrix
assert sol.searchMatrix(
    [[1, 4, 7, 10],
     [12, 15, 18, 21],
     [25, 30, 35, 40]], 35
) is True  # larger matrix search
Test Why
Example 1 Verifies successful search
Example 2 Verifies unsuccessful search
Single element matrix Tests smallest possible input
Single row matrix Ensures row-only structure works
Single column matrix Ensures column-only structure works
First element target Tests lower boundary
Last element target Tests upper boundary
Negative values Ensures handling of negative integers
Larger matrix Verifies general correctness

Edge Cases

Single Element Matrix

A matrix containing exactly one value is the smallest possible valid input. Binary search implementations sometimes fail on tiny ranges because of incorrect loop conditions or boundary updates.

For example:

[[5]]

If the target is 5, the algorithm immediately checks index 0 and returns True. If the target differs, the search range becomes invalid after one iteration and correctly returns False.

Target Smaller Than the Minimum or Larger Than the Maximum

When the target lies outside the matrix range, the algorithm should terminate cleanly without invalid indexing.

For example:

matrix = [[1, 3, 5]]
target = -1

or:

target = 100

Binary search naturally handles these situations by shrinking the search interval until left > right.

Single Row or Single Column

Some implementations accidentally assume both dimensions are larger than one.

For example:

[[1, 2, 3, 4]]

or:

[[1],
 [3],
 [5]]

The index mapping formulas still work correctly because:

row = mid // cols
col = mid % cols

remain valid even when cols == 1 or rows == 1.

Target Located at Matrix Boundaries

Targets at the very beginning or very end of the matrix can expose off by one errors in binary search implementations.

Examples include:

target = matrix[0][0]

and:

target = matrix[rows - 1][cols - 1]

The algorithm handles these correctly because the initial search range includes every valid index from 0 through rows * cols - 1.