Search a sorted 2D Matrix

Problem

You are given an m x n integer 2D array matrix with the following properties:

• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if it is present in the matrix, return false otherwise.

Input

int matrix[m][n], int target

Output

true if target is present in the matrix. false otherwise.

Constraints

• 1 <= m, n <= 300
• -104 <= matrix[i][j], target <= 104

Sample Input

4x4 Matrix, target = 33

Sample Output

true

Solution

Stepwise Linear Search Approach (O(m+n) time complexity)

The given algorithm starts from the top-right corner of the matrix and navigates towards the target in a step-wise fashion.

• If the current element is equal to the target, we’ve found our value and return true.
• If the target is greater than the current element, we move down (increment i) to the next row, as the current row does not contain the target (and since the current element is the largest in this row).
• If the target is less than the current element, we move to the left (decrement j) to the previous column, as the current column does not contain the target (and since the current element is larger than the target).

The process continues until we either find the target (in which case we return true), or we exhaust all rows (i exceeds m-1) or columns (j drops below 0), in which case we return false indicating the target does not exist in the matrix.

Code Implementation

    bool searchMatrix(vector<vector<int>>& matrix, int target) {

        int m = matrix.size();
        int n = matrix[0].size();
        
        int i=0, j=n-1;
        
        while (i<m && j>=0) {
            if (target == matrix[i][j]) {
                return true;
            } else if (target > matrix[i][j]) {
                i++;
            } else {
                j--;
            }
        }

        return false;
    }

The Stepwise Linear Search method navigates the matrix in a step-wise fashion, starting from the top right and moving down or left based on the comparison with the target. In the worst-case scenario (when the target is not in the matrix or lies in the bottom left corner), this method may have to traverse all the rows and columns once. Thus, the time complexity is O(m + n), where m is the number of rows and n is the number of columns.

Binary Search Method (O(log(mn)) time complexity)

We can apply Binary Search to this problem, but we’ll need to make some modifications to fit the 2D nature of the problem. We’re not dealing with a simple linear array but a 2D matrix. The idea is to treat the 2D matrix as a 1D array. This method has the limitation that it will work for only those matrix where the first integer of each row is greater than the last integer of the previous row. So it won’t work for a row-wise and column-wise sorted matrix like this:

while Stepwise Linear Search will work in this case also.

How to convert 2D Matrix to 1D Matrix in O(1) space?
When we treat a 2D matrix as a flattened 1D array in order to apply the Binary Search, the middle element index (mid) we calculate, is based on the 1D array. However, to access the corresponding element in the original 2D matrix, we need to convert this 1D index back into 2D indices.

Finding mid value in matrix[i][j]:
If we have n columns in our original 2D matrix, then every n elements in our 1D array constitutes a single row from our 2D matrix. Hence, we can find, which row an element in the 1D array would have been in the 2D matrix, by doing an integer division mid / n. This gives us the i or row value.

Similarly, to find the column index j, we can calculate the remainder when mid is divided by n (i.e., mid % n). This is because as we move from left to right across a row in the 2D matrix, each element is just the next element in the 1D array, until we hit the end of a row and jump to the start of the next row.

Consider this:

Let m = 3, n = 4,
matrix = [
    [1,  3,  5,  7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
]

Let’s flatten this matrix into a 1D array:

flattened = [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 50]

In our binary search, let’s say we’ve calculated mid to be 5. This means we’re looking at the 6th (0-based indexing) element in the flattened array, which is 11. But where is this in our original 2D matrix?
We can calculate the 2D indices as follows:

i = mid / n = 5 / 4 = 1 
j = mid % n = 5 % 4 = 1

So, in our original 2D matrix, matrix[1][1] is the value 11, which is the same as the 6th element in our flattened array.

Code Implementation

bool searchMatrix(vector<vector<int>>& matrix, int target) {

    if(matrix.empty() || matrix[0].empty()) {
        return false;
    }
        
    int m = matrix.size();
    int n = matrix[0].size();
    int left = 0;
    int right = m * n - 1;
        
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int mid_value = matrix[mid / n][mid % n];
            
        if (mid_value == target) {
            return true;
        } else if (mid_value < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
        
    return false;
}

The Binary Search approach treats the 2D matrix as a flattened 1D array and performs a binary search on it. Binary search has a time complexity of O(log n), where n is the total number of elements. In the context of this problem, the time complexity is O(log(mn)), where m is the number of rows and n is the number of columns in the matrix. This complexity arises from the fact that with each comparison, we eliminate half of the remaining elements from consideration.