Search a 2D Matrix II — Medium Problem & Solution

Each row of matrix is sorted in ascending order left to right, and each column is sorted in ascending order top to bottom.

Difficulty: Medium
Topics: Arrays, Matrix, Binary Search, Divide and Conquer
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Each row of matrix is sorted in ascending order left to right, and each column is sorted in ascending order top to bottom. Unlike the simpler version, rows do not continue from one another.

Return whether target is present.

Example 1

Input: matrix = [[1,4,7,11],[2,5,8,12],[3,6,9,16],[10,13,14,17]], target = 5
Output: true

Example 2

Input: matrix = [[1,4,7,11],[2,5,8,12],[3,6,9,16],[10,13,14,17]], target = 20
Output: false

Example 3

Input: matrix = [[5]], target = 5
Output: true

Constraints

1 <= rows, cols <= 300
-1000000000 <= matrix[i][j], target <= 1000000000
Each row is sorted ascending; each column is sorted ascending.

How to solve Search a 2D Matrix II

The top-right corner is a decision point: it is the maximum of its row and the minimum of its column, so comparing it with the target rules out one entire line each step. That is the staircase search.

Approach

Start at row 0, last column.
If the value equals the target, answer true.
If it is greater, no value in that column can be the target, so move left.
If it is smaller, no value in that row can be the target, so move down.

Why it works

At the top-right, everything below in the column is larger and everything left in the row is smaller. So a value greater than the target eliminates its column (all larger still), and a value smaller eliminates its row (all smaller to the left). Each step removes a row or a column, giving O(m + n) — better than the O(m log n) of binary-searching each row.

Complexity

Time — O(m + n)
Space — O(1)

Pitfalls

Starting at the top-left or bottom-right gives no usable decision — both directions increase or both decrease.
Treating the matrix as one sorted array is the previous problem's structure, not this one's.
The bounds check must cover both the row and the column.

Reference solution

Python

from typing import List

def searchMatrix(matrix: List[List[int]], target: int) -> bool:
    r, c = 0, len(matrix[0]) - 1
    while r < len(matrix) and c >= 0:
        if matrix[r][c] == target:
            return True
        if matrix[r][c] > target:
            c -= 1
        else:
            r += 1
    return False

JavaScript

var searchMatrix = function(matrix, target) {
    var r = 0, c = matrix[0].length - 1;
    while (r < matrix.length && c >= 0) {
        if (matrix[r][c] === target) return true;
        if (matrix[r][c] > target) c--; else r++;
    }
    return false;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue