Search a sorted Matrix (Both Rows and Columns are Sorted) | Coding Interview | Searching

This problem has been asked by Amazon, Facebook (Meta), and Microsoft.

For a better grasp, try to code the solution yourself. If you get stuck at any point, I have provided the answer and its code explanation.

This problem is part of the 30 days preparation plan for coding interviews.

Description

You are given a matrix of integers where each row and column is sorted. Search for a target integer.

Example 1:
Input:
      1   4   8   10
A =   3   9   13  17
      6   11  16  21
      9   15  23  34

target: 16

Output: True
Explanation: 16 can be found int the matrix at row number 3 and column number 3.

Example 2:
Input:
      1   4   8
A =   3   9   13
      6   11  16

target: 10

Output: False
Explanation: 10 is not present in the matrix.

Brute Force Solution

The naive way will be to visit each cell of the matrix, making the complexity O(mn) where m is the number of rows and n is the number of columns. We can use two for loops to traverse each cell; the outer for loop can iterate through rows and inner through columns.

Efficient Solution

We know that our rows and columns are sorted, hence just like binary search, we should try to think of a solution that eliminates or reduces our search space at every step.

Let’s say we want to search for the number 11. Notice that if our target is less than an item in the matrix (say 13), we can eliminate the rest of the column and all the columns on the right as they are greater than the current item (13). We move to the left cell to get a smaller item (9).

If our target (say 16) is more than an item in the matrix (say 10), then we move to the next row with a larger value (17) as rows and columns are sorted. Following this approach, we will find the target if its present in the matrix.

We start our search from the top right corner and move toward the bottom left corner till we find our target.

Since 10 is smaller than 16, we can see that all elements of the current row are smaller.

Hence, we eliminate the current row and move to the next row containing a larger element.

Now, 17 is greater than our target, and since columns are sorted, all the elements below 17 are also greater.

We will remove the current column from our search space and move to the left column in the same row with a smaller value, which is 13.

Here 13 is again smaller than 16, so we will eliminate the current row and continue our search in the next row.

This way, we find 16 in a matrix with sorted rows and columns.

Code

Output:

True
False

Time & Space Complexity

Time: If you notice, you will see that we are eliminating one complete row or column after every step. Hence, we complete our search after at most (m + n) steps where n is the number of rows and m is the number of columns. Time complexity is O(m+n).

Space: We are not using any extra memory for this approach. Hence, the space complexity is constant.

Thanks for your time.

If you liked what you just read, a clap 🤗🤗🤗would be highly appreciated. You can be generous in clapping; it shows me how much you enjoyed this story. And if you didn’t like it? Please do comment😋!

P.S.: If you like this uninterrupted reading experience on this beautiful platform of Medium.com, consider supporting the writers of this community by signing up for a membership HERE. It only costs $5 per month and supports all the writers.

You can also follow me HERE to get updates on the stories that I write.