Search a 2D Matrix medium

Problem Statement

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The 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.

You should return true if the target value exists in the matrix, and false otherwise.

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

Steps

1. Treat the matrix as a sorted list: Because of the properties of the matrix (sorted rows and increasing first element of each row), we can treat the entire matrix as a single sorted list.

2. Binary Search: Perform a binary search on this "sorted list". We'll need to calculate the index appropriately to access the correct row and column.

3. Midpoint Calculation: The midpoint index will tell us the row and column of the element we're checking.

4. Comparison and Adjustment: Compare the target value with the element at the midpoint. If they match, return true. If the target is smaller, adjust the search space to the lower half; otherwise, adjust to the upper half.

5. Base Case: If the search space is exhausted (left > right), return false.

Explanation

The key insight is to leverage the sorted nature of the matrix to efficiently search. Instead of iterating through the matrix, we use binary search, which has logarithmic time complexity. We need to map the single-dimensional binary search index to the corresponding row and column in the 2D matrix.

Code

function searchMatrix(matrix: number[][], target: number): boolean {
    const m = matrix.length;
    const n = matrix[0].length;
    let left = 0;
    let right = m * n - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const row = Math.floor(mid / n);
        const col = mid % n;
        const value = matrix[row][col];

        if (value === target) {
            return true;
        } else if (value < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return false;
};

Complexity

• Time Complexity: O(log(mn)), due to the binary search. This is significantly faster than a linear search O(mn).
• Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size.