# Leetcode Search a 2D Matrix problem solution

Apr 22, 2023

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] == target``````

## Solution 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;
}
}``````

#### By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.