Blind 75 - problem 12 : Search a 2D Matrix

Problem Statement:

Search a 2D Matrix

Given an m x n matrix matrix and a target value target, write a function to search for target in matrix. The matrix has the following properties:

1. Integers in each row are sorted from left to right.
2. The first integer of each row is greater than the last integer of the previous row.

You need to implement the function:

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

Optimal Approach:

The most efficient way to solve this problem is by treating the 2D matrix as a 1D sorted array. This approach can be solved using Binary Search in O(log(m * n)) time, where m is the number of rows and n is the number of columns.

Steps:

1. Start by performing a binary search on the rows.
2. Once the correct row is found, perform a binary search on the elements within that row.

LeetCode-Compatible Code Implementation:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        
        int low = 0, high = m * n - 1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int midValue = matrix[mid / n][mid % n];
            
            if (midValue == target) {
                return true;
            } else if (midValue < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        
        return false;
    }
};

Step-by-Step Explanation of Code:

1. Initialize variables: m is the number of rows and n is the number of columns.
2. Set up the binary search range: low starts at 0 and high starts at m * n - 1 (the last element in the flattened array).
3. Binary Search loop:
   • Calculate the middle index mid.
   • Convert mid into a 2D matrix index by dividing by n for the row and taking the remainder for the column.
   • Compare the value at matrix[mid / n][mid % n] with the target.
4. Adjust the binary search bounds: If the target is less than the current value, move the high pointer to mid - 1; if greater, move the low pointer to mid + 1.
5. Return the result: If the target is found, return true. Otherwise, return false.

Dry Run / Execution Steps:

Let’s dry run the algorithm with a sample input.

Input:

matrix = [
  [1, 4, 7, 11],
  [2, 5, 8, 12],
  [3, 6, 9, 16],
  [10, 13, 14, 17]
]
target = 5

Step-by-Step Execution:

1. Initialize low = 0, high = 15 (because m * n = 4 * 4 = 16).
2. Compute mid = (0 + 15) / 2 = 7.
   • matrix[7 / 4][7 % 4] = matrix[1][3] = 12.
   • Since 12 is greater than 5, update high = 6.
3. Compute mid = (0 + 6) / 2 = 3.
   • matrix[3 / 4][3 % 4] = matrix[0][3] = 11.
   • Since 11 is greater than 5, update high = 2.
4. Compute mid = (0 + 2) / 2 = 1.
   • matrix[1 / 4][1 % 4] = matrix[0][1] = 4.
   • Since 4 is less than 5, update low = 2.
5. Compute mid = (2 + 2) / 2 = 2.
   • matrix[2 / 4][2 % 4] = matrix[0][2] = 7.
   • Since 7 is greater than 5, update high = 1.
6. At this point, the binary search terminates.

Output: The output will be false.

Alternative Approaches & Why Not?

1. Brute Force: Iterate over each element in the matrix. This would take O(m * n) time, which is inefficient.
2. Sorting: You could flatten the matrix and sort it, but this would take O(m * n log(m * n)) time, which is less optimal.
3. Dynamic Programming: Not necessary for this problem, as a simple binary search is enough.
4. Two Pointers: A two-pointer approach might work, but binary search is more efficient.

Best Solution & Why It’s Best:

The binary search approach is the most efficient, achieving O(log(m * n)) time complexity and O(1) space complexity. It's optimal because we leverage the sorted nature of the matrix to reduce the search space exponentially.

Approach	Time Complexity	Space Complexity
Brute Force	O(m * n)	O(1)
Sorting	O(m * n log(m * n))	O(m * n)
Binary Search	O(log(m * n))	O(1)

Complexity Analysis:

• Time Complexity:

  • Brute Force: O(m * n)
  • Sorting: O(m * n log(m * n))
  • Binary Search: O(log(m * n))

• Space Complexity:

  • Brute Force: O(1)
  • Sorting: O(m * n)
  • Binary Search: O(1)

Conclusion:

The binary search method is the best approach for this problem due to its optimal time complexity and space efficiency. Similar problems that might help practice this approach include:

• Search in Rotated Sorted Array
• Find Minimum in Rotated Sorted Array