You are given a 2-D matrix with 'N' rows and 'M' columns, each row of the matrix is sorted in non-decreasing order and the first element of each row is greater than or equal to the last element of the previous row. You are also given an integer ‘X’, you are supposed to find whether 'X' is present in the given matrix or not.
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows.
The first line of each test case contains three integers ‘X’, ‘N’ and ‘M’ separated by a single space denoting the element to be searched, the number of rows in the matrix, and the number of columns in the matrix respectively.
The next ‘N’ lines contain ‘M’ integers each denoting the elements of the matrix.
For each test case, print “Yes”(without quotes) if ‘X’ is present in the matrix otherwise print “No”.
Print the output of each test case on a new line.
You don’t need to print anything; It has already been taken care of.
1 <= T <= 50
1 <= X <= 10 ^ 6
1 <= N, M <= 100
-10 ^ 6 <= ARR[i][j] <= 10 ^ 6
Where ‘T’ denotes the number of test cases, ‘N’ denotes the number of rows in a matrix, ‘M’ denotes the number of columns in the matrix and ARR[i][j] denotes the j-th element of the i’th row of the given matrix.
Time Limit: 1 sec
2
4 2 2
2 4
8 12
7 3 4
1 2 4 5
8 12 14 16
23 25 26 29
Yes
No
In the first test case, the 2nd element of the first row is equal to 4, hence the output is “Yes”.
In the second test case, 7 is not present in the matrix hence the output is “No”.
2
2 1 1
2
22 3 2
3 4
11 17
23 27
Yes
No
In the first test case, the only element is equal to 2, hence the output is “Yes”.
In the second test case, 22 is not present in the matrix hence the output is “No”.
Can you try to iterate through the matrix?
The idea is to iterate through the matrix and check if any element is equal to ‘X’.
The steps are as follows :
O(N*M), where ‘N’ is the number of rows and ‘M’ is the number of columns in the matrix.
We are iterating through the matrix which has ‘N’ rows and each row has ‘M’ elements, thus the total elements are N*M. Thus, the overall time complexity is O(N*M).
O(1).
We are using constant space. Thus, the overall space complexity is O(1).
All tags
Sort by
Interview problems
C++ || beat 100% || Easy code
#include <bits/stdc++.h>
bool findInMatrix(int x, vector<vector<int>> &arr)
{
int row = arr.size();
int col = arr[0].size();
int start = 0;
int end = row*col-1;
int mid = start + (end - start)/2;
while(start <= end ){
int element = arr[mid/col][mid%col];
if(element == x){
return 1;
}
if(element < x){
start = mid +1;
}
else {
end = mid-1;
}
mid = start + (end - start)/2;
}
return 0;
}
Interview problems
Binary search Method
#include <bits/stdc++.h>
bool findInMatrix(int target, std::vector<std::vector<int>> &matrix) {
int numRows = matrix.size();
int numCols = matrix[0].size();
int left = 0, right = numRows * numCols - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int midCol = mid % numCols;
int midRow = mid / numCols;
int midVal = matrix[midRow][midCol];
if (midVal == target) {
return true;
}
if (midVal < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
Interview problems
C++ Search in a 2D matrix - 3 approachs
#include <bits/stdc++.h>
bool findInMatrix(int x, vector<vector<int>> &arr)
{
//Write your code here
// 1st approach - Binary search
int row=0;
int col= arr[row].size() -1;
while(row < arr.size() && col >= 0){
if(arr[row][col]== x){
return true;
}
if(arr[row][col]< x){
row++;
}
else{
col--;
}
}
return false;
// 2nd approach - Improved Binary search
int row = arr.size();
int col= arr[0].size();
int l=0,h=row*col -1;
while(l<=h){
int mid = l+(h-l)/2;
int tC= mid % col;
int tR= mid/col;
int val = arr[tR][tC];
if(val==x){
return true;
}
if(val<x){
l=mid+1;
}
else{
h=mid-1;
}
}
return false;
// 3rd approach - Linear Search
for(int i=0;i<arr.size();i++){
for(int j=0;j<arr[i].size();j++){
if(arr[i][j]==x){
return true;
}
}
}
return false;
}
Interview problems
C++ simple iterative
#include <bits/stdc++.h>
bool findInMatrix(int x, vector<vector<int>> &arr)
{
int n=arr.size(),m=arr[0].size();
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(arr[i][j]==x)
return true;
}
}
return false;
}
Interview problems
C++ Solution
#include <bits/stdc++.h>
bool findInMatrix(int x, vector<vector<int>> &arr)
{
int i = arr.size()-1;
int j = 0;
while(i>=0 && j<arr[0].size()){
if(arr[i][j] == x){
return true;
}
else if(arr[i][j] < x){
j++;
}
else{
i--;
}
}
return false;
}
Interview problems
Binary Search Solution to apply in each row!!
#include <bits/stdc++.h>
bool findInMatrix(int x, vector<vector<int>> &arr) {
for (int i = 0; i < arr.size(); i++) {
int low = 0, high = arr[0].size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[i][mid] == x)
return true;
else if (arr[i][mid] < x)
low = mid + 1;
else
high = mid - 1;
}
}
return false;
}Interview problems
Beats 91% using Binary Search
#include <bits/stdc++.h>
bool findInMatrix(int x, vector<vector<int>> &arr)
{
int res;
for(vector<int>temp : arr){
int low = 0 , high=temp.size()-1;
if(temp[high] <x || temp[low] > x){
continue;
}
else{
while(low<=high){
int mid = low+(high-low)/2;
if(temp[mid] == x){
return true;
}
else if(temp[mid] < x){
low= mid+1;
}
else{
high=mid-1;
}
}
}
}
return false;
}
Interview problems
Intuition Explained ✅ | Beginner Friendly | Approaches Explained 👌 | Beats 94%
Intuition : We can solve the question in 1 of 3 ways :
Approach 1 of using linear Search is pretty much obvious for anyone to solve on their own.
Approach 2:
Approach 3: On carefully analyzing, we can observe that, the whole matrix is sorted, so if we convert the whole matrix into 1D array, giving each element the index from 0 to (n*m) - 1. We will be having the sorted 1D array.
But we won't convert it actually, we will simply assume that each element has index from 0 to (n*m) - 1.
Now if we want to calculate the rowIndex and colIndex for 6th element or index = 5, we just need to reduce the matrix problem into 1D array by asking two questions:
To calculate rowIndex, colIndex of index = 5 or element no. 6th in 1D Array):
So our index 5 or element no. 6th in 1D Array will be on [1][1] index in matrix.
Now we have the way to get rowIndex and colIndex of any element present in our imaginary 1D array. So, we all are smart enought to put binary search to use, to get the search done for target Element.
Interview problems
Binary search for 2D ARRAY Java
import java.util.ArrayList;
public class Solution {
public static boolean findInMatrix(int x, ArrayList<ArrayList<Integer>> arr) {
int totalRows = arr.size();
int totalColumns = arr.get(0).size();
int low = 0;
int high = totalRows * totalColumns - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int midRow = mid / totalColumns;
int midCol = mid % totalColumns;
int midValue = arr.get(midRow).get(midCol);
if (midValue == x) {
return true;
} else if (midValue < x) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return false;
}
}
Interview problems
Optimized Solution : Apporach : Binary search
bool findInMatrix(int x, vector<vector<int>> &arr)
{
int row=arr.size();
int col=arr[0].size();
int start=0;
int end=(row*col)-1;
while(start<=end){
int mid=start+(end-start)/2;
int element=arr[mid/col][mid%col];
if(element==x){
return 1;
}
if(element<x){
start=mid+1;
}
else{
end=mid-1;
}
}
return 0;
}
