Leetcode 74: Search a 2D Matrix

1. Problem Statement (Simple Explanation)

You’re given an m x n integer matrix with these properties:

1. Each row is sorted in non-decreasing order.

2. The first integer of each row is greater than the last integer of the previous row.

This means if you read the matrix row by row, it behaves like a sorted 1D array.

You must determine if a given target exists in the matrix, and you must do it in:

O(log(m * n))  // logarithmic in total number of elements

Return true if target is found, otherwise false.

2. Examples

Example 1:

Input:

matrix = [

  [ 1,  3,  5,  7],

  [10, 11, 16, 20],

  [23, 30, 34, 60]

]

target = 3

3 is present at (0,1).

Output: true

Example 2:

Input:

matrix = [

  [ 1,  3,  5,  7],

  [10, 11, 16, 20],

  [23, 30, 34, 60]

]

target = 13

13 is not in the matrix.

Output: false

3. Approach – Binary Search on Virtual 1D Array (O(log(m·n)))

Because of the given properties:

• The matrix elements in row-major order are sorted:

matrix[0][0], matrix[0][1], ..., matrix[0][n-1],

matrix[1][0], ...,                 matrix[1][n-1],

...

matrix[m-1][0], ...,               matrix[m-1][n-1]

We can treat this as a sorted 1D array of length m * n and run a standard binary search.

We just need a mapping from 1D index mid into 2D indices (row, col):

row = mid / n

col = mid % n

(where n is the number of columns).

Binary search then works as usual:

1. left = 0, right = m*n - 1

2. While left <= right:

• mid = left + (right - left) / 2

• val = matrix[row][col] at that mid.

• Compare val with target and adjust search bounds.

Pseudo-code:

Complexity:

• Time:

• Binary search over m*n elements → O(log(m*n))

• Space:

• O(1) extra space.

Satisfies problem’s requirement.

4. Java code

5. C code

6. C++ code

7. Python code

8. JavaScript code