Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
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.lengthn == matrix[i].length1 <= n, m <= 300-109 <= matrix[i][j] <= 109-109 <= target <= 109Problem 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.
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.
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.
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.
Time Complexity: O(m * log(n)), where m is the number of rows and n is the number of columns.
Space Complexity: O(1).
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).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
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:
matrix[i][j] = target, it means the target value is found, and we return true.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.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).
| Approach | Complexity |
|---|---|
| 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. |
| 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. |
| Binary Search | — |
| Search from Bottom-Left or Top-Right | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Top-Right Corner Traversal | O(m + n) | O(1) | Best general solution when rows and columns are both sorted |
| Binary Search in Each Row | O(m log n) | O(1) | Useful when treating rows as independent sorted arrays |
Search a 2D Matrix II | Live Coding with Explanation | Leetcode - 240 • Algorithms Made Easy • 15,671 views views
Watch 9 more video solutions →Practice Search a 2D Matrix II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor