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 is found in the matrix, otherwise return false.

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 leverage the sorted nature of the matrix. We can treat the matrix as a sorted list. Instead of doing a linear search, we can use a binary search approach.

1. Treat the matrix as a 1D array: Imagine flattening the matrix into a single sorted array. The index of an element (row, col) in the flattened array would be row * numCols + col.

2. Binary Search: Perform a binary search on this imagined 1D array. The lower bound is 0, and the upper bound is rows * cols -1.

3. Midpoint Calculation: In each iteration of the binary search, calculate the midpoint index.

4. Mapping back to 2D coordinates: Convert the midpoint index back to row and column coordinates using integer division and modulo operations.

5. Comparison: Compare the element at the calculated row and column with the target value. Adjust the lower or upper bound of the binary search based on the comparison result.

6. Return Value: If the target is found, return true; otherwise, return false after the binary search completes.

Explanation

The algorithm's efficiency comes from the binary search. A binary search has a time complexity of O(log n), where n is the number of elements. In this case, n is the total number of elements in the matrix (rows * cols). This is significantly faster than a linear search which would have O(rows * cols) time complexity.

The conversion between the 1D index and 2D coordinates is straightforward and doesn't add significant computational overhead.

Code

public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        int rows = matrix.Length;
        if (rows == 0) return false;
        int cols = matrix[0].Length;

        int low = 0;
        int high = rows * cols - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // Avoid integer overflow
            int row = mid / cols;
            int col = mid % cols;

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

        return false;
    }
}

Complexity

• Time Complexity: O(log(m*n)), where 'm' is the number of rows and 'n' is the number of columns in the matrix. This is due to the binary search.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size. The space used by the input matrix itself is not considered in space complexity analysis.