In the Leetcode Search a 2D Matrix problem solution You are given an m x n integer matrix matrix with the following two properties:
Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if target is in matrix or false otherwise.
You must write a solution in O(log(m * n)) time complexity.
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Constraints:
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -104 <= matrix[i][j], target <= 104
Solution in C Programming
bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
if(matrixSize == 0) {
return false;
}
int left = 0;
int right = matrixSize * (*matrixColSize) - 1;
while(left <= right) {
int mid = (left + right) / 2;
int element = matrix[mid/(*matrixColSize)][mid % (*matrixColSize)];
if(target == element) {
return true;
} else {
if(target < element) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
return false;
}Solution in C++ Programming
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m=matrix.size();
int n=matrix[0].size();
int x=0;
int y=n-1;
int temp;
while(x<m && y>=0){
temp=matrix[x][y];
if(temp==target)return 1;
if(temp>target)y--;
else{
x++;
}
}
return 0;
}
};Solution in Java Programming
class Solution {
//time:o(m + n) space:o(1)
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return false;
int row = matrix.length - 1;
int col = 0;
while(row >= 0 && col < matrix[0].length){
if(matrix[row][col] == target) return true;
if(matrix[row][col] < target){
col++;
}else{
row--;
}
}
return false;
}
}Solution in Python Programming
class MatrixFlatWrapper:
def __init__(self, m):
R, self.C = len(m), len(m[0])
self.len = R * self.C
self.m = m
def __len__(self):
return self.len
def __getitem__(self, index):
r, c = divmod(index, self.C)
return self.m[r][c]
class Solution:
def searchMatrix(self, m, target):
m = MatrixFlatWrapper(m)
N = len(m)
i = bisect_left(m, target)
return i < N and m[i] == targetSolution in C# Programming
public class Solution {
public bool SearchMatrix(int[][] matrix, int target) {
int rows = matrix.Length;
int cols = matrix[0].Length;
int l = 0;
int r = rows*cols - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
int val = matrix[mid / cols][mid % cols];
if (val < target)
l = mid + 1;
else if (val > target)
r = mid - 1;
else
return true;
}
return false;
}
}Also read,