74. Search a 2D Matrix - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description: We are given an m x n integer matrix with the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

Write an efficient algorithm to search for a given target value in this matrix. The algorithm should return true if the target is found or false otherwise. (Note: The expected time complexity is O(log(m * n)) for an optimal solution .)

Constraints:

1 <= m, n <= 100 (matrix dimensions)
-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
Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Example 3:
Input: matrix = [[1]], target = 1
Output: true (the single element matches the target)

Optimal Approaches

The matrix’s sorted structure allows us to search much faster than brute-force (which would be O(mn)). In fact, we can achieve **O(log(mn))** time by using binary search. Below we cover two optimal approaches: one treats the matrix as a flat sorted list, and the other performs binary search first on rows then on columns. Both run in logarithmic time and use only O(1) extra space.

Approach 1: Binary Search Treating the Matrix as a 1D Array

Idea: Because each row is sorted and each row’s first element is greater than the previous row’s last, the entire matrix can be thought of as one sorted list of length m*n in row-major order. We can map any index in this virtual 1D list to a matrix cell. Therefore, we can perform a standard binary search over the range of indices [0, m*n - 1] and map the mid index to (row, col) in the matrix. This approach is very efficient, running in O(log(m*n)) time and requiring no extra space .

Step-by-step:

Let m be the number of rows and n be the number of columns. Define two pointers: left = 0 and right = m*n - 1 (these represent indices in the flattened array).
While left <= right:
- Compute mid = (left + right) // 2.
- Map the 1D index mid to 2D coordinates: row = mid // n (integer division) and col = mid % n.
- Let val = matrix[row][col] be the mid element.
- If val == target: return true (target found).
- Else if val < target: move left up to mid + 1 (search right half).
- Else if val > target: move right down to mid - 1 (search left half).
If the loop finishes without finding the target, return false.

Below is the implementation of this approach in Python and Java. Both programs read the matrix and target from standard input and print "true" or "false" as the result.

Python Implementation (Approach 1)

Python3

. . . .

Java Implementation (Approach 1)

Java

. . . .

Time Complexity: O(log(m * n)) – We perform binary search on m*n elements. For example, a 100x100 matrix (10,000 elements) would take at most ~14 comparisons in the worst case.

Space Complexity: O(1) – We only use a few variables for indexing, and no additional data structures outside the input.

Approach 2: Two-Step Binary Search (Find Row, Then Column)

Idea: Another optimal method is to first narrow down which row the target could be in, then search within that row. Since the first element of each row is greater than the last element of the previous row, the target, if it exists, must lie in one particular row. We can use binary search on the first (or last) elements of each row to find the candidate row, and then do a binary search on that row. This approach runs in O(log m + log n) time, which is essentially the same as O(log(m*n)) , and also uses constant extra space.

Step-by-step:

Check matrix boundaries. If target is less than the first element of the matrix or greater than the last element of the matrix, return false immediately (the target is out of the range of all values).
Use binary search on the rows (for example, comparing the target to the first element of each row or the last element of each row) to find an index row such that the target must be in this row if it exists. Specifically:
- Initialize low = 0 and high = m - 1.
- While low <= high:
  - mid = (low + high) // 2.
  - Let first = matrix[mid][0] and last = matrix[mid][n-1] (first and last elements of the mid row).
  - If target is between first and last (inclusive), then the target could be in row mid. Set targetRow = mid and break out of the loop.
  - Else if target < first, set high = mid - 1 (target must be above in an earlier row).
  - Else if target > last, set low = mid + 1 (target must be below in a later row).
- If no row was found (i.e., target is not within the range of any row), return false.
Once the candidate row is identified, perform a standard binary search on that row to look for the target. Compare with the middle element of the row and adjust the search range (left/right within that row) accordingly. If found, return true; if not, return false.

Python Implementation (Approach 2)

Python3

. . . .

Java Implementation (Approach 2)

Java

. . . .

Time Complexity: O(log m + log n). In the worst case, we do one binary search over m rows and another over n columns. Since these searches happen sequentially, the complexity adds up. This is essentially equivalent to O(log(m * n)) time (for example, searching 100 rows and then 100 columns takes about 7 steps + 7 steps ≈ 14 steps, similar to a single binary search on 10,000 elements).

Space Complexity: O(1). We only use a fixed number of variables for indexing and comparisons.

Edge Cases

Single Row or Column: The matrix could effectively be 1D (e.g. 1×N or M×1). Both approaches handle this naturally. For example, a single-row matrix is just a sorted list – the binary search will correctly find the target or determine it's absent.
Single Element Matrix: If the matrix has just one element (1×1), the algorithm should return true if the target equals that element, or false otherwise. (Example: matrix [[5]], target 5 → true; target 2 → false.)
Target Out of Range: If the target is smaller than the smallest element in the matrix or larger than the largest element, the search can return false immediately. Our second approach explicitly checks this scenario up front. In the first approach, the binary search will naturally terminate without finding the target, but it's still a good mental check.
Empty Matrix: If m or n is 0 (i.e. no rows or no columns), the function should return false. (The given constraints ensure at least 1 row and 1 column, so this may not occur in this problem, but it's good practice to handle it.)

For further practice, you can try these related LeetCode problems:

33. Search in Rotated Sorted Array: Search for a target in a sorted array that has been rotated (modified binary search logic needed).
240. Search a 2D Matrix II: A variant where each row and column is sorted (not the strict row-major ordering of this problem). Requires an O(m + n) search strategy.

74. Search a 2D Matrix - Detailed Explanation

Problem Statement

Optimal Approaches

Approach 1: Binary Search Treating the Matrix as a 1D Array

Python Implementation (Approach 1)

Java Implementation (Approach 1)

Approach 2: Two-Step Binary Search (Find Row, Then Column)

Python Implementation (Approach 2)

Java Implementation (Approach 2)

Edge Cases

Related Problems