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.

Given a target value, return true if it is present 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

The key to efficiently solving this problem is to leverage the sorted nature of the matrix. We can treat the matrix as a sorted array. Instead of performing a linear search, we can employ a binary search approach.

1. Treat the matrix as a sorted 1D array: Imagine flattening the matrix into a single sorted array. The index mapping from the 2D matrix coordinates (row, col) to the 1D array index would be index = row * n + col, where 'n' is the number of columns.

2. Binary Search: Perform a binary search on this conceptually flattened array. The lower bound of the search is 0 and the upper bound is m * n - 1.

3. Mapping back to 2D coordinates: During the binary search, when you find a mid index, you need to map it back to the 2D coordinates (row, col) using integer division and modulo operations: row = mid / n, col = mid % n.

4. Comparison and Adjustment: Compare the value at matrix[row][col] with the target.

   • If they are equal, return true.
   • If matrix[row][col] is less than the target, adjust the lower bound of the binary search to mid + 1.
   • If matrix[row][col] is greater than the target, adjust the upper bound of the binary search to mid - 1.

5. Return false: If the binary search completes without finding the target, return false.

Explanation

The algorithm leverages the efficiency of binary search (O(log(mn)) time complexity) to find the target value in a much faster way than a brute force linear search (O(mn) time complexity). The key is the clever mapping between the 1D index used in the binary search and the 2D coordinates of the matrix. This mapping allows us to seamlessly perform a binary search on the conceptually flattened array without actually flattening it, saving space.

Code

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (m == 0) return false;
        int n = matrix[0].length;

        int low = 0;
        int high = m * n - 1;

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

            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)), due to the binary search.
• Space Complexity: O(1), as we are using only a constant amount of extra space.