Search in 2D Matrix | Leetcode 74 Solution | Searching and Sorting

Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. For a better experience and more exercises, VISIT: www.pepcoding.com/resources/o...
Have a look at our result: www.pepcoding.com/placements
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education

[@sakshiaggarwal6199]

Manisha mam ka padhaya hua ek dum clear ho jata hai ek dum jadu ☺️. Hats off to Manisha mam and Sumeet sir 🙏🙏. Keep uploading the best content as always.

[@prakharpathak9212]

Great teachers great content 🔥.
Thank you so much to Pepcoding team for providing such an amazing content free of cost.

[@Pepcoding]

Thank you so much and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )

[@prakash36g]

Your explanation is really great, anyone can understand easily.

[@dietpepsi7338]

my fav teacher of pep

[@Pepcoding]

Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊

[@VikasGupta-ok9lh]

After sumit sir mam u have great understanding of concepts with very good teaching skills

[@vishalsinghrajpurohit6037]

Great Explanation. Thik hai ji

[@Pepcoding]

Glad to know, that you love the explanation, for better experience and precisely arranged videos.
Visit - nados.pepcoding.com and sign up to NADOS.
Don't forget to follow us on Instagram instagram.com/pepcoding/

[@popularedits6984]

Very nice mam 😊

[@ankitkatewa2943]

great explanation please keep uploading new videos daily

[@Pepcoding]

Thank you, I will

[@snehaashishgupta1254]

shouldn't we treat it like a sorted list instead and find row and col by cell_val/n and cell_val/m where matrix is n*m that'll give log(m+n) instead of m*log(n)

[@RishabhJain-hr6sz]

Superrrr!

[@Pepcoding]

Glad you love the explanation,
For better experience and well organised content sign up on nados.io
And for being updated follow us on Instagram instagram.com/pepcoding/

[@vaibhavgupta973]

nice

[@pushpaksambhe7405]

Which has best Time Complexity
O(log(nm)) or O(logn+Ologm) ???

[@aryangupta2014]

log ka formula h wo, both r same

[@sahilsaxena8374]

Ma'am we have to calculate mid as
Mid= lo + (Hi-Lo)/2
To avoid overflow

[@indranilchakraborty5949]

yea kya fanda hai vaii??

[@shashankkumar1974]

@@indranilchakraborty5949 arey dekh bro, agr l+h/2 kre to ho skta hai ki l+h is greater than 32 bit integer size to overflow issue aa jayega and agr l+(h-L)/2 kre to ye issue surely nhi aayega.

[@Rohan-rz2qn]

@ThoRin nahi bro jb mam wale code ko leetcode pr submit karoge toh waha pr overflow ho jayega

[@bharatmakkar9706]

simply do (hi+lo)/2

[@letsdoeverythinginoneweek9398]

maam ek confusion haa
jo aapna potential row nikali ha
usma jo aapna hi ki value lee ha vo hi=matrix.length-1 lee ha ya toh hame row ki length degi naa.
hame toh column ki length chahia toh kya hum esa nahi likh sakta hi=matrix.length[0]-1

[@harshanand4018]

hi=matrix.length[0]-1 nahi likh sakte kyunki hamlog row traversal kar rahe hai.

[@tanyagupta0201]

This solution gives TLE in C++

[@manishapawar3471]

working faster than 100%
C++ code
class Solution {
public:
bool searchMatrix(vector& matrix, int target) {
int pr = findPotentialRow(matrix,target); //log n

if(pr == -1) {
return false;
}

return binarySearch(matrix,pr,target); //log m
}

int findPotentialRow(vectormatrix,int target) {
int lo = 0;
int hi = matrix.size()-1;
int lc = matrix[0].size()-1;

while(lo target) {
hi = m-1;
}
else {
lo = m+1;
}
}

return -1;
}

bool binarySearch(vectormatrix,int r,int target) {
int lo = 0;
int hi = matrix[0].size()-1;

while(lo

[@ialgorithms]

Python solution:
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
r = self.rowSelection(matrix, target)
isFound = self.binarySearch(matrix, r, target)
if r == -1:
return False
return isFound
def rowSelection(self, matrix, target):
lo = 0
hi = len(matrix)-1
lc = len(matrix[0])-1
while lo

[@LegitGamer2345]

simple one pass :
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int low = 0;
int high = (matrix.length*matrix[0].length)-1;
while(lowtarget) high = middle-1;
else low = middle+1;
}
return false;
}
}
credits : leetcode discuss :p

[@soumyadrip]

thumbnail looks different though

[@ytg6663]

U r clickbait