LeetCode Search A 2D Matrix Solution Explained - Java
ฝัง
- เผยแพร่เมื่อ 11 ก.ย. 2024
- The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.d...
AlgoCademy - algocademy.com...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/...
Follow Me on X/Twitter - x.com/nickwhit...
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nick....
Become A Member - / @nickwhite
#coding #programming #softwareengineering
The way I understood midpoint_element = matrix[midpoint/columns][midpoint%columns] 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.
almost instantly clicked, thank you.
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.
yo thanks for the explanation
well explained
thank you
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.
Sorry it should be midpoint%columns for columns numbers
Thanks for the explanation man!!! I actually couldn't understand when nick explained. I could understand this better now with your explanation.
I was truly missing the catch to compute mid-Point! Thanks Bro! Great work.
lol..loved the last midpoint explanation!!
great explanation!I always look forward to this channel whenever i'm stuck.
THIS IS THE BEST VIDEO!!!! I was soo engrossed especially when you were explaining!!
No need to buy premium; we nick for solutions.....
Thank you for taking the time to really trying to explain it Nick, appreciate it!
Hey nick, can you tell me the intuition behind when to choose while(left
not sure if its correct, but when you need to "find the minimum in rotate sorted" then its while(left
Please when can i use while left + 1 < right or while left
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 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
how to get this intuition of using [mid%columns] and [mid/columns]............could have never thought of this.........any idea how to get this idea/intuition when we come across such questions?
Could someone quickly explain why we set:
right = midpoint +1
left = midpoint -1
Specifically why we +1 and -1?
Thanks
After some more debugging i can answer my own question (posting on here in case it's useful for anyone else) - we've already verified the midpoint is not the target element, so we're excluding it from the right/left bounds on the next iteration of the loop.
Dude you are a genius 😳🙏🏻
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)
amazing man, thank you so much
Absolute genius! Thanks for this amazing explanation. I don't know Java but understood everything you said, thanks to your narration.
This is why: mid_point = left + (right - left)/2 = (right - left)/2
left + (right - left)/2
= (2left + right - left)/2
= (right - left)/2
"Your brain will work better if you eat healthy"
Nick: 0:13
Please when can i use while left + 1 < right or while left
while doing Binary search I am confused as to when to use:
1) left
Hi, the comparison is not between left and right, it is comparing the mid to the target, if the mid number is larger than the target, it means the target exists in the section between 0 to mid because the array is sorted. Hopefully my explanation will be helpful. : )
it doesnt pass many test cases
can you explain why it is so?
Please when can i use while left + 1 < right or while left
It should be :
int cols = matrix[0].length;
int rows = matrix.length;
All test cases will be passed.
very clever thank you
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.
This dude is hot af. Just love his explanation so much damn.
Does the solution of 2x2 matrix? for example [[1,4],[2,5]] and element to find is 2
Hey Madan I was stuck on this too, looks like both of us were working on Search a 2D Matrix II not Search a 2D matrix which requires a slightly different approach with O(m+n) time complexity
This solution is for Q.74 and will not work for Q.240. 240 has a slight difference.
Why thumbs down ?
Great work
great.
Thanks Thanks thanks thanks thanks thanks thanks thanks thanks thanks thanks thanks thanks thanks thanks
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;
}
}
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int row=matrix.length; if(row==0) return false;
int col=matrix[0].length;
for(int i=0;i
good, but not fast enough
it is a brute force solution
This is a N^2 solution no? Nick's answer is O(log mn)
Please when can i use while left + 1 < right or while left
[[1,4],[2,5]]
2
Code couldn’t pass the above test case.
just check, while(left
Wrong input
No
For anyone who is getting the same error, this logic works for search a 2d matrix question, but not for search for 2d matrix 2.
Binary search only works on a sorted list. Your input list is not sorted.