Search a 2D Matrix - Leetcode 74 - Python

[@NeetCode]

🚀 neetcode.io/ - A better way to prepare for Coding Interviews

[@canete_code]

God knows how many people have landed job thanks to this man. Thanks a lot Neetcode

[@yt-user-99]

No need to do multiple binary searches. Since it is sorted top to bottom, and left to right, you can basically treat the 2d matrix as a single array where left = 0 and right = height * width - 1. In each iteration just calculate the rows and columns as such: row = floor(mid / width), col = mid % width.

[@chenjus]

this is also a convenient trick for golfing a nested for loop! slight tweak if you're using python, can do hard divide mid//width, so don't need the additional function call to math.floor.

[@arminphulkar]

Yeah, playing with the indices itself makes things much easier!

[@pranavsharma7479]

bro if interview you forget the formula of conversion then ? also there are main issues in this approach, 1. m (rows) , n(cols) when you go mn it may cause overflow.

[@prunesalad]

the multiple binary searches strategy should have better worst case perf. log m + log n vs log mn

[@xenomagpie4484]

@@prunesalad no, cause log m + log n = log mn

[@parthbrahmbhatt2619]

Felt like I was listening to Dora when he asked me, "Do you know an algorithm that can search a target value in a sorted array? **Brief pause** I know of one, called Binary Search"

[@haymasunder2638]

Very good explanation, But do we need to specify row=(top+bot)//2 again since once we break out of the first loop we already have the row to be searched with us

[@NeetCode]

Good point, I think you are correct

[@OMFGallusernamesgone]

I was so happy I solved this myself after doing the 2 Blind75 problems. I did it different/arguably easier: just do binary search and pretend the list is already concatenated, to get the mid value, write a decrypt function which is just row = idx % row_len, col = idx // row_len

[@minciNashu]

both solutions are log mn

[@vinprabhu]

Log (m+n)

[@ClassicalRaritiesChannel]

Yep, this is the way. What's presented in the video is waay overcomplicated

[@JyotiKumari-dg3oq]

Thanks, NeetCode for the amazing content. Your daily video inspires me a lot. Keep doing this amazing work.

[@andreytamelo1183]

For curious, imo there is a bit more intuitive and straightforward solution which exploits the property stated in the problem description: "The first integer of each row is greater than the last integer of the previous row.". It essentially gives us right to interpret the matrix as a regular single-dimension array via a simple index -> (row, column) translation math. (C#) public bool SearchMatrix(int[][] matrix, int target) { int left = 0; int rows = matrix.Length; int columns = matrix[0].Length; int right = rows * columns - 1; while (left

[@ryankawall3550]

Dude you’re awesome !!! I don’t what I’d do without these videos ..

[@krzysztofsobocinski2207]

Nicely explained. I tried another approach with just 1 binary search over whole matrix converting search index to coordinates. Resulting code is more concise.

[@urlvo]

Hello, I really like your answer, optimal and easy to grasp! I however feel like after finding the targetRow after the first while loop, we do not need to row = (top + bottom) // 2 before the second while loop; we already have row in memory.

[@rparsons779]

I thought I was going crazy. when I saw that too. You're right, we already have the row in memory.

[@sharangkulkarni1759]

yes

[@erickmercado1711]

Yeah we already have that same calculation stored in memory. That is redundant but maybe its to help people visualize it better

[@elab4d140]

I think he did that because he thinks it will go out of scope when it reaches the second loop, but in python, variables defined within a function are not limited to the scope of the block in which they are created

[@aspisov]

we can just assume we have an array instead of matrix and then decode our array index (convert into i, j) n, m = len(matrix), len(matrix[0]) l, r = 0, n * m - 1 while l target: r = mid - 1 else: return True return False this is btw a very useful trick for solving some linear algebra problems (nxm matrix is isomorphic to R^(nxm) vector)

[@roguenoir]

Since each row and column is sorted and the last value in one list is smaller than the first value in the subsequent list, you can simply join all the consecutive lists together into one huge list and do binary search on that one. This may take extra memory and modifies the input. But if we don't want to take extra memory and don't want to modify the input, we can use that same logic and pretend we're working with a single list and use a function to map an index on that large list to a cell in the matrix. I do it this way: h = len(matrix) w = len(matrix[0]) def translate(x): col = x % w row = (x - col) // w return row,col Then do a binary search on a "list" of length h*w with i = 0 and j = h*w - 1 but you use the translate() function to convert the 1-D index into the 2-D index to look up the value in the matrix.

[@bigbigdog]

If you put all the values into a single list then that would be an O(n) operation.

[@jude3926]

@@bigbigdog No it would be log(m*n) because you are essentially gonna perform binary search on m*n elements

[@tenkara101]

I'm wondering why this isn't the best answer. It's easy to visualize, works just as fast at O(log m*n) since we're operating on a m*n length array once the 2D array is translated. @bigbigdog that would be incorrect, because we're just doing binary search on m*n elements. Therefore it takes O(log m*n) time.

[@exdoth1376]

Putting the values of the matrix into a list has time complexity O(n). Consider a matrix with m rows but only 1 column (like a vector), to translate this matrix to an array you have to access every single row and thus every single item (since the number of rows is the number of items because each row has 1 item) so in the end it becomes a linear operation.

[@sodo3872]

I think the O time is Logm + Logn, instead of Logm * Logn. Is it so? Because after the binary search of rows, we have narrowed down the search scope to one row. Then we only need to do another binary search for that one row, instead of every row.

[@Mo-cn9kd]

that was what he had i think

[@fogotunde-onadele8016]

He had it right at 4:30 but wrote it wrong by accident at the end

[@thisguylives3827]

well if there is one row and 1000 columns for example, that would be log(m*n) technically worst case

[@technophile_]

log(m) + log(n) can be written as log (m * n), ie log(m) + log(n) = log (m * n). This is known as the product property of logarithms.

[@Nazgenyanly]

Wait till you discover log properties

[@bluesteel1]

Lower bound on the last column to find row than binary search on that (log mn) Iterative where you start at the top right go down if array element is smaller go left if array element is larger (m + n)

[@ahmadmtera]

You could've used an auxiliary function to do the 1D Binary Search (Divide a Large Problem into Smaller Ones Strategy). This would allow you to put "return helper(...)" in the else statement at line 13 and a "return false" at line 14 and erased everything from line 15 onwards.

[@sumkid9263]

I loved this problem, if you could understand and implement binary search, then you have everything you need to solve this.

[@hr3392]

I don't think we need to check for bottom exceeding top after the first binary search. It worked fine without that portion of code. The break statement would only be hit when the condition for the while loop is valid, so I think the check is not needed

[@nguyentuan1990]

correct me if i am wrong, but after the first binary search, we would know exactly which row the target belong to? meaning you dont have to do row = top + bottom // 2 on the second binary search. But at this point, top and bot row are pointing at the same row and for sure contains target and can be treated as an array?

[@tuandino6990]

That row variable only exist in the first while loop

[@zapuhlyak]

Thank you for your videos! They are really helpful for me. I decided to share with you my approach with only one loop. This code in Swift. ```func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool { let rows = matrix.count let columns = matrix[0].count var left = 0 var right = rows * columns - 1 while left target { right = middle - 1 } else if value < target { left = middle + 1 } else { return true } } return false }```

[@Isaac-gz8wx]

you do leetcode in swift?

[@vividviking6187]

I came up with this thinking that it would be log (m * n). Could someone confirm, my thinking is that by using only the first and last element, continuing and not searching the sub list would the same as ignoring it. Is it the same efficiency or would mine be worse? class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: for r in range(len(matrix)): low, high = 0, len(matrix[r]) - 1 if target > matrix[r][high] and target < matrix[r][low]: continue else: while low target: high = mid - 1 return False Edit: I recognized that I would still need to visit each row at least once so it probably would have been O (m logn) instead. Implemented a binary search on both rows and column and corrected the issue.

[@eshabaweja]

Solved it before watching the video because your 150 Roadmap says "binary search" which was a HUGE hint. Gonna see your solution now.

[@ddshoo5282]

i just modelled it after the basic binary search solution lol: class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: l = 0 r = len(matrix) * len(matrix[0]) - 1 while l target: r = mid - 1 elif matrix[midRow][midCol] < target: l = mid + 1 else: return True return False

[@kumareshnatarajan4614]

A simpler method is to flatten a 2d array by adding it with a empty list, and then checking if target is in the flattened list, 4 lines of code.

[@WeirdAlSuperFan]

that sounds like O(mn) complexity

[@Ragdoll333-q5l]

Really love your explaination! Could you make a video list of google interview coding questions(high frequency)?

[@souvikbhattacharya9082]

what is the need for line 15 to 17 ? we have already checked the top

[@surajthapa5808]

Yes, no need to do row = (top + bot)// 2 second time since we already found our row.

[@cristianh.valderrama1603]

Hello, I am looking for how to perform a search in a 2d array vertically, horizontally and diagonally (right and left) of 4 equal characters, example "AAAA" and see how many times it is repeated, what algorithm do you recommend? I have looked for it but not I know which one to choose, lower cost and time. It is a nxn array, thanks to your help it would be very useful. PS: Sorry my english, I'm using google translator

[@DarylKielMora]

Since we only need to know if the target value is in one of the lists inside the matrix parameter, I decided to just check if the target value exists in the list for the corresponding middle index I get from binary searching. Here's my take on it in python3: class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: start, end = 0, len(matrix) - 1 while start target: end = mid - 1 else: start = mid + 1 return False Thank you for the videos, NeetCode!

[@dusvn1484]

I think I solve this on easy way. I listen your lecture for recursion and it's not same for this problem but I identify we need to do search for every row until we find value or mby not. I say this for recursion becouse I identify base problem for every row of matrix So how I solve this: 1.Write function for binary search 2. Go in loop thought all lists and if return value of binary search for single list is != -1 just return true 3. After for loop just return False becouse we go thought all list and we don't find target value I hope this help for us guys :D

[@harishsn4866]

Hey, just a small doubt. in the first while loop, when target > matrix[row][-1] and target < matrix[row][0] fails, we are breaking out of the loop. I was thinking what if the target == matrix[row][-1] or target == matrix[row][0], then we can just return True. I did try this but it shows "Time Limit Exceeded". I could not understand why it doesn't work. Can you please shed some light on this? while top matrix[row][-1]: top = row + 1 elif target < matrix[row][0]: bottom = row - 1 elif target == matrix[row][-1] or target == matrix[row][0]: return True

[@Ajay-cs5lf]

the third condition should not be like this. Because the target value might be falling into the range, not the exact left most position or right most position. try this out: elif target >= matrix[row][0] and target

[@stylisgames]

This is a pretty tough one! Tons of edge cases.

[@AcademictoIndustrytalk]

One can use itertools.chain() for one line solution. This also valid for problem search 2d matrix II (leetcode 240). return target in list(chain(*matrix))

[@WeirdAlSuperFan]

that's linear time complexity and a one-way ticket to a failed interview

[@oguzcan123]

class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: k = 0 for i in range(len(matrix)): p = matrix[k][0] s = matrix[k][len(matrix[k]) - 1] print(p, s) if p

[@thndesmondsaid]

Funny, I always thought of the first row of the matrix as the "bottom", and the last row as the "top"... thinking about it from an ascending order. Had to realize that I had those swapped to debug my own solution here lol.

[@orangethemeow]

Why does "if not (top

[@Great_Papa]

因为如果target很大，top就会一直+1，直到比bot还大，这个时候就证明target不在matrix里。同理，如果target很小，bot一直-1，直到-1，比0小，这个时候target不在matrix里。

[@ok-cr3yd]

If the while loop ends due to the pointers crossing, it means that the binary search was not able to find a row that would contain the target

[@shush5878]

class Solution(object): def searchMatrix(self, matrix, target): l = 0 while len(matrix) - 1 >= l: if target in matrix[l]: return True else: l += 1 return False

[@Priyam6F4]

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; } }

[@JamesBond-mq7pd]

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: ROW, COL = len(matrix), len(matrix[0]) left = 0 right = ROW * COL - 1 while left target: right = mid - 1 elif matrix[row][col] < target: left = mid + 1 else: return True return False

[@jocelynwang6270]

thank you!

[@keyursolanki]

Love the way you explain the structure and way to solve the algo. But do we need the second binary search for the element is present in a single row or not. We can do that if we want to find the index of that element but here all we need is that if the element is present or not. Please correct me if I am wrong. Thanks again for your support. :)

[@jude3926]

You have the right idea..however, if you did that it would be log(m)*n because you did binary search on rows and then went through every element in that row of n elements to check for the target( "return target in row" is O(n) because it searches every element in that row)

[@rasulsilva2985]

This code doesn't pass the test cases on the problem, for instance [[1],[3],[5]] does not work

[@hr3392]

Its working fine for me

[@rasulsilva2985]

@@hr3392 yea I ended up getting it working too. I can't remember what it was but it was my fault

[@henryCcc8614]

I don’t think there’s a need for all that. Set current value to the top right, if target less than current, col-1, if target greater than current, row+1, else return current value.

[@CeciliaBarnes-f8n]

Instead of the second while loop, you can just do `return target in matrix[row]`

[@pepperdayjackpac4521]

but what would the implementation of "return target in matrix[row]" be?

[@victoronofiok4551]

shouldn't it be if not (bot

[@MrRenaissance17]

I'm curious for my understanding does each row in the matrix have to be the same identical length?

[@minciNashu]

according to the statement, the sizes are fixed M x N

[@hwang1607]

You can solve this by converting regular indices to 2d array indices: class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: ROWS = len(matrix) COLS = len(matrix[0]) l = 0 r = ROWS*COLS - 1 while l = midnum: l = mid + 1 else: r = mid - 1 return False

[@thekiran]

recalculating the row before the row search loop is redundant as the value of row remains same throughout..

[@jasonahn8658]

Can anyone explain how "if not(top < = bot): return False" immediately returns True if the target value is not in the matrix?

[@The6thProgrammer]

"if not(top

[@AniruddhaShahapurkar-wu3ed]

Another variant: Key is always starting from top right corner of the matrix. But the time complexity of this is O(m+n) class Solution(object): def searchMatrix(self, matrix, target): """ :type matrix: List[List[int]] :type target: int :rtype: bool """ r = 0 c = len(matrix[0])-1 print(len(matrix)) while r < len(matrix) and c >= 0: if matrix[r][c] < target: r += 1 elif matrix[r][c] > target: c -= 1 else: return True return False

[@dragtr0n]

converted into single array and then did binary search emp = [] for e in matrix: emp = emp + e

[@xushengchin511]

Somehow the code doesn't work on case 1: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]] target = 3 Code from video: ```python class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: ROWS, COLS = len(matrix), len(matrix[0]) top, bot = 0, ROWS - 1 while top matrix[row][-1]: top = row + 1 elif target < matrix[row][-1]: bot = row - 1 else: break if not (top

[@david_tgridy]

I iterated over the list and then did binary search like normal afterwards for ra in matrix: if ra[-1] < target: continue

[@raphaelespanha4554]

your approach would be n * log m I guess since you have to iterate over all n rows

[@ivayloarnaudov7816]

Maybe you can do it in O(n + m), because we can use the ordering of the matrix elements and reduce the checks

[@DavidDLee]

Sure, but O(n + m) > O(log(n*m))

[@vikaschauhan3845]

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: for row in matrix: if target == row[0] or target == row[-1]: return True elif target > row[0] and target < row[-1]: low = 0 high = len(row) - 1 while low row[mid]: low = mid + 1 else: return True return False

[@fizruk7644]

Yall there's an easier solution: m = len(matrix) # rows n = len(matrix[0]) # columns l = 0 r = m * n - 1 while l matrix[mid_m][mid_n]: l = mid + 1 elif target < matrix[mid_m][mid_n]: r = mid - 1 else: return True return False

[@ok-cr3yd]

10:10 I think you misspoke here. If the target is smaller than the midpoint, you want to search to the left of it, not the right

[@harijoel]

pro tip: you can use else on a while loop statement

[@anasraza2000]

My Solution : class Solution: def searchMatrix(self, matrix: list[list[int]], target: int) -> bool: that_row = 0 for i in range(len(matrix)): if matrix[i][-1] >= target : break else : that_row += 1 try: if target in matrix[that_row]: return True except: return False

[@Emorinken]

Thank you very much man

[@valkon_]

Holy, did this really got 2k likes more since June? Damn everyone is leetcoding, get your jobs now guys it will be a bloodbath soon.

[@myname9114]

Is this a good approach class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: oL, oR = 0, len(matrix) - 1 while oL matrix[mid][-1]: oL = mid + 1 else: arr, il, ir = matrix[mid], 0, len(matrix[mid]) - 1 while il arr[imid]: il = imid + 1 else: return True return False

[@sahilarora4602]

Thanks Neetcode

[@oneke4498]

7:58 WHYYYY GOOOOD I KNEEWW IIITT !!! :'D

[@ahmedzedan1772]

Thank you dude!

[@sharangkulkarni1759]

why recalculate row?

[@shadowwolf5578]

why c++ and java code is smaller than python :)

[@rojinprajapati6840]

This solution now shows the time limit exceeded.

[@brentmarquez9057]

getting the same thing

[@antony9058]

For me it works perfectly

[@jakearmijo]

league client tick noise at 6:53 was confusing me. thought it was mine

[@ethanhsu6761]

I don't hear it? I only hear his keyboard sound?

[@mr6462]

Thanks for the amazing content

[@NeetCode]

Glad it's helpful!

[@GoziePO]

Who else freaked out at 8 minutes when he switched the top / bottom update on accident? 😂 Thought I was going mad.

[@naimeimran3247]

Thanks

[@cloudboysmusic5223]

Neetcode, memorizing this sh1t for google!

[@yugaank100]

for i in matrix: if target in i: return True return False this works too 🤣

[@yugaank100]

and for some reason, this computes faster

[@malarkodibalakrishnan7961]

Don't you think this is unnecessary? after breaking while loop row = (top + bot) // 2 Code will just work fine without this

[@coliv2]

It seems that this guy doesn't know that log(n*m) = log n + log m, in other words, the more complex algorithm is completely irrelevant, you can just consider the matrix as a big array and do bin search only once!

[@indhumathi5846]

understood

[@AtulSharmany]

would n't it be easier to do this: key is to translate 2d index to 1d index ------------------------------------------------------------------ t = len(d[0]) * len(d) def search(l1, r1): if l1 >= r1: return -1 m = l1 + ((r1 - l1) // 2) r2, c2 = m // 4, m % 4 diff = target_value - d[r2][c2] if diff == 0: return (r2, c2) , d[r2][c2] elif diff > 0: return search(m + 1, r1) else: return search(l1, m - 1) return -1 res = search(0, t - 1)

[@edwardteach2]

You a 2d binary search matrix God😢

[@indraxios]

soon i will crack google too.

[@therealjulian1276]

Surprisingly bad solution, this won't even be accepted as a solution on LC anymore. I suggest doing a regular binary search and use `row = mid // cols` and `col = mid % cols`.

[@dk20can86]

This shouldn't be a medium, it's a very easy question.

[@minciNashu]

it still is a medium on leetcode

[@kenkaneki5433]

u should have made binary serach for top and bott. not increasing and decreasing just by one. this way its still linear so u got O(m) + O(log(n)).

[@maamounhajnajeeb209]

thanks