Search a 2D Matrix - Leet Code 74 - TypeScript
Vložit
- čas přidán 9. 07. 2024
- This problem is a great way to understand the n * lg n time complexity as it combines binary search with a for loop.
--------------------------------------------------
Recommended Udemy courses
--------------------------------------------------
Understanding TypeScript: tinyurl.com/9wz6fp7k
NodeJS - The Complete Guide: tinyurl.com/3z4ehtpm
React - The Complete Guide: tinyurl.com/2t6v5yeu
Angular - The Complete Guide: tinyurl.com/4h5rmpsj
DSA TS Playlist: • Data Structures and Al...
00:00-03:02 - Understanding the problem
03:03 - Solving the problem
This question needs to be solved in log(n*m), your solution however was m log(n). Would it not make more sense if we were to apply binary search on the columns first?
The reason this answer gets accepted and is top 75% is because the tests are likely not handling matrices as they approach an infinitely large number of rows and columns. Meaning that things run fine for say 4*4 row by column. You are right though. I would need to think about the actual implementation as I have just used my previous work in context of this series, but I would be inclined to treat the 2d array as a 1d array since it is sorted, then perform binary search on the n*m cells making it lgnm