LeetCode Solution 74 - Search a 2D Matrix

Problem Statement

Given an m x n matrix where each row is sorted in ascending order and the first integer of each row is greater than the last integer of the previous row, write an algorithm that searches for a target value efficiently.

Example:

Input: matrix = [[1, 3, 5, 7],
                 [10, 11, 16, 20],
                 [23, 30, 34, 60]], target = 3
Output: true

Optimal Approach: Binary Search

We can treat the 2D matrix as a flattened sorted array and apply Binary Search. By mapping a 1D index to a 2D matrix, we can perform a logarithmic search in O(log(m * n)) time complexity.

LeetCode-Compatible C++ Solution:

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

Step-by-Step Explanation

1. Flatten the matrix: Treat the 2D matrix as a 1D sorted array.
2. Binary search: Compute the middle index and map it to matrix[mid / n][mid % n].
3. Check conditions: If midElement matches target, return true. Otherwise, adjust left or right.
4. End condition: If left exceeds right, return false.

Dry Run Example

Input:

matrix = [[1, 3, 5, 7],
          [10, 11, 16, 20],
          [23, 30, 34, 60]], target = 11

Execution Steps:

1. left = 0, right = 11, mid = 5, midElement = 11
2. midElement == target → Return true

Alternative Approaches

Brute Force (O(m * n))

• Iterate through every element in the matrix.
• Inefficient for large matrices.

Row-wise Binary Search (O(m * log n))

• Perform binary search in each row separately.
• Better than brute force, but worse than treating the matrix as a 1D array.

Best Solution & Why?

Approach	Time Complexity	Space Complexity
Brute Force	O(m * n)	O(1)
Row-wise Binary Search	O(m * log n)	O(1)
Flattened Binary Search	O(log(m * n))	O(1)

Why is Flattened Binary Search Best?

• Uses logarithmic search over all elements.
• Reduces problem to standard Binary Search.
• O(log(m * n)) is optimal compared to O(m * log n).

Complexity Analysis

• Time Complexity: O(log(m * n))
• Space Complexity: O(1)

Conclusion

• Flattening the matrix and using Binary Search is the most efficient approach.
• This method ensures logarithmic time complexity with minimal space usage.
• Further practice: Try solving similar problems like Search a 2D Matrix II.

Stay tuned for more optimized solutions! 🚀