Skip to main content
Talentd

Search a 2D Matrix - Solution & Explanation

MediumArrayBinary SearchMatrix24 min readAsked at: Amazon, Microsoft, Apple +16
Practice this problem

Problem Statement

You are given an m x n integer matrix matrix with the following two properties:

  • Each row is sorted in non-decreasing order.
  • 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.

You must write a solution in O(log(m * n)) time complexity.

 

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

 

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -104 <= matrix[i][j], target <= 104

Approach Overview

Problem Overview: You are given an m x n matrix where each row is sorted in ascending order and the first element of each row is greater than the last element of the previous row. The task is to determine whether a given target value exists in the matrix.

Approach 1: Binary Search on Matrix as a 1D Array (O(log(m*n)) time, O(1) space)

The key insight is that the matrix behaves like a globally sorted array. Because every row starts with a value greater than the previous row’s last value, you can conceptually flatten the matrix into a single sorted list of size m * n. Run standard binary search on indices from 0 to m*n - 1. Convert a 1D index back to matrix coordinates using row = mid / n and col = mid % n. Each step compares matrix[row][col] with the target and halves the search space. This approach is optimal because it treats the structure as a single sorted dataset while keeping constant memory.

Approach 2: Two-step Binary Search (Row then Column) (O(log m + log n) time, O(1) space)

This method performs two separate binary searches. First, run binary search on the rows to locate the only row that could contain the target. Compare the target with the first and last element of each row to narrow down the candidate row. Once the correct row is identified, run a second binary search within that row to locate the target value. This approach explicitly uses the row ordering property of the matrix and the sorted order inside each row. It is easy to reason about during interviews because the two steps clearly mirror the structure of the data.

Both solutions rely on the same property: the matrix behaves like a sorted structure. The first approach compresses the entire matrix into a conceptual array, while the second approach searches rows and columns separately. Either way, the algorithm repeatedly halves the search space using array indexing and binary search comparisons.

Recommended for interviews: The 1D binary search approach is usually the expected optimal solution. It demonstrates that you recognize the matrix is globally sorted and can transform the problem into classic binary search. The two-step method is also accepted and often easier to derive during an interview because it directly uses the matrix layout.

Approach 1: Binary Search on Matrix as a 1D Array

The matrix can be viewed as a single sorted list. Hence, we can perform a binary search on the entire matrix by treating it as a 1D array. Suppose we have a matrix of size m x n, any element in the matrix can be accessed using a single index calculated as follows:

Element at index k can be accessed using matrix[k / n][k % n], where / and % represent integer division and modulus operations, respectively.

This approach ensures that the solution operates in O(log(m * n)) time complexity as required.

The function searchMatrix implements binary search on a conceptual 1D version of the matrix. The mid index is calculated using integer division and modulus to map it to the matrix cell. This mapping ensures that all matrix elements can be inspected via binary search.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(log(m * n))
Space complexity: O(1)

Try this approach in the editor →

Approach 2: Two-step Binary Search (Row then Column)

The problem also allows for a two-step binary search owing to the special properties of the matrix. First, we identify the row which potentially contains the target by performing binary search on first elements of each row. Then, we conduct a binary search in that specific row.

Although not strictly O(log(m * n)), this approach exploits the matrix's properties in an efficient manner for similar effective results.

This C code expands the binary search to two distinct logical steps: first identifying the potential row and then binary searching within that row itself to find the target efficiently.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(log(m) + log(n))
Space complexity: O(1)

Try this approach in the editor →

Approach 3: Binary Search

We can logically unfold the two-dimensional matrix and then perform binary search.

The time complexity is O(log(m times n)), where m and n are the number of rows and columns of the matrix, respectively. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Approach 4: Search from the Bottom Left or Top Right

Here, we start searching from the bottom left corner and move towards the top right direction. We compare the current element matrix[i][j] with target:

  • If matrix[i][j] = target, we have found the target value and return true.
  • If matrix[i][j] > target, all elements to the right of the current position in this row are greater than target, so we should move the pointer i upwards, i.e., i = i - 1.
  • If matrix[i][j] < target, all elements above the current position in this column are less than target, so we should move the pointer j to the right, i.e., j = j + 1.

If we still can't find target after the search, return false.

The time complexity is O(m + n), where m and n are the number of rows and columns of the matrix, respectively. The space complexity is O(1).

Code

PythonJavaC++GoRustJavaScript

Python

Java

C++

Go

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search on Matrix as a 1D Array

Time complexity: O(log(m * n))
Space complexity: O(1)

Two-step Binary Search (Row then Column)

Time complexity: O(log(m) + log(n))
Space complexity: O(1)

Binary Search—
Search from the Bottom Left or Top Right—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Binary Search on Matrix as 1D ArrayO(log(m*n))O(1)Best general solution when the matrix behaves like a globally sorted array
Two-step Binary Search (Row then Column)O(log m + log n)O(1)Useful when reasoning about row ranges first and then searching within a row

Video Solution

BS-24. Search in a 2D Matrix - I | Binary Search of 2D • take U forward • 278,743 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Search a 2D Matrix easy or hard?
Search a 2D Matrix is considered a Medium difficulty problem. The main challenge is recognizing that the matrix can be treated as a single sorted array, which allows binary search instead of scanning rows linearly.
Search a 2D Matrix Python or Java solution?
Python and Java implementations typically perform binary search across the virtual index range 0 to m*n-1. Each midpoint index is converted to matrix coordinates using division and modulus operations, then compared with the target to adjust the search boundaries.
How to solve Search a 2D Matrix in O(log(m*n))?
Treat the matrix as a flattened sorted array with m*n elements. Perform binary search on index range 0 to m*n-1 and convert each midpoint into matrix coordinates using row = mid / n and col = mid % n. Compare the value at matrix[row][col] with the target and adjust the search range accordingly.
What is the best approach for Search a 2D Matrix?
Binary search on the matrix treated as a virtual 1D array is the most efficient approach. Because each row's first element is greater than the previous row's last element, the matrix is globally sorted. Applying binary search over indices from 0 to m*n-1 gives O(log(m*n)) time and O(1) space complexity.
Is Search a 2D Matrix asked at Google/Amazon/Meta?
Search a 2D Matrix is a common binary search interview question and has appeared in interviews at companies like Amazon, Google, and Meta. It tests whether candidates can recognize hidden sorted structures and apply binary search beyond simple arrays.
What data structure is used in Search a 2D Matrix?
The problem uses a 2D matrix represented as a nested array structure. The algorithm relies on binary search and index arithmetic to map between a conceptual 1D array and 2D matrix coordinates.
What is the time complexity of Search a 2D Matrix?
The optimal solution runs in O(log(m*n)) time using binary search over the entire matrix. Another valid approach performs binary search twice—first to locate the candidate row and then within that row—resulting in O(log m + log n) time. Both approaches use constant O(1) extra space.

Ready to solve this problem?

Practice Search a 2D Matrix with our built-in code editor and test cases.

Practice on FleetCode
Previous

Search a 2D Matrix II

Next

Split Message Based on Limit