Bhai this is amazing, 4 minutes into the video and I was able to solve the problem all by myself. I learned something new today. Thanks Aditya. One more thing, at 15:31 we don't actually need to check for (i >= 0) and (j
Finally completed this playlist sequentially with practice problema on gfg and codeforces. Waiting for next playlist on backtracking. Please upload them soon. Thanks for such loaded content videos. Helping a lot for internship preparations.
I loved the way how you explained this approach by relating it to the method of binary search. Previously, I was not able to understand why are we starting from top-right corner, but now it is making sense while relating it to binary search! Thank you so much! ❤️
Thank you so much brother for such an step by step learning approach..This was the thing I was looking on the internet, from months and Thank god! finally found your channel. Your way of teaching is incredible..especially when you build the concepts gradually and then the topic and problems based on it becomes so easy to understand & apply for us..Hope you make same playlist for [Tree,Graph,Backtracking,Recursion], It will really help students like me to get such a structured learning right from basic to advance in one playlist on this particular topics mentioned. Its a genuine request to make it as soon as possible because on internet information is available on each topics but it is in scattered way(no proper way of concept building is available).Hope you can understand our feelings and from your busy schedule you can devote some time & make a complete end to end playlist on the above mentioned topics.
what i suggest is since our matrix is sorted in both ways(row and col). element at array[0][0] will be smallest and array[n-1][m-1] will be largest . So before going into loop we can check if keyarray[n-1][m-1] return -1; After doing this you can also change your while condition to while(j>=0 && i
I started this question on my own before watching the solution, what I did was applied binary search on each column starting from top right corner to find the key. I thought I got a really good solution but then I saw your solution. Great approach!
genrally if video length is grater than 20 min most people tend to skip some of the part but while watching your and striver content it is totally opposite really superb
Amazing playlist man, just one suggestion for this solution, it d be better if we use the floor function on j to determine the column to enter into and subsequently use the ceil for traversing the row, that way it actually becomes a question of binary search
@Aditya Verma, please make video on "Median of 2 sorted arrays of different lengths using O(1) space", based on some videos it seems like Binary Search can be applied
If the array would have been sorted only row wise and also the last element of the previous row must be less than the first element of the current row then the thought process could have been better. We could have searched the first column first. If we found the key in that column then we could return it straight but if not then we could have first found the floor of the key in the first column and then in that row we could have again applied binary search to find the element. This would have used the concept of both finding the floor and binary search. The worst case time complexity of this solution would be (log n + log m) where n is the number of rows and m is the number of columns
Java code: static boolean search(int matrix[][], int n, int m, int x) { int row = 0; int col = m-1; while(row < n && col > -1) { if(matrix[row][col] == x) return true; else if(matrix[row][col] < x) row++; else col--; } return false; }
There could be 2 kinds of sorted 2d arrays. The one which is mentioned in the video there could not be any better approach than the approach which is being told in the video i.e staircase search. arr = {{10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50}}; Here array is sorted and but there is different kind of sorted arrays with a condition that the first integer of each row is greater than the last integer of the previous row. This you will find in question 74 2D matrix Leetcode. Here you can apply binary search on row and col and can reduce the time complexity to O (log n * log m) matrix = [[1,3,5,7], [10,11,16,20], [23,30,34,60] ] We can apply binary search to matrix but not to arr. for arr we will use staircase search which gives time complexity O(n + m)
Or You can store the whole matrix in a separate array and find the element using binary search and find row and col my doing mod with number of rows and col respectively. Time : log( m * n ) as we are finding our ele in the whole matrix just stored in a single 1d array. ** We can also directly access the matrix by using mod and it will decrease the space to O(1)
This can be done in O(log(m*n)). It is basically an array with m*n elements (divided into m rows). So binary search on this array. for any mid the element to compare is matrix[mid/n][mid%n]. And O(log(m*n)) is O(log(m)+log(n)) which is lesser than O(m+n).
GFG Accepted code: int search(int **arr, int n, int m, int k) { int i = 0; int j = m - 1; while (i >= 0 && i < n && j >= 0 && j < m) { if (arr[i][j] == k) { // pair p(i, j); // return p; // above two steps were for returning if questions demands pair of indexes. // here, we only need if present or not, so return 1 as follows: return 1; } else if (k < arr[i][j]) j--; else if (k > arr[i][j]) i++; } return 0; }
This approach is good but i have one more approach for this problem => treating the 2D matrix as 1D only :- we have to just find out its equivalent row and column and formula for same is row = mid/m; column = mid % m ; code is :- class Solution { public: bool searchMatrix(vector& M, int target) {
int n = M.size(); int m = M[0].size(); int low = 0; int high = m*n - 1; while(lowtarget) { high = mid -1; } else low = mid +1; } return 0;
Applying binary search on every row is also an intuitive approach that can bring down the time complexity to O(nlog(m)). And thanks bhaiya for all the videos.
@@revaanmishra can't we use binary search to find row first then the same method to find appropriate column number .so will complexity reduce to max(logn,logm)?
Intuition This problem will purely be solved on the core principles of how a 2D matrix works,its traversal and a few comparisons. Approach We assign i=0 and j=n-1, means i is at start of the row and j is present at the start of the last column. We start comparing from j=n-1. Basically,the comparison is starting from the last element of the first row. Now,if observed closely, the last element of the first row, moving downwards from there will always result in a greater value as the 2D Matrix happens to be sorted. If target is smaller, there is no point moving down. Hence, we decrement j and move to the previous column. We check again, if target is still smaller (matrix[i][j]>target) we decrement j again. observe one thing. As we move from the extreme right to left, we notice that values are eventually decreasing for the ith row. So we are bound to reach a point, where matrix[i][j] has a smaller value than target. If so, we now increment i and move to the row below,which gets us closer to the target. Finally we reach a point where we find the target. Complexity Time complexity: O(m+n) Space complexity: O(1) Code class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length; // row int n = matrix[0].length; // col int i = 0; int j = n - 1; while (i >= 0 && i < m && j >= 0 && j < n) { if (matrix[i][j] == target) { return true; } else if (matrix[i][j] > target) { j--; } else if (matrix[i][j] < target) { i++; } } return false; } }
Just wanted to ask , can't we apply binary search here . We'll start from arr[mid_row][mid_col] and then first check between which two columns does our element lie and then similarly which two row , finally arriving at the element , this way the time complexity would be log(n)*log(m)?
can we use the bottom left corner also I guess in this case it will give solution more quickly and what we are doing for columns we can do the same for rows also! I think it will be same pls correct me if I am wrong thanks☺️
One solution that came to my mind is: A.) First find the floor value index of the key in first row using binary search(time complexity will be O(log n)).Here index will be 1(20 is present). B.) Then once again apply binary search on that particular column. can we the problem this way???
I think its a little better solution and better way for implementing binary search int m = matrix.size(); int n = matrix[0].size(); int low = 0; int high = n-1; int row = 0; while(low
We can use binary search on this: when u are in a particular column, find the floor of the target --> this becomes the new column when u are in a particular row, find the ceiling of the target --> this becomes the new row
@@rishabsoni256 thnx buddy but I need one more help. If you have watched Aditya's DP video of min coin change problem then can you share your code for top down approach, cause I m terribly stuck at creating a large 2d global array of variable size depending upon user inputs.
we can further reduce the time complexity by using a binary search in every row and column. We'll now have a code which will run in O(log(n) + log(m)).
My Solution: Leetcode (74): class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: n_rows = len(matrix) if n_rows == 0: return False n_cols = len(matrix[0])
i = 0 j = n_cols - 1 while(i >=0 and i < n_rows and j >=0 and j < n_cols): if matrix[i][j] == target: return True elif matrix[i][j] > target: # no need to search downwards; search leftwards j -= 1 else: # no need to search leftwards; search down this column itself i += 1 return False
Since we are searching in sorted array to jo ham linear search karte hain, uski jagah binary bhi to implement kr skte. For example while moving left, we just need to find Floor(X) and while moving down, we have to find Ceil(X). Isse Time Complexity kaafi kam ho jayegi. Am I right?
You can also solve this question using binary search :-)) Time : O(log n + log m) Space : O(1) Explanation and Code:- Observe the matrix and you will notice that all rows and columns are sorted. Now, we can apply binary search on the first column of the matrix and check if it contains the target. If it does, then return true. If not, the binary search will end with high pointing towards the element just smaller than target. This is not a conincidence!! Try dry running binary search on an array for an element which is not present in the array. You will always observe that the binary search will end with high pointing towards the element just smaller than the target. We will use this to our advantage! By now you would have understood what to do next :-)). Now as you have found the element just smaller than target; you are now on the right row, as this row will contain elements greater than on its right hand side. Now, apply binary search on this row and you will find the target. If none of that happens, return false as the target never existed in the matrix. The below code is just a search code, but you can modify a bit and use the same to return indices of the target as well. bool searchMatrix(vector& mat, int target) { int lo=0, hi=mat.size()-1; int mid;
while(lotarget) hi=mid-1; else lo=mid+1; }
if(hi==-1) // Edge case if hi goes out of bound. return false;
int row=hi; lo=0, hi=mat[0].size()-1;
while(lotarget) hi=mid-1; else lo=mid+1; } return false; } You can also think of first applying binary search on the first row, find the appropriate column and then apply it again on that column :-)). Like to let more people know about this and aditya to pin this comment :).
but sir why did we started the searching of the element in the matrix from top right corner why not top left or bottom left/right ? any specific reason ??
Bhai this is amazing, 4 minutes into the video and I was able to solve the problem all by myself. I learned something new today. Thanks Aditya.
One more thing, at 15:31 we don't actually need to check for (i >= 0) and (j
Finally completed this playlist sequentially with practice problema on gfg and codeforces.
Waiting for next playlist on backtracking.
Please upload them soon.
Thanks for such loaded content videos.
Helping a lot for internship preparations.
1 left
lagi kya bhai internship
Bhai lagi thi k nhi internship? sahi sahi batana .....tbhi last wala video dekhnge
@@danishraza3061 🤣
Waiting for next playlist on Backtracking... Never gonna happen! Sadly.
every second is worth to spend watching Aditya Verma content :).
Absolutely true....his way of explanation is just way too awesome🔥
Absolutely 🔥
Only thing I'm disappointed is that backtracking video's are not yet uploaded 🥺😭😭😭
Hi Aditya, I was struggling with DSA and RUclips recommended me your channel, thanks a lot to you and RUclips for such a quality content
I loved the way how you explained this approach by relating it to the method of binary search. Previously, I was not able to understand why are we starting from top-right corner, but now it is making sense while relating it to binary search!
Thank you so much! ❤️
Thank you so much brother for such an step by step learning approach..This was the thing I was looking on the internet, from months and Thank god! finally found your channel. Your way of teaching is incredible..especially when you build the concepts gradually and then the topic and problems based on it becomes so easy to understand & apply for us..Hope you make same playlist for [Tree,Graph,Backtracking,Recursion], It will really help students like me to get such a structured learning right from basic to advance in one playlist on this particular topics mentioned. Its a genuine request to make it as soon as possible because on internet information is available on each topics but it is in scattered way(no proper way of concept building is available).Hope you can understand our feelings and from your busy schedule you can devote some time & make a complete end to end playlist on the above mentioned topics.
what i suggest is since our matrix is sorted in both ways(row and col). element at array[0][0] will be smallest and array[n-1][m-1] will be largest . So before going into loop we can check if keyarray[n-1][m-1] return -1; After doing this you can also change your while condition to while(j>=0 && i
Yeah checking first arr[0][0]>tar || arr[n-1][m-1]=0 && r
Awesome! Please take up recursion/backtracking next.
Also checking for while(i=0) will suffice.
true
i guess that's because we're never doing i-- or j++
i is going down only and j is going left only
Yeah
I started this question on my own before watching the solution, what I did was applied binary search on each column starting from top right corner to find the key. I thought I got a really good solution but then I saw your solution. Great approach!
The explanation was awesome. It would be really helpful if you upload a video on finding median in a row wise sorted matrix without using extra space.
I was asked this question in PayPal interview for SDE-1 when I was at college. Well explained.
Now in which company you're??
genrally if video length is grater than 20 min most people tend to skip some of the part but while watching your and striver content it is totally opposite really superb
Amazing playlist man, just one suggestion for this solution, it d be better if we use the floor function on j to determine the column to enter into and subsequently use the ceil for traversing the row, that way it actually becomes a question of binary search
gone through the whole playlist this is pure gold, thanks Aditya for taking the effort
Moreover, we can shorten the bounds for while loop i.e while ( i=0 )
As we know i always increase & j always decrease
But, vice versa is not 🚫
hands down one of the best approach ive ever seen
Amazing, Wonderful explanation.
woow bhiya aap pen ghumake concept clear kr dete ho
love you!
thanku
kafi maja ara h 2 pointer sliding window tree etc pr bhi banao videos pen ghumake
The way you explain the solution is awesome👍
Thank you Adithya Verma...
@Aditya Verma, please make video on "Median of 2 sorted arrays of different lengths using O(1) space", based on some videos it seems like Binary Search can be applied
This is what you need : ruclips.net/video/uPqPDPjtPX4/видео.html
loved the way you explained❤
I never get bored by watching your videos ❤
Bhai .. ek no. Explanation.. watched your video for the first time , ab se aapka hi vdo dekhna h 🤟🤟😇
very well explained with code great work
this is the best video on this topic. thanks sir
Most optimal for this problem is using binary search with time complexity O( log(m ) + log (n) )
Bht sahi hai yr bhai..tester ko bhi coding sikha diye
Best playlist for bs. Thanks.
I finally understood this one! Great explanation..Thank you :)
Thank you Bhaiya !
Keep it up !
You are helping a lot of people ... may god bless you !
Thanks, sir. Your way of explanation is truly awesome.
very well explained! thank you for uploading these content.
bahut achi approach, maza aya dekhne me.
If the array would have been sorted only row wise and also the last element of the previous row must be less than the first element of the current row then the thought process could have been better.
We could have searched the first column first. If we found the key in that column then we could return it straight but if not then we could have first found the floor of the key in the first column and then in that row we could have again applied binary search to find the element. This would have used the concept of both finding the floor and binary search. The worst case time complexity of this solution would be (log n + log m) where n is the number of rows and m is the number of columns
Bhaiya, please make videos on string algorithms (advanced ones)
Java code:
static boolean search(int matrix[][], int n, int m, int x)
{
int row = 0;
int col = m-1;
while(row < n && col > -1)
{
if(matrix[row][col] == x)
return true;
else if(matrix[row][col] < x)
row++;
else
col--;
}
return false;
}
Please upload a playlist on Backtracking as soon as possible!
very nice explanation
Nice explanation sir....thanks for the playlist
finding coding easy through ur lectures .
There could be 2 kinds of sorted 2d arrays. The one which is mentioned in the video there could not be any better approach than the approach which is being told in the video i.e staircase search.
arr = {{10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};
Here array is sorted and but there is different kind of sorted arrays with a condition that the first integer of each row is greater than the last integer of the previous row. This you will find in question 74 2D matrix Leetcode.
Here you can apply binary search on row and col and can reduce the time complexity to O (log n * log m)
matrix = [[1,3,5,7],
[10,11,16,20],
[23,30,34,60] ]
We can apply binary search to matrix but not to arr. for arr we will use staircase search which gives time complexity O(n + m)
Or You can store the whole matrix in a separate array and find the element using binary search and find row and col my doing mod with number of rows and col respectively.
Time : log( m * n )
as we are finding our ele in the whole matrix just stored in a single 1d array.
** We can also directly access the matrix by using mod and it will decrease the space to O(1)
Thank you bhaiya very easy explanation
bhai maja aa gaya yaar Aditya pls make more playlist like these
0:01 what an intro bruhhh :)
Really like your way of teaching. Can you please make a playlist for time and space complexity?
Watch this for time complexity analysis ruclips.net/video/oPvT1IBXNxM/видео.html
bas explanation hi enough hai sir aapka 😏😍.. code toh hum 80% apki explanation se kr dete hai... ❤
Thank u bhaiya😌👐,
Thanks you for watching brother !!
This can be done in O(log(m*n)). It is basically an array with m*n elements (divided into m rows). So binary search on this array. for any mid the element to compare is matrix[mid/n][mid%n]. And O(log(m*n)) is O(log(m)+log(n)) which is lesser than O(m+n).
nope ! thats a different version of this problem which guarantees first element of a row is always greater than the last element of the previous row.
Thanks aditya bhai
thanks bhaiya ....!
no word for u....u are really amazing and very helpfull ....!
Worthy! content literally 🔥
GFG Accepted code:
int search(int **arr, int n, int m, int k)
{
int i = 0;
int j = m - 1;
while (i >= 0 && i < n && j >= 0 && j < m)
{
if (arr[i][j] == k)
{
// pair p(i, j);
// return p;
// above two steps were for returning if questions demands pair of indexes.
// here, we only need if present or not, so return 1 as follows:
return 1;
}
else if (k < arr[i][j])
j--;
else if (k > arr[i][j])
i++;
}
return 0;
}
Nice Explaination
Gawddd level teacher 🔥🔥🔥🔥🔥🔥
This is so great..
love ur videos so much...it helps me a lot❤️
This approach is good but i have one more approach for this problem => treating the 2D matrix as 1D only :-
we have to just find out its equivalent row and column and formula for same is
row = mid/m;
column = mid % m ;
code is :-
class Solution {
public:
bool searchMatrix(vector& M, int target) {
int n = M.size();
int m = M[0].size();
int low = 0;
int high = m*n - 1;
while(lowtarget)
{
high = mid -1;
}
else
low = mid +1;
}
return 0;
}
};
Please like if you find it useful :)
Traversing can also be started from bottom left and moving sideways or upwards.
thanx for such tutorials
Thank you bade bhai :)
Or vedios bnao aditya , osm yr, always bnate raho vedios bhai
Can you start a live class, i want a mentor, missing a mentor, mujhe aapka samjh me aata hai
Thank you big brother. ❤️
we can do this in (log(n)*log(m))🥰
Applying binary search on every row is also an intuitive approach that can bring down the time complexity to O(nlog(m)). And thanks bhaiya for all the videos.
complexity of the code is O(m + n) and its the best possible for this question.
@@revaanmishra can't we use binary search to find row first then the same method to find appropriate column number .so will complexity reduce to max(logn,logm)?
yes that is one of the intuitive approach, so in interview , first we can say O(m*n) and then optimise to nlogm and then optimise to o(m+n)
Intuition
This problem will purely be solved on the core principles of how a 2D matrix works,its traversal and a few comparisons.
Approach
We assign i=0 and j=n-1, means i is at start of the row and j is present at the start of the last column. We start comparing from j=n-1. Basically,the comparison is starting from the last element of the first row. Now,if observed closely, the last element of the first row, moving downwards from there will always result in a greater value as the 2D Matrix happens to be sorted. If target is smaller, there is no point moving down. Hence, we decrement j and move to the previous column. We check again, if target is still smaller (matrix[i][j]>target) we decrement j again.
observe one thing. As we move from the extreme right to left, we notice that values are eventually decreasing for the ith row. So we are bound to reach a point, where matrix[i][j] has a smaller value than target. If so, we now increment i and move to the row below,which gets us closer to the target.
Finally we reach a point where we find the target.
Complexity
Time complexity:
O(m+n)
Space complexity:
O(1)
Code
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length; // row
int n = matrix[0].length; // col
int i = 0;
int j = n - 1;
while (i >= 0 && i < m && j >= 0 && j < n) {
if (matrix[i][j] == target) {
return true;
} else if (matrix[i][j] > target) {
j--;
} else if (matrix[i][j] < target) {
i++;
}
}
return false;
}
}
is simply applying the binary search on row and column a good approach?
Just wanted to ask , can't we apply binary search here .
We'll start from arr[mid_row][mid_col] and then first check between which two columns does our element lie and then similarly which two row , finally arriving at the element , this way the time complexity would be log(n)*log(m)?
we can do that but the complexity will be log(n) + log(m)
@@sudhanshugour3553 not + it would be *
can we use the bottom left corner also I guess in this case it will give solution more quickly and what we are doing for columns we can do the same for rows also! I think it will be same pls correct me if I am wrong thanks☺️
One solution that came to my mind is:
A.) First find the floor value index of the key in first row using binary search(time complexity will be O(log n)).Here index will be 1(20 is present).
B.) Then once again apply binary search on that particular column.
can we the problem this way???
I think its a little better solution and better way for implementing binary search
int m = matrix.size();
int n = matrix[0].size();
int low = 0;
int high = n-1;
int row = 0;
while(low
Excellent
BHAIYA PLEASE UPLOAD VIDEOS ON TREES AND GRAPHS! THOSE ARE MOST REQUIRED VIDEOS FOR US THAN ANYTHING ELSE!
Thanks
We can use binary search on this:
when u are in a particular column, find the floor of the target --> this becomes the new column
when u are in a particular row, find the ceiling of the target --> this becomes the new row
It will increase the Time Complexity
Next level 🔥
More videos plz , sab dekh lia😭😭
Bhai Maja Aa gaya Approach Dekh Ke
Waiting For Your Flipkart Coding Round BS Question Video
Will be uploading in few hours brother !!
@@TheAdityaVerma Thanks Bhai
@@TheAdityaVerma
Waiting for recursion and backtracking videos.
Good work. Keep going.
can we apply here binary search on column using floor and ceil after that binary search on the row?
Bro uska T.C :- nlogn ho jayega
best video !
waiting for backtracking tutorials !!
Thanks pls do code forces round question of dp using ur approach
Can you the links for those codeforces problems ?
@@RudraSingh-pb5ls bro u can use dp tag in problemset in codeforces
@@rishabsoni256 thnx buddy but I need one more help. If you have watched Aditya's DP video of min coin change problem then can you share your code for top down approach, cause I m terribly stuck at creating a large 2d global array of variable size depending upon user inputs.
sir pen ghumana seekhado ...nice explanation for the que thnx a lot
Once we found the item greater than key, then on that column we can apply binary search ( as column is also sorted ) leading to O(n + logm) complexity
Yes and i think this approch is better than this video's one.
Doesn't matter because asymptotically both are same.
@@somiljain7996 complexity of the code is O(m + n) and its the best possible for this question.
can this be done in log n + log m ?
Love you bhai....
Bhaiya vo DP ki Grid aur LIS vali videos ayengi kya ?
Bhai aani to chahiyee 😅😅, pr time lg jaaega thoda abhi !!
@@TheAdityaVerma bahiya pls ab dal do uspe vidio
Thanks bhaiya
Bhai sliding window ka bhi video banade na pls.
can we have a better sol with time complexity of O(nlogn), If we binary search for the key in each row ?
The Horizontal lines which you have created on the table are for us I know that :-)
ki sang tere paaniyon sa...paaniyon sa samajhta rahoon..oo..oo
Boss 🙏
we can further reduce the time complexity by using a binary search in every row and column.
We'll now have a code which will run in O(log(n) + log(m)).
My Solution: Leetcode (74):
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
n_rows = len(matrix)
if n_rows == 0:
return False
n_cols = len(matrix[0])
i = 0
j = n_cols - 1
while(i >=0 and i < n_rows and j >=0 and j < n_cols):
if matrix[i][j] == target:
return True
elif matrix[i][j] > target:
# no need to search downwards; search leftwards
j -= 1
else:
# no need to search leftwards; search down this column itself
i += 1
return False
Sir, Please make videos on trees and graph
Now I understand why they call u "god of DS & Algorithm"
Since we are searching in sorted array to jo ham linear search karte hain, uski jagah binary bhi to implement kr skte. For example while moving left, we just need to find Floor(X) and while moving down, we have to find Ceil(X). Isse Time Complexity kaafi kam ho jayegi. Am I right?
You can also solve this question using binary search :-))
Time : O(log n + log m)
Space : O(1)
Explanation and Code:-
Observe the matrix and you will notice that all rows and columns are sorted.
Now, we can apply binary search on the first column of the matrix and check if it contains the target. If it does, then return true.
If not, the binary search will end with high pointing towards the element just smaller than target. This is not a conincidence!! Try dry running binary search on an array for an element which is not present in the array. You will always observe that the binary search will end with high pointing towards the element just smaller than the target.
We will use this to our advantage!
By now you would have understood what to do next :-)).
Now as you have found the element just smaller than target; you are now on the right row, as this row will contain elements greater than on its right hand side.
Now, apply binary search on this row and you will find the target.
If none of that happens, return false as the target never existed in the matrix.
The below code is just a search code, but you can modify a bit and use the same to return indices of the target as well.
bool searchMatrix(vector& mat, int target) {
int lo=0, hi=mat.size()-1;
int mid;
while(lotarget)
hi=mid-1;
else lo=mid+1;
}
if(hi==-1) // Edge case if hi goes out of bound.
return false;
int row=hi;
lo=0, hi=mat[0].size()-1;
while(lotarget)
hi=mid-1;
else lo=mid+1;
}
return false;
}
You can also think of first applying binary search on the first row, find the appropriate column and then apply it again on that column :-)).
Like to let more people know about this and aditya to pin this comment :).
is it two pointer approach or Binary Search?
Sir ek series baisae question pae bhi banana jinko bit main sochh kar solve kartae hai
Bit manipulation bala
but sir why did we started the searching of the element in the matrix from top right corner
why not top left or bottom left/right ? any specific reason ??