Search a 2D Matrix

Patrick Leaton

Published: June 13, 2021, 11:12 a.m.

Problem Description

Write an efficient algorithm that searches for a value in an m x n 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
-10^4 <= matrix[i][j], target <= 10^4

The description was taken from https://leetcode.com/problems/search-a-2d-matrix/.

Problem Solution

#O(Log(N*M)) Time, O(1) Space

class Solution:

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:

rows, cols = len(matrix), len(matrix[0])

left, right = 0, rows*cols-1

if rows == 0 or cols == 0:

return False

while left <= right:

mid = (left+right)//2

mid_val = matrix[mid//cols][mid%cols]

if mid_val == target:

return True

else:

if mid_val < target:

left = mid + 1

else:

right = mid - 1

return False

Problem Explanation

Here we have a sorted array, a two-dimensional array but an array nevertheless. Within that array, we are looking for a single, specific value. That lets us know that we can probably use a binary search.

This binary search will follow a traditional template in which we will set left and right pointers to the first and last positions of the matrix, respectively. We will then take a mean index of these two values at the beginning of each iteration, and we will compare that mean element to the target. If the mean value is greater, then we can move the left pointer past the mean index and eliminate the left half of the current search space. If the mean value is less, then we can move the right pointer before the mean index and eliminate the right half of the current search space.

The tricky part of this question is calculating the mean indices, so we'll explore that in a bit.

Let's start by calculating how many rows and columns we have, this will be important for later.

rows, cols = len(matrix), len(matrix[0])

Next, let's set our left pointer to the first cell of the matrix and our right pointer to the last.

left, right = 0, rows*cols-1

If we have zero rows or zero columns, we will have a matrix of size zero since the product of anything multiplied by zero will be zero.

If we have no matrix, we can't find any target.

if rows == 0 or cols == 0:

return False

Next, we will create our binary search algorithm.

Same as most binary search algorithms, we will continue to search the array until the left and right pointers have overlapped, meaning we still have a search space greater than size zero.

while left <= right:

In each iteration, we will calculate a mid pointer that will be the mean of the left and right pointers.

mid = (left+right)//2

Here is the tricky part of the question.

We will need to actually grab the mid element to compare to the target. This is the same as a normal binary search, we abstract the left and right pointers to indices and only compare the mid element to the target.

However, we are searching within a two-dimensional array so we can't calculate a two-dimensional coordinate from two one-dimensional coordinates. Meaning, we can't just say "left is zero and right is five, so our mean element is matrix[3]."

Let's draw this out since this will get complicated without a visualization. Let's use the matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]], and the target of 3.

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

We'll have our left pointer initially at the first cell, zero, and our right at the last cell, eleven. Remember, arrays start from zero.

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

That means our mid pointer will be five, which would be element eleven. Again, starting from zero.

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

How do we grab that eleven to compare against the target value?

We can do this by how many rotations we need to perform when scanning a row.

Let's grab the row.

A row is going to be made up of columns. A row of size four will be made up of four columns.

We divide the mid pointer, five, by how many columns we have, four. We get one. That is because once we get to the fourth column, we will have to rotate around once, or else we will go out of bounds. When rotating rows through columns, we would drop down to the next row each time we move past the last column.

Let's grab the column.

Again, a row is made up of columns so we can count columns by moving through a row.

We will use the modulo operator to keep the remainder from dividing the mid pointer, five, by how many columns we have, four. We get a remainder of one. That is because once we get to the fourth column, we will have to rotate around once, or else we will go out of bounds. When rotating columns through columns, we would just end up back at the first column of the row each time we move past the last column.

So now we have established that within a two-dimensional array, matrix[5] would translate to matrix[1,1].

mid_val = matrix[mid//cols][mid%cols]

Next, we will get that mid value and compare it to the target.

If they are equal, we will return true since we found the target.

if mid_val == target:

return True

Otherwise, if the mid value is less, we will move our left pointer one past the mid cell.

else:

if mid_val < target:

left = mid + 1

If the mid value is greater, we will move our right pointer one before the mid cell.

else:

right = mid - 1

If we have reduced the search space to zero from our left and right pointers overlapping, we will return false since we searched everywhere and didn't find the target.

return False