74. Search a 2D Matrix — LeetCode(Python)

I got you!

Problem:

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

Solution:

1. Double binary search —

# find x < target in matrix[i][0]
l, r = 0, len(matrix) - 1
while l <= r:
    row = (l + r) // 2
    if matrix[row][-1] < target:
        l = row + 1
    elif matrix[row][0] > target:
        r = row - 1
    else:
        break
                
if l > r:
    return False
        
# then binary search in matrix[x][:]
l, r = 0, len(matrix[0]) - 1
while l <= r:
    mid = (l + r) // 2
    if matrix[row][mid] == target:
        return True
    elif matrix[row][mid] < target:
        l = mid + 1
    else:
        r = mid - 1
                
return False

Explanation —

First, we figure out which row to search the target value in. And the, we search our number in that row.

We can use binary search for both the operations.

We know that each row is sorted. Also, the matrix is sorted. So the last element of each row is smaller than the first element of the next row.

Using these properties of our matrix, we can say that the set of first elements in each row will be in ascending order.

For example, the matrix:

[[1,3,5,7],[10,11,16,20],[23,30,34,60]]

has it’s [0][0], [1][0] and [2][0] in ascending order.

We perform binary search on the set of first elements in each row to find which row our target value is stored in.

• We find the mid row.
• If the last element in this row is less than target, we move our l pointer to the next row.
• Else if, the first element in a row is greater than target, we move our r pointer to the previous row.
• If neither of these evaluate to True, it means that we have found the valid row, so we break out of the while loop.

Maybe, we created an invalid condition so our while loop terminated. Therefore, we return False, if l > r.

Now that we have found our valid row, we perform binary search on that row.

And then, we return True or False, depending on whether we found the target value.

Time and Space Complexity —

We have performed binary search twice — first on the first element of each row, and then on the valid row.

Also, we have used only a constant amount of extra space.

Thus, if m is the number of rows and n is the number of columns in the matrix,

Time Complexity: O(log(m) + log(n)) or O(log(mn)) [quick maff]

Space Complexity: O(1)

2. Performing Binary Search On The Entire Matrix —

rows, cols = len(matrix), len(matrix[0])
l, r = 0, (rows * cols) - 1
        
while l <= r:
            
    mid = (l + r) // 2
            
    num = matrix[mid // cols][mid % cols]
            
    if num == target:
        return True
            
    elif num < target:
        l = mid + 1
                
    else:
        r = mid - 1
                
return False

Explanation —

We perform binary search on the entire matrix, since we know that it is strictly sorted.

We initialize two pointers on two ends of the matrix — the first and the last element.

Then, we calculate the mid value. This is tricky.

We have found a number mid that tells us, though cryptically, which number in the element we have to check for. But it does not provide us with the exact index to that number.

We use math here.

Say, we have the same example matrix,

[[1,3,5,7],[10,11,16,20],[23,30,34,60]]

This matrix has 3 rows and 4 columns and a total of 12 elements. So, our left and right pointers were set on 0 and 11.

We calculate our mid to be (l + r) // 2.

So, now we get mid = 5.

How do we find what index in the matrix has the 5th element while traversing classically — first row-wise, then column-wise?

When we divide this mid value by the number of columns, we are essentially dividing the number of column elements that have been traversed , by the number of columns — which is the number of rows traversed. [mid / columns]

The remainder of this operation tells us how many column elements are left — which tells us the column number we need to check. [mid % columns]

Since, 5 / 4= 1 and 5 % 4= 1. Thus, our mid element is at matrix[1][1].

After finding this information, we continue with the standard binary search algorithm.

Time and Space Complexity —

Since this is a standard binary search procedure, our time and space complexities are the same.

Thus, if m is the number of rows and n is the number of columns in the matrix,

Time Complexity: O(log(m) + log(n)) or O(log(mn)) [quick maff]

Space Complexity: O(1)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏