Search a 2D Matrix

Problem

You are given an m x n integer matrix with the following two properties: each row is sorted in non-decreasing order, and the first integer of each row is greater than the last integer of the previous row. Given an integer target, return true if target is in matrix or false otherwise.

Examples

The brute-force approach

Scan every cell. Return true if any equals target.

for row in matrix:
    for val in row:
        if val == target: return True
return False

O(m×n) — ignores the sorted structure.

Spotting the pattern

This is a Binary Search problem. The key question to ask yourself:

If you flatten the matrix into a 1D array, what is the formula to convert a 1D index i back to row and column? Which integer operations do you use?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.