Search in a Sorted Matrix | Skilled.dev
Interview Question

# 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.

``````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
``````

## Breakdown

1. In a brute force approach, you could search along all `r` rows and `c` columns. This would be a O(r x c) brute force solution, so think how you can do better.
2. There are a couple of ways to solve this using binary search or divide and conquering. For example, you could iterate down all `r` rows and do a binary search on all `c` columns. 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.
3. This problem can be solved linearly in O(r + c) time where the `r` and `c` are the row and column lengths, and it needs no additional space O(1).