LeetCode Search A 2D Matrix Solution Explained - Java

Preparing For Your Coding Interviews? Use These Resources
————————————————————

Other Social Media
----------------------------------------------

Show Support
------------------------------------------------------------------------------

#coding #programming #softwareengineering

[avii]

The way I understood midpoint_element = is -


To convert 2D array into 1d array, you *multiply* rows by columns on line 9, int right = rows * columns - 1

So to convert it back to 2D, we do the opposite of the above multiplication and hence we *divide* the index value by columns to get row value. And whatever remaining which is midpoint%columns will be the column value.

[MrKracx]

In case anyone is confused about the midpoint_element = matrix[midpoint/columns][midpoint%columns], here is my way of understanding:

In the example at @11:28, we have 3 rows, 4 columns

When finding the initial midpoint, we do (0+11)/2 = 5

Think about this statement very carefully:

Every row has 4 columns. Read it again. Every row has 4 columns. Read it once more. 1 row consists of 4 columns.

So if I'm given an index, and I need to calculate the row, its just dividing by the number of columns.

First row has columns 0, 1, 2, 3
Second row has columns 4, 5, 6, 7

For calculating the column number, you have to realize that the column of index = 0 is same as the column of index = 4. Similarly, the column of index 1 = column of index 5.
That is, index 0 and 4 are still considered column 0. Index 1 and 5 are still considered column 1.

In this sense its just wrapping around, and when we have something like this, we use mod. So index % cols will give you the column.

If you are given a 2d index and want to convert back to 1d, it is just the reverse.

Say we are given the index [1][1]. We saw above that this is actually index 5 on a 1d list.

The [1] (row) says that we are on the first row. What this means is that we crossed 4 columns (passed the 0th row), and are now on the first row. So, we know that our answer will consist of row_index * num_cols

After that, the [1] (col) just means that we have moved this much ahead from the start of the row. So the formula becomes (row_index * num_cols) + col_index

If it was [1][0], this means that we are on the first row, and have not moved up any column. Similarly, [1][3] means first row, and moved to 4th col.

[dadingchen]

midpoint/columns give row numbers because it is basically computing how many full columns can you get. For example, in the video, 4 columns make one row. So midpoint/column basically is calculating how many groups of 4 columns you can get which in turn is row number since each row has 4 columns. And it is obvious that mid*columns would give you column number because after computing the row number after division all it left is just the not completed columns for the matrix which is the column number.

[vaibhavgupta]

I was truly missing the catch to compute mid-Point! Thanks Bro! Great work.

[alpishjain]

great explanation!I always look forward to this channel whenever i'm stuck.

[tasneemayham]

THIS IS THE BEST VIDEO!!!! I was soo engrossed especially when you were explaining!!

[samuelvalentine]

This is my own solution that i came up with in 30 mins.. I haven't tried it on leetcode this

def find_in2(lst: list, number: int):
left = 0
right = len(lst) - 1

while left <= right:
mid = (left+right) // 2
if number in lst[mid]:
return True
elif number > lst[mid][0] and number < lst[mid][-1]:
return number in lst[mid]
if number > lst[mid][-1]:
left = mid + 1
else:
right = mid - 1

return False

It compares the left most and right most integer since each row is sorted

[pandupvpk]

lol..loved the last midpoint explanation!!

[hamoodhabibi]

Okay, how i understood it in words
matrix_mid = matrix[mid // col][mid % col] is

mid // col == the number of rows we have completed
mid % col == the number of extra cells we have left (which is our cols)

[tonytony]

This is why: mid_point = left + (right - left)/2 = (right - left)/2
left + (right - left)/2
= (2left + right - left)/2
= (right - left)/2

[yitingg]

Thank you for taking the time to really trying to explain it Nick, appreciate it!

[anirbanchakraborty]

Hey nick, can you tell me the intuition behind when to choose while(left<=right) and when to choose while(left<right) in. binary search?

[munishmisra]

It should be :
int cols = matrix[0].length;
int rows = matrix.length;

All test cases will be passed.

[daveB]

Could someone quickly explain why we set:

right = midpoint +1
left = midpoint -1

Specifically why we +1 and -1?

Thanks

[vishalsinghpanwar]

how to get this intuition of using [mid%columns] and have never thought of idea how to get this idea/intuition when we come across such questions?

[NaserMohdBaig]

Absolute genius! Thanks for this amazing explanation. I don't know Java but understood everything you said, thanks to your narration.

[glenfernandes]

while doing Binary search I am confused as to when to use:
1) left <= right, left = mid + 1, right = mid -1
2) left < right, left = mid +1, right = mid
Please help clear my doubt. Thanks.

[triplestrikee]

Great explanation! Liked the solution. The part converted the regular midpoint to the matrix position is very smart, make the problem very close to the "regular" binary search. Thanks a lot.

[jacobl.]

"Your brain will work better if you eat healthy"
Nick: 0:13

[ayushgoyal]

it doesnt pass many test cases
can you explain why it is so?