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.

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

The key to solving this problem efficiently is to treat the matrix as a sorted 1D array. Because the rows and columns are sorted, we can use a binary search approach. Instead of using two separate indices for rows and columns, we'll use a single index that spans the entire matrix.

1. Treat the matrix as a sorted 1D array: Calculate the total number of elements in the matrix (m * n).
2. Binary Search: Perform a binary search on this "virtual" 1D array.
3. Mapping index to row and column: During the binary search, whenever we access an element using the current index mid, we need to convert this index back into row and column coordinates using integer division (mid / n) and modulo (mid % n).
4. Comparison: Compare the element at the calculated row and column with the target value. Adjust the search space (left and right boundaries) based on the comparison result, just like in a standard binary search.
5. Return: If the target is found, return true; otherwise, return false after the binary search completes.

Explanation

The efficiency comes from the binary search. A linear scan would have O(mn) time complexity. Binary search reduces this to O(log(mn)), which is significantly faster for larger matrices. The conversion from the 1D index to row and column coordinates is a constant time operation.

Code

#include <vector>

using namespace std;

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size();
    if (m == 0) return false;
    int n = matrix[0].size();
    int left = 0;
    int right = m * n - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        int row = mid / n;
        int col = mid % n;

        if (matrix[row][col] == target) {
            return true;
        } else if (matrix[row][col] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return false;
}

Complexity

• Time Complexity: O(log(m*n)) due to the binary search.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space.