21 Search in Row wise And Column wise Sorted Array
Вставка
- Опубліковано 6 вер 2024
- 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.geeksforge...
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
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 🥺😭😭😭
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
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 🚫
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 was asked this question in PayPal interview for SDE-1 when I was at college. Well explained.
Now in which company you're??
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! ❤️
Hi Aditya, I was struggling with DSA and UA-cam recommended me your channel, thanks a lot to you and UA-cam 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.
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
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;
}
@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 : ua-cam.com/video/uPqPDPjtPX4/v-deo.html
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
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)
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!
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
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.
gone through the whole playlist this is pure gold, thanks Aditya for taking the effort
Most optimal for this problem is using binary search with time complexity O( log(m ) + log (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;
}
}
hands down one of the best approach ive ever seen
Bhaiya, please make videos on string algorithms (advanced ones)
The way you explain the solution is awesome👍
Thank you Adithya Verma...
Really like your way of teaching. Can you please make a playlist for time and space complexity?
Watch this for time complexity analysis ua-cam.com/video/oPvT1IBXNxM/v-deo.html
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
loved the way you explained❤
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.
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???
Bhai .. ek no. Explanation.. watched your video for the first time , ab se aapka hi vdo dekhna h 🤟🤟😇
Please upload a playlist on Backtracking as soon as possible!
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 :)
Thank u bhaiya😌👐,
Thanks you for watching brother !!
very nice explanation
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 :).
Thank you bhaiya very easy explanation
Traversing can also be started from bottom left and moving sideways or upwards.
Thank you Bhaiya !
Keep it up !
You are helping a lot of people ... may god bless you !
very well explained with code great work
bas explanation hi enough hai sir aapka 😏😍.. code toh hum 80% apki explanation se kr dete hai... ❤
Bht sahi hai yr bhai..tester ko bhi coding sikha diye
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
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)).
Thanks, sir. Your way of explanation is truly awesome.
finding coding easy through ur lectures .
I finally understood this one! Great explanation..Thank you :)
Best playlist for bs. Thanks.
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
very well explained! thank you for uploading these content.
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☺️
this is the best video on this topic. thanks sir
What happened to the 20th video?
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;
}
Thanks aditya bhai
This is so great..
love ur videos so much...it helps me a lot❤️
thanks bhaiya ....!
no word for u....u are really amazing and very helpfull ....!
Nice Explaination
bhai maja aa gaya yaar Aditya pls make more playlist like these
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.
is simply applying the binary search on row and column a good approach?
Nice explanation sir....thanks for the playlist
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)
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 *
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.
bahut achi approach, maza aya dekhne me.
Worthy! content literally 🔥
Thank you bade bhai :)
Or vedios bnao aditya , osm yr, always bnate raho vedios 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 ??
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
thanx for such tutorials
Excellent
best video !
0:01 what an intro bruhhh :)
Thanks
Gawddd level teacher 🔥🔥🔥🔥🔥🔥
BHAIYA PLEASE UPLOAD VIDEOS ON TREES AND GRAPHS! THOSE ARE MOST REQUIRED VIDEOS FOR US THAN ANYTHING ELSE!
@Aditya Verma, please make video on "Search Kth Smallest Element in a Row wise and Column wise Sorted Matrix using Binary Search"
Yesss
can we have a better sol with time complexity of O(nlogn), If we binary search for the key in each row ?
Thank you big brother. ❤️
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
The Horizontal lines which you have created on the table are for us I know that :-)
your thanks was very cold 😂
waiting for backtracking tutorials !!
What if we first find the floor in the column using BS, which gives us LogN(n columns) complexity, and then use BS to find the element in logM (m rows) complexity.
The total complexity will be, LogN + logM.
I think traversing from the top right is easier, but for me using BS is more intutive.
This is a better approach. The above approach takes O(n * log m) not O(log m * log n) which is needed.
Next level 🔥
we can do this in (log(n)*log(m))🥰
We can solve this question in O(logm + logn)
If we do BS on the rows and BS on the col then we can achieve this time complexity.
Let has have a matrix of m x n size
Basically by using BS we "find" the "row" which has its row[0] >= target and row[n-1]
Yes It's a good approach. We can find our key using binary search in O(n * log m) by iterating through the rows and then finding the key. But yours is good too. Thanks for sharing.
why do we need to start from top right?
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
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
Sir, Please make videos on trees and graph
Bhai sliding window ka bhi video banade na pls.
can this be done in log n + log m ?
Now I understand why they call u "god of DS & Algorithm"
//java code
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
//arr[0][c-1]
int r = matrix.length;
int c = matrix[0].length;
int i = 0;
int j = c-1;
while(i=0)
{
if(matrix[i][j]==target)
return true;
else if(matrix[i][j]target)
j--;
}
return false;
}
}
is it two pointer approach or Binary Search?
if we use Binary search on every column isn't it become O(mlogn) in worst and O(logn) in best???
More videos plz , sab dekh lia😭😭