Search in 2D matrix

In this post, we will discuss two approaches to searching for an element in a sorted 2D matrix efficiently.

💡 Brute Force Approach

The simplest way to search for an element is to traverse the entire matrix row by row and column by column.

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int rows = matrix.size();  
    if (rows == 0) return false;  
    int cols = matrix[0].size();  
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == target)
                return true;
        }
    }
    return false;
}

Time Complexity:

• O(m × n) (where m is the number of rows and n is the number of columns)

• This is because we check every element.

Space Complexity:

• O(1) (since we are not using extra space)

While this method works, it is not optimal for large matrices. Let's improve it!

Optimized Approach: Binary Search

Since the matrix is sorted in row-major order, we can flatten it into a virtual 1D array and apply binary search. However, we don’t actually need to store it as a 1D array—we can calculate the row and column indices using a formula.

🔢 Understanding the Formula

Consider this matrix:

1   2   3   4
5   6   7   8
9  10  11  12

We can treat it as a 1D array:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

Indexing formula:

• Row = mid / cols → Finds which row the mid index belongs to.

• Column = mid % cols → Finds the column within that row.

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    int low = 0, high = (rows * cols - 1); // Total elements: m*n

    while (low <= high) {
        int mid = (low + high) / 2;
        int row = mid / cols;
        int col = mid % cols;

        if (matrix[row][col] == target)
            return true;
        else if (matrix[row][col] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return false;
}

Time Complexity:

• O(log(m × n)) → Since we are using binary search, we reduce the search space logarithmically.

Space Complexity:

• O(1) → No extra space is used.

KEY POINTS :

✅ Brute Force: O(m × n) (Inefficient)
✅ Binary Search: O(log(m × n)) (Optimal)

This binary search method makes searching for an element in a sorted 2D matrix super fast! 🚀

Hope you found this useful! Stay tuned for more DSA solutions. 😊💡

problem link: https://leetcode.com/problems/search-a-2d-matrix/description/