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 <= 109In #240 Search a 2D Matrix II, each row and each column of the matrix is sorted in ascending order. A brute force scan would take O(m*n), but the sorted structure allows more efficient strategies.
The most common technique is the staircase search. Start from the top-right (or bottom-left) corner of the matrix. At this position, you can eliminate either a row or a column with each comparison. If the current value is greater than the target, move left to reduce the value. If it is smaller, move down to increase the value. This gradually narrows the search space without checking every element.
Another possible idea is applying binary search on each row or column since they are individually sorted, though this is usually less optimal. The staircase method achieves O(m + n) time with constant extra space, making it the preferred approach for large matrices.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Staircase Search (Top-Right Traversal) | O(m + n) | O(1) |
| Binary Search on Each Row | O(m log n) | O(1) |
NeetCode
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.
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.
1#include <stdbool.h>
2
3bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
4 int row = 0The 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.
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.
Time Complexity: O(m * log(n)), where m is the number of rows and n is the number of columns.
Space Complexity: O(1).
1public class Solution {
2 private bool BinarySearch(int[] array, int target) {
int left = 0, right = array.Length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) return true;
else if (array[mid] < target) left = mid + 1;
else right = mid - 1;
}
return false;
}
public bool SearchMatrix(int[][] matrix, int target) {
foreach (var row in matrix) {
if (BinarySearch(row, target)) return true;
}
return false;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or its variations frequently appear in FAANG and other top tech company interviews. Interviewers use it to evaluate matrix traversal strategies, search optimization, and the ability to leverage sorted properties in multidimensional data.
Yes, binary search can be applied to each row or column individually because they are sorted. However, this leads to O(m log n) or O(n log m) time, which is generally slower than the O(m + n) staircase search approach.
The problem primarily uses a 2D array (matrix). The key idea is not changing the data structure but exploiting the sorted property of rows and columns to efficiently eliminate parts of the search space.
The optimal approach is the staircase search technique. Start from the top-right corner and move left or down depending on the comparison with the target. This works because rows and columns are sorted, giving a time complexity of O(m + n).
C# implementation employs a helper method `BinarySearch` to manage orderly checking of each row for the target using binary search. It utilizes C#'s syntax for array manipulation and traversal.