Sorted Matrix Search
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 down any column are always increasing.
You will search for an item in the matrix, and return its row and column index 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.
Breakdown
Approach and test strategy
Eliminate a row or column using both matrix orderings
Read the approach, boundary cases, and complexity
Rows and columns are ordered, but the flattened matrix need not form one globally sorted sequence. Start at the top-right corner: if its value is too large, discard that column; if too small, discard that row. Each comparison eliminates candidates that cannot contain the target under the row and column order rules. Return the row and column, or [-1, -1] when absent.
Cases to check
- Test an empty row and a missing target.
- Place targets at the top-left and top-right corners.
- Use a matrix where the first value of a row is smaller than the last value of the previous row, exposing an invalid flattened binary-search assumption.
Cost model
The staircase path crosses at most r rows and c columns, giving O(r + c) time and O(1) auxiliary state. The matrix's ordering preconditions are part of that argument.
Programming languages for this lesson
Starter code and reference implementations are available in:
The editor shows which of these languages can run on this deployment.
Validate My Answer
In a brute force approach, you could search along all
rrows andccolumns. 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 and conquering. For example, you could iterate down all
rrows and do a binary search on allccolumns. If you're brave, you could also just perform a binary search on rows and columns 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
randcare 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.
Sorted Matrix Search
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 down any column are always increasing.
You will search for an item in the matrix, and return its row and column index 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.