Search in 2D matrix

Problem Link

Search-a-2d-matrix

Problem Statement

You are given a 2D matrix of integers with the following properties:

1. Each row is sorted in non-decreasing order.

2. 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 found in the matrix, otherwise return false.

You must implement a solution with O(log(m * n)) time complexity.

Examples

Example 1:

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

Example 2:

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

Constraints

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 100

• -10⁴ <= matrix[i][j], target <= 10⁴

Intuition

The matrix can be visualized as a flattened 1D sorted array because:

• Each row is sorted.

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

This makes the entire matrix behave like a single sorted array. Therefore, we can apply binary search on this 1D view.

To map 1D indices to 2D positions:

• For index i, the corresponding cell is at matrix[i / n][i % n], where n is the number of columns.

Approach

1. Flattened Search Space:

   • Total number of elements = m * n

   • Perform binary search on range [0, m*n - 1]

2. Binary Search Loop:

   • Compute mid = (low + high) / 2

   • Map to 2D: row = mid / n, col = mid % n

   • Compare matrix[row][col] with target:

     • If equal, return true

     • If less than target, search right half

     • Otherwise, search left half

3. Return false if the element is not found after the loop.

Java Code

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

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

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

Time and Space Complexity

• Time Complexity: O(log(m * n))
  Binary search over all m * n elements.

• Space Complexity: O(1)
  Constant space is used (no additional data structures).

Dry Run

Input:

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

Flattened Matrix:

[1,3,5,7,10,11,16,20,23,30,34,60] (total 12 elements)

Binary Search Steps:

- low = 0, high = 11
    
- mid = 5 → matrix[1][1] = 11 < target → low = 6
    
- mid = 8 → matrix[2][0] = 23 > target → high = 7
    
- mid = 6 → matrix[1][2] = 16 → match found

Output: true

Conclusion

By treating the matrix as a virtual sorted 1D array, this problem becomes a standard binary search problem. It highlights the importance of index mapping and space-efficient searching in multi-dimensional arrays. The key insight is that sorted matrix rows + increasing start elements per row simulate a linear sorted array.

This method is optimal and adheres strictly to the O(log(m * n)) time constraint.