Sorted Matrix Search
Course launching November 17, 2020
Follow me on YouTube for free coding interview videos.
Users who sign up for the email list will receive an exclusive 75% discount at launch.
Given a sorted matrix of integers, write a function
searchMatrix that returns the
[row, column] index of a
target value if it exists or
[-1, -1] if it does not.
We will define the matrix as being sorted if all the items along any row are always increasing, and all the items along any column are always increasing.
You will search for an item in the matrix, and returns its row and column index in as two items in an array.
If the item does not exist in the matrix, return
-1 for both the row and column index.
The integers in the array are guaranteed to be unique.
const matrix = [ [0, 2, 5, 8, 10], [1, 4, 9, 15, 20], [3, 7, 14, 19, 21], [17, 22, 23, 24, 25], ]; const target = 19; // row // | searchMatrix(matrix, target); // [2, 3] // | // column
Validate My Answer
In a brute force approach, you could search along all
ccolumns. This would be a O(r x c) brute force solution, so think how you can do better.
There are a couple of ways to solve this using binary search or divide an conquering. For example, you could iterate down all
rrows and do a binary search on all
ccolumns. If you're brave, you could also just perform a binary search on rows and columsn simultaneously, but this gets messy quickly. With divide and conquer, you can recursively split the matrix into four sub-matrices.
All of these solutions are on the approximate order of O(n log n) time complexity solutions.
You can do better while also using simpler code.
This problem can be solved linearly in O(r + c) time where the
care the row and column lengths, and it needs no additional space O(1).
To achieve this, you either need to start at the bottom-left or top-right corner and come up with the logic and iterate the matrix from either of those points.