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 <= 109This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * log(n)), where m is the number of rows and n is the number of columns.
Space Complexity: 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. |
Search a 2D Matrix - Leetcode 74 - Python • NeetCode • 206,302 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