Search in 2D-MATRIX | Leetcode | GFG | C++ | Java | Brute-Better-Better-Optimal

Find DSA, LLD, OOPs, Core Subjects, 1000+ Premium Questions company wise, Aptitude, SQL, AI doubt support and many other features that will help you to stay focussed inside one platform under one affordable subscription. Have a hassle free one stop solution for up-skilling and preparing.

[takeUforward]

Reason behind /c and %c : for every row we have m columns, hence mid/m gives you the row number

.

[dovyraj]

i was asked this question in GOLDMAN SACHS INTERVIEW .

[adarshkumarmaheshwari]

Hello brother, I usually don't comment in YT videos but seeing your work and a improvement I am getting using your SDE and a CP sheet is noticeable. I have not done my UG in computer science but Commerce, managed to get admission in tier 2 college in MSc(IT) course. I am currently studying 8 - 9 hours a day. Your sheets have given me direction and a hope. I am pretty sure I would be able to crack some good companies if I continue to practice like this and you guide like you always do. Thanks for your efforts. Means a lot. Once I have reached at certain point in CP and get a job I desire. I will text you for sure to share my journey with your audience. Thanks.

[riyanshpal]

the gfg version is also present on leetcode by the name "Search a 2D Matrix II"

[Harishiv]

Hey Bro! Really loving this series. Before watching this video, I solved the leetcode question with my own approach where I used 2 binary search functions, one to find the row and another to traverse this row and find the value. Your approach was also really elegant.

[mianto]

great tutorial!
Thanks so much. It must have taken a lot of effort and time to explain everything that smoothly.

[abhishekranjansingh]

This was the best video till now in whole series ❤️❤️🔥🔥

[PriyamF]

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

[wanderer_ankur]

wow man such a cool method !! Keep going strive .. and thanks for helping so many people like me who are just confused what to do and how to prepare for placements :)

[nishantsrivastava]

The last approach was just awesome...great man!!

[HarshKumar-nhbe]

Truly amazing please keep uploading, you are our true mentor. YOU ARE MAKING THE LIFE OF LAKHS OF PEOPLE..
KEEP IT UP!

[somyapratapsingh]

Ur problem solving skills are really top-level
Hats off to u

[jitinkrishnamadineni]

Bro... At 6:57 after while loop u should check a condition if j<0 then return 0 so that we can know element is not present in array.

I thank your patience and efforts bro. I like all your videos. I request you to post videos on graphs very soon .

[perumallayaswanth]

After watching this video, I can't go back without subscribing you.

[hackingforfun]

It is the best video of Array Playlist till now. Keep up doing the great work. Thanks a lot.

[devanshmesson]

At 3:49, Why are we starting our search from top-right corner?
I know it's working for us, but is there any proof of this?


By starting from top-right corner, we have two choices to go:
1.Down (same column, next row)
2.Left (Same row, previous column)
By Going downwards, elements >= current element are present and by Going left, elements <= current element are present.

So, just like binary search we compare the current element with X :
1.if X > current element, go downwards and remove the row where the current element exists.
2.if X < current element, go left and remove the column where the current element exists.
3.f X == current element stop.

Isn't this same as binary search, so understand the "why" part of this approach by relating it with binary search.
We can also start our approach from bottom left corner, it's the same thing.


What will happen if we start our search from top-left corner?
-We will not be able to remove the row/column where the element cannot exist due the condition given, So we have to traverse all rows and columns to find X.

[tanyacharanpahadi]

Blown!!!! I wonder if i can ever think like you .. You are lit bro.

[charushilabhadane]

thank you, whenever I have any doubts your channel has solution for that

[abhinavmishra]

bahot accha bataya h striver bhai...kudos!!!! Nice revision of algos of famous n common problems before scheduled interviews and also, getting the right way of answering in brute-better-optimal way told by you.

[lavanya_m]

WOW! Your final optimal solution for leetcode is brilliant! Thanks a lot for this striver :)