Search a 2D Matrix II

Medium
828.

Search a 2D Matrix II

Search a 2D Matrix II is a medium coding problem on arrays, binary search and matrix, asked in Amazon, Google, Microsoft and Zomato interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Search a 2D Matrix II — Solution in Python, Java & C++

Search a 2D Matrix II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Search a 2D Matrix II is a medium coding problem on arrays, binary search and matrix, asked in Amazon, Google, Microsoft and Zomato interviews.

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.

Hints for Search a 2D Matrix II

  1. Hint 1

    Flattening the matrix does not give a sorted array here, so a single binary search will not work.

  2. Hint 2

    Start at the top-right corner: it is the largest in its row and the smallest in its column.

  3. Hint 3

    Each comparison eliminates a whole row or a whole column.

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

  1. Start at row 0, last column.
  2. If the value equals the target, answer true.
  3. If it is greater, no value in that column can be the target, so move left.
  4. 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

Java

public static boolean searchMatrix(int[][] matrix, int target) {
    int 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;
}

C++

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int r = 0, c = (int) matrix[0].size() - 1;
    while (r < (int) matrix.size() && c >= 0) {
        if (matrix[r][c] == target) return true;
        if (matrix[r][c] > target) c--; else r++;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search