21 Search in Row wise And Column wise Sorted Array
Vložit
- čas přidán 9. 04. 2020
- SEARCH IN A ROW WISE AND COLUMN WISE SORTED MATRIX:
Given an n x n matrix and a number x, find the position of x in the matrix if it is present in it. Otherwise, print “Not Found”. In the given matrix, every row and column is sorted in increasing order. The designed algorithm should have linear time complexity.
Example :
Input : mat[4][4] = { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};
x = 29
Output : Found at (2, 1)
PROBLEM STATEMENT LINK:www.geeksforgeeks.org/search-...
PLAYLIST LINK: • Binary Search | Interv... .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
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
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 🥺😭😭😭
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! ❤️
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!
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.
Hi Aditya, I was struggling with DSA and CZcams recommended me your channel, thanks a lot to you and CZcams for such a quality content
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.
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 finally understood this one! Great explanation..Thank you :)
gone through the whole playlist this is pure gold, thanks Aditya for taking the effort
Thanks, sir. Your way of explanation is truly awesome.
very well explained! thank you for uploading these content.
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
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
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 🚫
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
hands down one of the best approach ive ever seen
This is so great..
love ur videos so much...it helps me a lot❤️
Worthy! content literally 🔥
The way you explain the solution is awesome👍
Thank you Adithya Verma...
I was asked this question in PayPal interview for SDE-1 when I was at college. Well explained.
Now in which company you're??
Thank you Bhaiya !
Keep it up !
You are helping a lot of people ... may god bless you !
loved the way you explained❤
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
this is the best video on this topic. thanks sir
thanx for such tutorials
Nice explanation sir....thanks for the playlist
very well explained with code great work
Bhai .. ek no. Explanation.. watched your video for the first time , ab se aapka hi vdo dekhna h 🤟🤟😇
thanks bhaiya ....!
no word for u....u are really amazing and very helpfull ....!
Thank you big brother. ❤️
Please upload a playlist on Backtracking as soon as possible!
Nice Explaination
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
@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 : czcams.com/video/uPqPDPjtPX4/video.html
Best playlist for bs. Thanks.
Traversing can also be started from bottom left and moving sideways or upwards.
Bhaiya, please make videos on string algorithms (advanced ones)
can we have a better sol with time complexity of O(nlogn), If we binary search for the key in each row ?
Bht sahi hai yr bhai..tester ko bhi coding sikha diye
bas explanation hi enough hai sir aapka 😏😍.. code toh hum 80% apki explanation se kr dete hai... ❤
bahut achi approach, maza aya dekhne me.
Most optimal for this problem is using binary search with time complexity O( log(m ) + log (n) )
Really like your way of teaching. Can you please make a playlist for time and space complexity?
Watch this for time complexity analysis czcams.com/video/oPvT1IBXNxM/video.html
very nice explanation
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
Next level 🔥
BHAIYA PLEASE UPLOAD VIDEOS ON TREES AND GRAPHS! THOSE ARE MOST REQUIRED VIDEOS FOR US THAN ANYTHING ELSE!
Thank you bhaiya very easy explanation
finding coding easy through ur lectures .
is simply applying the binary search on row and column a good approach?
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.
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)
bhai maja aa gaya yaar Aditya pls make more playlist like these
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)
Thank you bade bhai :)
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☺️
Thanks aditya bhai
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 ??
This could be beautifully done with the help of recursion by tranversing diagonally and eliminating top left sub matrix and bottom right submatrix.
Thanks bhaiya
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 apply here binary search on column using floor and ceil after that binary search on the row?
Bro uska T.C :- nlogn ho jayega
Love you bhai....
Gawddd level teacher 🔥🔥🔥🔥🔥🔥
best video !
Thanks
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.
The Horizontal lines which you have created on the table are for us I know that :-)
Thank u bhaiya😌👐,
Thanks you for watching brother !!
Excellent
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
waiting for backtracking tutorials !!
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.
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 :)
Sir, Please make videos on trees and graph
Sir ek series baisae question pae bhi banana jinko bit main sochh kar solve kartae hai
Bit manipulation bala
Can anyone tell why did we started from top right. is it because that number will always lie in the middle . so can we also do it from bottom left? or is there some other reason for this? and please tell us the approach on how did u think of this. Thanks
Or vedios bnao aditya , osm yr, always bnate raho vedios bhai
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???
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)).
is it two pointer approach or Binary Search?
Now I understand why they call u "god of DS & Algorithm"
awesome
Bhai sliding window ka bhi video banade na pls.
More videos plz , sab dekh lia😭😭
can this be done in log n + log m ?
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
your thanks was very cold 😂
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.
we can do this in (log(n)*log(m))🥰
0:01 what an intro bruhhh :)
What happened to the 20th video?
nice
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;
}
why do we need to start from top right?
i think we can reduce the complexity further
@Aditya Verma, please make video on "Search Kth Smallest Element in a Row wise and Column wise Sorted Matrix using Binary Search"
Yesss
if we use Binary search on every column isn't it become O(mlogn) in worst and O(logn) in best???
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