Leetcode 0240 Search 2d Matrix Ii
Meta Data
Link
Tags
Similar
- Other solutions at Leetcode-0074-search-2D-matix
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
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
Solution Approaches
O(N * M) Brute Force Linear Search
- Implement a simple Linear Search Algorithm for matrix
O(N * Log(M)) Binary Search Row Wise
- As rows are sorted perform Binary Search Algorithm on each
- If
target
is not found at the end of search then move to the next row - Time for binary search is
log M
which is applied onN rows
soO(N * Log(M))
in total.
O(N+M) Top Right Approach
- Link
- 21 Search in Row wise And Column wise Sorted Array - YouTube by [[ Aditya Verma ]]
- Using Row Wise Column Wise Sorted Property
- For any element
a[i][j]
the following is true- Elements towards left are always smaller
a[0][j] a[1][j] ... a[i-1][j] < a[i][j]
- Elements towards down are always bigger
a[i][j+1] a[i][j+2] ... a[i][m] > a[i][j]
- Elements towards left are always smaller
- This makes the property applicable for Binary Search Algorithm type implementation
- Starting from Top Left we can move in two directions
down to get larger and left to get smaller
- For any element
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size() - 1;
int n = matrix[0].size() - 1;
int i = 0;
int j = n;
while (i <= m and j >= 0) {
if (matrix[i][j] == target) {return true;}
else if (matrix[i][j] < target) {i++;}
else {j--;}
}
return false;
}
Return to DSA