🔍 Problem Summary

You're given a 2D matrix with these properties:

Each row is sorted in ascending order.

The first number of each row is greater than the last number of the previous row.

This makes the entire matrix feel like a flattened sorted array.

Example 1:

matrix =   [[1, 3, 5, 7],
          [10, 11, 16, 20],
          [23, 30, 34, 60]]
target = 16
Output: true
Explanation: 16 is present in row 1, column 2.

Example 2:

matrix = [[1, 3, 5, 7],
          [10, 11, 16, 20],
          [23, 30, 34, 60]]
target = 13
Output: false
Explanation: 13 is not found anywhere in the matrix.

🎯 Goal

Given a target value, determine whether it exists in the matrix.

🧠 Key Insight

You can treat the matrix as one sorted array (like a flat list) and perform binary search across all m * n elements.

✅ Step-by-Step Binary Search Approach

Step 1: Treat the matrix as a 1D sorted array of size m * n

m = number of rows, n = number of columns

Valid indices: 0 to m * n - 1

Step 2: Binary search on virtual 1D array

Let low = 0, high = m * n - 1

While low <= high:

Compute mid = (low + high) // 2

Convert mid to 2D indices:

row = mid // n

col = mid % n

Compare matrix[row][col] with target:

If equal, return True

If less, search right half (low = mid + 1)

If more, search left half (high = mid - 1)

💻 Code in C++

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) / 2;
        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;
}

💻 Code in Java

public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length;
    int n = matrix[0].length;

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

    while (low <= high) {
        int mid = (low + high) / 2;
        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;
}

💻 Code in Python

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    
    m, n = len(matrix), len(matrix[0])
    low, high = 0, m * n - 1
    
    while low <= high:
        mid = (low + high) // 2
        row, col = divmod(mid, n)
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return False

🕒 Time and Space Complexity

Time: O(log(m * n)) — Binary search on the flattened array.

Space: O(1) — No extra space used.

✅ Interview Q&A Based on "Search a 2D Matrix"

🧾 Q1: Can you explain the approach you'd use to search for a target in a sorted 2D matrix?

Answer:

Yes. Since the matrix has two important properties:

Each row is sorted in ascending order.

The first element of each row is greater than the last element of the previous row.

This means the entire matrix can be treated like a flattened sorted 1D array. So, I use binary search on the range from 0 to m*n - 1.
At each step, I map the 1D index to 2D coordinates using:

row = mid // n

col = mid % n

Then I compare the element at that position with the target. If equal, I return true. If less, I move to the right half, otherwise to the left.

This gives me a time complexity of O(log(m * n)).

🧾 Q2: Why is binary search applicable here?

Answer:

Binary search is applicable because the entire 2D matrix can be seen as a sorted linear array 
due to its structure.
Since each row is sorted and the first element of a row is greater than the last of the previous row, it behaves like a sorted array. That lets us perform binary search for efficient lookups.

🧾 Q3: Can you walk me through how you'd convert a 1D index to a 2D matrix index?

Answer:

Yes. If I’m treating the matrix as a 1D array, and n is the number of columns, then:

The row index is mid / n

The column index is mid % n

This way, I can access matrix[row][col] using a single mid index from the binary search.

🧾 Q4: What is the time and space complexity of your solution?

Answer:

Time Complexity: O(log(m * n)) — because we apply binary search over m * n elements.

Space Complexity: O(1) — we don’t use any extra space, just a few pointers for binary search.

🧾 Q5: How would you handle edge cases, like an empty matrix?

Answer:

I would first check:


if not matrix or not matrix[0]:
return False

This ensures I don't get an index error when accessing matrix[0][0] in an empty matrix or when the     matrix has empty rows.

🧾 Q6: What if rows are sorted, but the first element of a row is not greater than the last element of the previous row?

Answer:

In that case, the matrix can’t be treated as a linear sorted array. So, I wouldn't apply this binary     search method.

Instead, I would:

Use binary search to find the correct row where the target might exist.

Then do binary search within that row.

This gives a time complexity of O(log m + log n).