Skip to main content
Talentd

Search a 2D Matrix II - Solution & Explanation

MediumArrayBinary SearchDivide and ConquerMatrix25 min readAsked at: Amazon, Microsoft, Apple +13
Practice this problem

Problem Statement

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

 

Example 1:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Example 2:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false

 

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -109 <= matrix[i][j] <= 109
  • All the integers in each row are sorted in ascending order.
  • All the integers in each column are sorted in ascending order.
  • -109 <= target <= 109

Approach Overview

Problem Overview: You are given an m x n matrix where each row is sorted left to right and each column is sorted top to bottom. The task is to determine whether a target value exists in the matrix without scanning every element.

Approach 1: Start from Top-Right Corner (O(m + n) time, O(1) space)

This approach exploits the sorted structure of both rows and columns. Start at the top-right element. From this position, each comparison eliminates either a full row or a full column. If the current value is greater than the target, move left because all values below are even larger. If the value is smaller than the target, move down since everything to the left is smaller. Each step removes one row or column from consideration, so you perform at most m + n moves.

The key insight: the top-right corner acts like a pivot where one direction strictly decreases and the other strictly increases. This allows deterministic movement similar to a two-pointer scan in a sorted grid. The algorithm uses only index movement and comparisons, so the extra memory remains constant. This technique frequently appears in problems involving sorted matrices and grid monotonicity, making it a useful pattern for array and matrix search problems.

Approach 2: Binary Search in Rows (O(m log n) time, O(1) space)

Another option is to treat each row as an independent sorted array and apply binary search. Iterate through every row and check whether the target can exist in that row by comparing it with the row's first and last elements. If the target falls within that range, run binary search on that row to locate it.

This works because each row is individually sorted, which fits the classic binary search pattern. However, you still need to iterate through up to m rows, and each binary search costs O(log n). The result is O(m log n) time. While slower than the optimal solution, this approach is straightforward to implement and easy to reason about during interviews.

Recommended for interviews: Interviewers usually expect the top-right traversal. It shows you recognize the monotonic ordering across both dimensions and can eliminate rows or columns in constant time per step. The row-wise binary search approach demonstrates understanding of sorted arrays, but the O(m + n) strategy highlights stronger algorithmic insight and familiarity with matrix search patterns often discussed alongside divide and conquer style reasoning.

Approach 1: Approach 1: Start from Top-Right Corner

This approach begins searching from the top-right corner of the matrix. If the current element is equal to the target, return true. If the current element is greater than the target, move left. If the current element is less than the target, move down. This method effectively narrows down the search space, taking advantage of the sorted property of the matrix.

The solution initializes the search at the top-right corner of the matrix. It iteratively checks the current element against the target and adjusts the row and column pointers accordingly. If the current element is larger than the target, it moves left; if smaller, it moves down. It returns true if the target is found and false if the pointers go out of bounds.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m + n), where m is the number of rows and n is the number of columns.
Space Complexity: O(1), as no extra space is used.

Try this approach in the editor →

Approach 2: Approach 2: Binary Search in Rows

This approach uses binary search on each row of the matrix. Since each row is sorted, binary search can efficiently determine if the target exists within the row. If found in any row, the function returns true.

The C code uses a helper function `binarySearch` to search within a row. It iterates through each row of the matrix and applies binary search. If the target is found in any row, it returns true; otherwise, it iterates through all rows and returns false afterward.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * log(n)), where m is the number of rows and n is the number of columns.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Binary Search

Since all elements in each row are sorted in ascending order, for each row, we can use binary search to find the first element greater than or equal to target, and then check if that element is equal to target. If it is equal to target, it means the target value is found, and we return true. If it is not equal to target, it means all elements in this row are less than target, and we should continue searching the next row.

If all rows have been searched and the target value is not found, it means the target value does not exist, and we return false.

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

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Approach 4: Search from Bottom-Left or Top-Right

We start the search from the bottom-left or top-right corner and move towards the top-right or bottom-left direction. Compare the current element matrix[i][j] with target:

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

If the search ends and the target is not found, 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++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Start from Top-Right Corner

Time Complexity: O(m + n), where m is the number of rows and n is the number of columns.
Space Complexity: O(1), as no extra space is used.

Approach 2: Binary Search in Rows

Time Complexity: O(m * log(n)), where m is the number of rows and n is the number of columns.
Space Complexity: O(1).

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

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Top-Right Corner TraversalO(m + n)O(1)Best general solution when rows and columns are both sorted
Binary Search in Each RowO(m log n)O(1)Useful when treating rows as independent sorted arrays

Video Solution

BS-25. Search in a 2D Matrix - II | Binary Search on 2D • take U forward • 205,819 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Search a 2D Matrix II easy or hard?
Search a 2D Matrix II is generally classified as a medium difficulty problem. The challenge is recognizing that the sorted rows and columns allow elimination of entire rows or columns, leading to the O(m + n) traversal strategy.
How to solve Search a 2D Matrix II in O(m+n)?
Start from the top-right element of the matrix. Compare it with the target. If it is larger, move one column left; if smaller, move one row down. Because rows increase left to right and columns increase top to bottom, each move removes an entire row or column from the search space.
Search a 2D Matrix II Python or Java solution?
In Python or Java, the most common solution initializes two indices at the top-right corner of the matrix. A loop moves left or down based on comparisons with the target until the element is found or the indices move outside the matrix bounds.
What is the best approach for Search a 2D Matrix II?
The optimal approach starts from the top-right corner of the matrix and eliminates one row or one column after each comparison. If the current value is larger than the target, move left; if smaller, move down. This strategy runs in O(m + n) time and O(1) space, making it the most efficient solution for this problem.
What data structure is used in Search a 2D Matrix II?
The core data structure is a 2D matrix (grid) implemented as a 2D array. The algorithm relies on the sorted property of rows and columns and uses pointer-style traversal or binary search to efficiently locate the target.
What is the time complexity of Search a 2D Matrix II?
The optimal solution runs in O(m + n) time where m is the number of rows and n is the number of columns. Each step discards either a row or a column, so you perform at most m + n comparisons. Space complexity is O(1) because the algorithm only uses a few index variables.
Is Search a 2D Matrix II asked at Google, Amazon, or Meta?
Search a 2D Matrix II is a common interview problem at large tech companies including Google, Amazon, and Meta. It tests understanding of matrix traversal, monotonic ordering, and the ability to reduce search space efficiently without scanning the entire grid.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Search a 2D Matrix