do we need 2 variables or 4 variables to track the position of elements to solve this?? and check the logic also?
and is this search can only make in the square matrix or any matrix??
question:- https://online.codingblocks.com/app/player/189104/content/180062/1105/lecture
hello @dasvishal60
the logic is incorrect.
for example if key is 10 , and u r at 13, then as per u logic , u will discard all columns that are in right of 13 (becuase key < 13), which is wrong as 10 falls in right.
so then I need to update each position of each corresponding element +1 after each iteration but then it will not similar to binary search??
either iterate all rows and find whether element exist in that row or not using binary search ( M Log N ) time complexity.
or follow this divide conquer technique O(N+M ) time complexity.
We will make use of the fact that matrix is row wise and column wise sorted. So if we start from the top right we can observe the fact that if we go in the left direction the numbers decrease and if we go downwards the numbers increase. So we can restrict our search space depending on which index we are currently at. If the number at which we are currently standing is greater than the target number then it is obvious that we can find it on the left side of the current row and if the target is greater than the element at current standing then it is obvious that we can find it towards the bottom in that column where every number is greater.
check code now also check for if the number is not found and this code can be more better??
and is this the best case for time complexity or somewhere medium ??
I don’t know much about time and space complexity as it is not given in course of my college where can I learn this in detail??
check now->
here u dont have to compute mid.
there is artcile on hackerearth , u can read it and then practice some problems from gfg
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.