Search a 2D Matrix

The solution to Leetcode Medium Problem

Sukanya Bharati

Published in

TheLeanProgrammer

4 min readOct 10, 2021

Write an efficient algorithm that searches for a value in a m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

Example 1:

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

Example 2:

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

Constraints:

m == matrix.length (number of rows)
n == matrix[i].length (number of colomns)
1 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4

Well, we see above that the elements in the matrix are sorted, so what is the first intuition that comes to your mind?

“Binary Search” right? When elements are sorted we use a binary search for finding the target element and this is the concept which I am going to use to solve this problem today! It works on the principle of divide and conquer.

So first let us understand how a binary search works :

Below is a sorted list and let us try to search for 31 in the list.

First let us find the middle element in the list by using the formula , mid = low + (high - low) / 2

Here low is the starting index, i.e 0, and high is the last index i.e 9,

mid = 0 + (9 - 0) / 2 = 4 (taking integral value)

Now arr[mid] = arr[4] = 27 which is smaller than the element to be found.So we neglect the left half of the array. Now our array becomes [31, 33, 35, 42, 44]

Now our low value becomes low = mid+1 and high remains the same. Calculate mid again, now our midpoints to 35.

Again check if an element in mid-position is smaller or greater than 35, it is smaller. So consider the left half of the array.

high = mid-1 (updated to). Keep doing this process recursively until you find the element.

Finally, element 31 is found at index 5.

The time complexity of Binary Search is O(log N) where N is the number of elements in the list/array.

Similarly, you can try to solve the given examples below,

Now let us come back to the above question of searching an element in a 2D matrix.

Time Complexity -O(nlogm) where n is the number of rows and m is the number of columns. The analogy here can be considered as a two-pointer technique.

Space Complexity-O(1)

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int i = 0;
        int j = matrix[0].size()-1;  // number of coloumns
        
        while(i<matrix.size() && j>=0)
        {
            if(target==matrix[i][j])
                return true;         
            else if(target<matrix[i][j])
                j--;
            else 
                i++;
        }
        return false;
    }
};Runtime: 0 ms, faster than 100.00% of C++ online submissions for Search a 2D Matrix.Memory Usage: 9.6 MB, less than 52.46% of C++ online submissions for Search a 2D Matrix. (as executed on Leetcode platform)

2. Time Complexity-O(log(n*m)), Space Complexity-O(1) which is constant. Approach — Simply performing a binary search on the given matrix.

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0) 
            return false;
        
        int n = matrix.size();
        int m = matrix[0].size();
        
        int low = 0;
        int high = (n*m)-1;
        
        while(low<=high)
        {
            int mid = (low +(high-low)/2);
            if(matrix[mid/m][mid%m]==target)
                return true;
            
            if(matrix[mid/m][mid%m]<target)
                low = mid+1;
            else
                high = mid-1;
        }
        return false;
    }
};Runtime: 4 ms, faster than 74.94% of C++ online submissions for Search a 2D Matrix.Memory Usage: 9.5 MB, less than 52.46% of C++ online submissions for Search a 2D Matrix.(as executed on Leetcode)

There can be many other approaches to solving this problem, if you have one do comment it down below and let the readers know of it.

Till then keep coding! Good Luck!

Useful links :

Since you enjoyed reading my blog , why not buy me a coffee and supoort my work here!! https://www.buymeacoffee.com/sukanyabharati ☕

Don’t forget to follow The Lean Programmer Publication for more such articles, and subscribe to our newsletter tinyletter.com/TheLeanProgrammer

Search a 2D Matrix

The solution to Leetcode Medium Problem

Now let us come back to the above question of searching an element in a 2D matrix.

Written by Sukanya Bharati