Blog

Here’s the question link on LeetCode 74. Search a 2D Matrix:

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

Brute O(n*m)

A brute-force way is to perform an n*m search every time:

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

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

But this will fail the restrictions:

Optimal O(log(n*m))

We can think of this as a normal array and use a helper function to get indexes correct and run a simple binary search algorithm.

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

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

Code Lines Explained

• left = 1, right = n * m: Treat the entire matrix as a normal 1D array. We have n * m elements.
• mid = left + (right - left)/2: Calculate the middle index, just like normal binary search.
• getValFromInd(matrix, mid): Get the actual matrix value corresponding to our 1D index.
• if(curr == target): We found our target. Return true.
• else if(curr < target): Target must be on the right. Move left = mid + 1.
• else: Target must be on the left. Move right = mid - 1.

Now the interesting part, our helper function:

int n = matrix[0].size();
int i = (ind - 1) / n;
int j = (ind - 1) % n;
return matrix[i][j];

We convert our 1D index into 2D coordinates.

• (ind - 1) / n gives us the row.
• (ind - 1) % n gives us the column.

We subtract 1 because we’re using 1-based indexing in binary search, but matrix indices start from 0.

That’s it; see you in the next one.