[Solution]Problem 52:Search 2D Matrix[Microsoft]
I'm sure this solution will be quite surprising for a quite a few of you.
To learn more about the newsletter, check our detailed About Page + FAQs
To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.
Recommend this publication to Substack over here
Are you ready for this,
Make sure you really understand the solution to this upcoming problem. This problem is special because solving doesn’t really require much special knowledge. Just some logic and the teensiest bit of basic algebra. What makes this problem is not how hard the solution is, but that spotting what to do requires some insight. I love problems like this because they are great for testing your problem-solving skills.
This problem can be found as problem 74. Search a 2D Matrix on Leetcode.
Problem
Write an efficient algorithm that searches for a value target
in an m x n
integer matrix matrix
. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
You can test your solution here
[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or by Email:
Venmo: httount.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Or you can sign up for a Free Trial Below. Since the reception has been great, I got a special offer for y’all. You can get this newsletter free for 2 months, just by using the button below-
Step 1: Working on the Brute-Force
Since this problem is pretty straightforward, we can get into the brute-force solution. As we talked about many times in my newsletter, one of the most impactful ways to obtain efficient solutions is to take the brute force solution and cut-down from there.
Our brute force will look relatively simple. We’ll traverse through the matrix, and check through the cells one by one. We’re basically conducting a linear search, on the entire 2D array. The time complexity required would be O(m*n) since we need to check every value. We’d also be using no extra space.
How can we improve this? Obviously, we haven’t really used the properties of the matrix in any way. That would be a good next step. Let’s take a look and see what insights we can come up with.
Step 2: Looking at the matrix rules
We’re given 2 special rules about the matrix-
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
Combined, this tells us something interesting- this matrix is sorted in the row-major order. This term might be new to you, but take a look below, and you will see this is typically the order we use when traversing 2D arrays using nested for loops. Make sure you flex this terminology in your interview to gain those sweet brownie points.
Now, most solutions online use this insight and do very little with this. They run binary search twice, once to identify the correct row and another to then get the right column. This isn’t bad, but it’s a really clunky way of doing things. The code you’ll have to run will be much longer than necessary. What I’m going to share with you is much simpler to code up and requires only a little bit more work to come up with. If you will be working with matrices a lot (most professional software devs), then knowing this technique is a must.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.