Search a 2D Matrix

Problem in Plain English

You are given an m by n matrix where each row is sorted and every row starts after the previous row ends, plus a target integer. Return true when the target appears in the matrix and false otherwise.

Problem Statement

You are given an m x n integer matrix matrix with 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. The required solution runs in $O(log(m * n))$ time.

Constraints

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4

Examples

Example 1

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

The value 3 sits at row 0, column 1, so the answer is true.

Example 2

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

The target 13 lies between 11 and 16 in the second row. Neither cell equals 13, and the row boundaries rule out every other row, so return false.

Example 3

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

The minimum-size matrix has one candidate cell, and its value equals the negative target. The inclusive search interval must examine that cell and return true.

Example 4

Input: matrix = [[1,1,3],[5,5,8]], target = 5
Output: true

Duplicates within a row are allowed. Both 5 values occur in row 1, so finding either is sufficient; strict separation between rows still makes the virtual sequence sorted.

Intuition

Reading each row left to right and then moving to the next row gives one sorted sequence: the next row begins above the previous row's last value. In Example 1 the virtual list is [1,3,5,7,10,11,16,20,23,30,34,60]. Binary search repeatedly halves a candidate interval; integer division by the four columns converts a virtual position to its row, and the remainder gives its column. The list is a way to reason about the input, so there is no need to allocate it.

Approaches

Linear Scan

Solution Details

Reveal Linear Scan: intuition, complexity, and code

Intuition

Inspect every cell until one equals the target. This baseline needs no ordering assumption, but an absent target or a match in the final cell forces a full scan instead of using the matrix's sorted order.

Step-by-Step Logic

Visit rows from top to bottom, and columns from left to right within each row. In Example 1 there are three rows and four columns, with target 3.
At each cell, compare its value with target and immediately return true on equality. The first cell at row 0, column 0 holds 1, so increment the column to 1.
The next cell holds 3 at row 0, column 1, so Example 1 returns true before moving to another row.
If a row ends without a match, start column 0 of the next row. If all rows end without a match, return false.

Why It Works

Before checking a cell, every earlier cell in row order has been examined and is unequal to target. Each loop increment advances to the next unexamined cell, so no position is skipped. Returning true requires an actual equality; if the loops finish, every position has failed equality and returning false is correct.

Dry Run

Linear Scan: variable states at each step
Event	row i / r	column j / c	cell value	comparison	next state / result
Initialize outer and inner loops	0	0	1	1 != 3	column advances 0 to 1; row stays 0
Read next cell	0	1	3	3 == 3	return true; no further increment

Complexity Analysis

Time Complexity

O(m * n)

Space Complexity

O(1)

Let m be the row count and n the column count. The nested loops inspect at most m * n cells, with equality tested once per cell. An absent target realizes this worst case. Only loop counters and the Boolean result use extra storage: no flattened list, slices, recursion or input mutation.

Code

Solution.java

1class Solution {2    public boolean searchMatrix(int[][] matrix, int target) {3        for (int i = 0; i < matrix.length; i++) {4            for (int j = 0; j < matrix[0].length; j++) {5                if (matrix[i][j] == target) {6                    return true;7                }8            }9        }10        return false;11    }12}

Hints

Hint 1

Read the two sorting rules together: the last value of each row sits below the first value of the next row, so the matrix is one sorted sequence.

Hint 2

A flat position mid in a row of n columns converts to row mid / n and column mid % n with integer division.

Hint 3

Run standard binary search on the range 0 to m * n - 1 and compare matrix[row][col] against target at each step.

Edge Cases

A single-cell matrix such as [[1]] works because left and right both start at 0.
A target smaller than the first cell or larger than the last cell exhausts the range and returns false.
A single-row or single-column matrix still maps correctly since the divisor n equals the true column count.

Common Mistakes and Interview Tips

Applying this virtual binary search to a matrix that has only individually sorted rows. For [[1,4],[2,5]], row boundaries break the global order, so this method can discard a present target.
Dividing mid by the row count m instead of the column count n, or swapping quotient and remainder, maps rectangular matrices to the wrong cell.
Using ordinary division in Python or JavaScript produces a fractional row; use // or Math.floor. Java int division already truncates nonnegative indices.
Allocating a flattened list first adds O(m * n) copying time and space, defeating the required logarithmic search and constant extra storage.
Using left < right skips the final candidate; updating a bound to mid rather than mid + 1 or mid - 1 can stall on a small interval.
Assuming rows are strictly increasing rejects valid duplicates within a row. Non-decreasing order is enough; separation between rows is strict. The stated input is nonempty, so matrix[0] is valid.

Key Takeaway

When a 2D grid flattens into one sorted sequence, binary search over virtual indices with arithmetic mapping beats scanning every cell.