You have been given a 2-D array 'mat' of size 'M x N' where 'M' and 'N' denote the number of rows and columns, respectively. The elements of each row are sorted in non-decreasing order.
Moreover, the first element of a row is greater than the last element of the previous row (if it exists).
You are given an integer ‘target’, and your task is to find if it exists in the given 'mat' or not.
Input: ‘M’ = 3, 'N' = 4, ‘mat’ = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]], ‘target’ = 8
Output: true
Explanation: The output should be true as '8' exists in the matrix.
The first line contains three space-separated integers 'M', 'N', and ‘target’ where 'M' and 'N' denote the number of rows and columns of the 'mat', respectively, and ‘target’ is the integer to be found.
From the second line, the next 'M' lines represent the rows of the 'mat'. Every row contains 'N' single space-separated integers.
Return 'true' if ‘target’ is present in the 'mat'; else, return 'false'.
You do not need to print anything. It has already been taken care of. Just implement the function.
Can you solve this problem in less than O(M*N) time complexity?
3 4 8
1 2 3 4
5 6 7 8
9 10 11 12
true
The ‘target’ = 8 exists in the 'mat' at index (1, 3).
3 3 78
1 2 4
6 7 8
9 10 34
false
The ‘target' = 78 does not exist in the 'mat'. Therefore in the output, we see 'false'.
1 <= N <= 50
1 <= M <= 50
-10^5 <= mat[i], target <= 10^5
Time Limit: 1 sec
Naively search the MAT to find the TARGET.
We have a brute force solution to this problem. We can simply traverse the matrix and check if ‘TARGET’ exists or not.
O(M*N) where ‘M’ and ‘N’ denote the number of rows and columns in ‘MAT’, respectively.
In the worst case, we will be traversing the entire matrix of M*N elements.
O(1)
Since, we are not using any extra space to find the number of pairs. Therefore, the overall space complexity will be O(1).
All tags
Sort by
Interview problems
Easy java solution
import java.util.ArrayList;
public class Solution {
static boolean searchMatrix(ArrayList<ArrayList<Integer>> mat, int target) {
// Write your code here.
int n=mat.size();
int m=mat.get(0).size();
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(mat.get(i).get(j)==target){
return true;
}
}
}
return false;
}
}
Interview problems
Clear Concept | Reduces RunTime | C++
bool searchMatrix(vector<vector<int>>& mat, int target) {
int m = mat.size();
for(int i = 0; i < m; i++)
{
int n = mat[i].size();
if(mat[i][0]>target || mat[i][n-1] < target)
continue;
int low = 0, high =n-1;
while(low <= high)
{
int mid = (high+low)/2;
if(mat[i][mid]==target)
return true;
else if(mat[i][mid]< target)
low = mid+1;
else
high = mid - 1;
}
}
return false;
}Interview problems
JAVA || All Test Cases Passed || Easy Code
import java.util.ArrayList;
public class Solution {
static boolean searchMatrix(ArrayList<ArrayList<Integer>> mat, int target) {
// Write your code here.
for(int i=0;i<mat.size();i++){
int len =mat.get(0).size();
for(int j =0;j<len;j++){
if(mat.get(i).get(0) > target){
return false;
}
if(mat.get(i).get(0)<=target && mat.get(i).get(len-1)>=target ){
if(mat.get(i).get(j) == target){
return true;
}
}
}
}
return false;
}
}
Interview problems
Find element in 2D matrix. (Python using numpy)
import numpy as np
def searchMatrix(mat: [[int]], target: int) -> bool:
a=np.array(mat)
b=a.reshape
if target in a:
return True
else:
return False
Interview problems
JAVA SOLUTION || Search In A 2D Matrix ||
import java.util.ArrayList;
public class Solution {
static boolean searchMatrix(ArrayList<ArrayList<Integer>> mat, int target) {
for(ArrayList<Integer> arr :mat)
if(arr.get(arr.size()-1)>= target)
{
int j=0;
while(j<arr.size())
{
if(arr.get(j) == target)
{
return true;
}
j++;
}
}
}
return false;
}
}
Interview problems
Detailed code for this.
bool searchMatrix(vector<vector<int>>& mat, int target) {
int n = mat.size(); //declare the size
int m = mat[0].size(); //declare the martix size
int low = 0; int high = n*m-1; //low = 0 and n[col], m[row] -1
while(low <= high){
int mid = (low+high) /2; //hypothetically write in an 1d array and formulate this
int row = mid/m; // mid and row
int col = mid % m; //mid mod row
if(mat[row] [col] == target) return true; //if it finds
else if (mat[row] [col] < target) low = mid +1; // if find right side
else high = mid -1; // if find left side
}
return false; // if found nothing
}
Interview problems
Easiest Binary Search Approach
bool searchMatrix(vector<vector<int>>& mat, int target) {
int n = mat.size();
int m = mat[0].size();
int low = 0;
int high = (n * m) - 1;
while(low <= high) {
int mid = (low + high) / 2;
int row = mid / m;
int column = mid % m;
if(mat[row][column] == target) return true;
else if(mat[row][column] < target) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
return false;
}
// Time Complexity = O(Log(N * M))
// Space Complexity = O(1)
Interview problems
C++ Code with Binary Search Solution ........... T.C = O(log (N*M))
bool searchMatrix(vector<vector<int>>& mat, int target) {
int m = mat.size(); // number of rows
int n = mat[0].size(); // number of columns
int low = 0;
int high = (m*n -1);
while(low<=high){
int mid = (low+high)/2 ;
int row = mid/n;
int col = mid%n;
if(mat[row][col] == target) return true;
else if (mat[row][col] > target) high = mid-1;
else low = mid+1;
}
return false;
}Interview problems
Using Binary Search | O( mlogn )
bool search_row(vector<int> &nums, int t)
{
int i = 0, j = nums.size()-1;
int mid = (i+j)/2;
while(i <= j)
{
if(t < nums[mid])
{
j = mid-1;
mid = (i+j)/2;
}
else if(t > nums[mid])
{
i = mid+1;
mid = (i+j)/2;
}
else
return true;
}
return false;
}
bool searchMatrix(vector<vector<int>>& mat, int target) {
for(int i = 0; i<mat.size(); i++)
{
if(search_row(mat[i], target))
return true;
}
return false;
}Interview problems
C++ easy solution || binary search , beats 99.06% users
bool searchMatrix(vector<vector<int>>& mat, int target) {
int row=mat.size();
int col=mat[0].size();
int s=0;
int e=row*col-1;
int mid=s+(e-s)/2;
while(s<=e){
if(mat[mid/col][mid%col]==target){
return true;
}
else if(mat[mid/col][mid%col]<target){
s=mid+1;
}
else{
e=mid-1;
}
mid=s+(e-s)/2;
}
return false;
}
