Search A 2d Matrix - Leetcode Solution

Problem Statement:

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

1. Integers in each row are sorted from left to right.
2. 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

Solution:

To solve this problem, we can use binary search. We can consider the matrix as a single sorted array and perform binary search on it. To achieve this, we need to map a single index to an element in the matrix. We can map an index i to a row j and a column k using the following formulas:

j = i // n k = i % n

Where n is the number of columns in the matrix.

We can perform binary search on the single sorted array using the following steps:

1. Initialize the low pointer to 0 and the high pointer to m x n - 1.
2. While low <= high: a. Compute the mid index as (low + high) // 2. b. Map the mid index to a row and a column using the above formulas. c. Compare the element at the mapped row and column with the target: i. If the element is equal to the target, return True. ii. If the element is less than the target, set low to mid + 1. iii. If the element is greater than the target, set high to mid - 1.
3. If the target is not found, return False.

The time complexity of this algorithm is O(log(m x n)) since we are performing binary search on a single sorted array of size m x n. The space complexity is O(1) since we are using constant extra space.

Here is the Python implementation of the above algorithm:

def searchMatrix(matrix, target): if not matrix: return False

m, n = len(matrix), len(matrix[0])
low, high = 0, m * n - 1

while low <= high:
    mid = (low + high) // 2
    i, j = mid // n, mid % n
    
    if matrix[i][j] == target:
        return True
    elif matrix[i][j] < target:
        low = mid + 1
    else:
        high = mid - 1

return False

Testing:

We can test the above implementation using the examples provided in the problem statement:

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

target1 = 3

assert searchMatrix(matrix1, target1) == True

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

target2 = 13

assert searchMatrix(matrix2, target2) == False

Both of the assertions passed, which means that the implementation is correct.

1