Binary Search Problem |LeetCode Problem – 1|Easy

In this article we will see some implementation problems of binary search. Before you see and learn the solution, try to solve it on your own. Just understand the problem and try to solve it on your own. Let’s get started!

Count Negative Numbers in a Sorted Matrix       

Problem – Given a m * n matrix grid which is sorted in non-increasing order both row-wise and column-wise.  Return the number of negative numbers in grid using Binary search in this problem

Example 1:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]

Output: 8

Explanation: There are 8 negatives number in the matrix.

Example 2:

Input: grid = [[3,2],[1,0]]

Output: 0

Example 3:

Input: grid = [[1,-1],[-1,-1]]

Output: 3

Example 4:

Input: grid = [[-1]]

Output: 1

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100

Solution

According to size, if we go in linear fashion, that is, Check each cell of matrix one by one the time complexity is O (m*n)  which is affordbale if m and n less then 100

But if we try to do it in O(m*log(n)) time, We have to use Binary Search, which is better approach.

Linear Search Solution

Algorithm –

Simply traverse one by one each cell of matrix and increase count if the value is negative

int countNegatives(vector<vector<int>>& grid) {
        
        
        int ans = 0;
        for(int i =0;i<grid.size();i++)
        {
            for(int j = 0;j<grid[i].size();j++)
                if(grid[i][j]<0)
                    ans++;
        
        }
        return ans;
    }

Time Complexity

Time Complexity – O(no of rows* no of column)

Binary Search Solution

As we know, Binary search is a divide and conquer algorithm, so, we are going to focus on dividing each row of the array in this problem

1. Traverse each row one by one
2. Do a Binary search to find the first negative element index
3. Subtract the length of row by index to find the total number of a negative number, because elements are arranged in descending order
4. Repeat Until any row left

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        
        
        int ans = 0;
        for(int i =0;i<grid.size();i++)
        {
            ans+=binarySearch(grid[i]); // Traversing each row one by one
        
        }
        return ans;
        
        
        
    }
    
    int binarySearch(vector<int> &bs)
    {
        int  l = 0;
        int  r = bs.size()-1;
      
        while(l<=r)
        {
            int mid = (l+r)/2;
            if(bs[mid]<0)
            {                    // for finding negative element
                
                r = mid-1;
            }
            else
                l = mid+1;
            
            
        }
        if(l<bs.size() && bs[l]<0)
        return bs.size()-l;   // return number of negative element
        else
            return 0;
        
        
        
        
    }
};    

Explanation:

1. We will solve the problem using class. Assign the traversing operation in a separate function.
2. Now in a separate function write the binary search condition. (Separating the list into two different parts).
3. For separating the list, we find the middle element and assign the left and right according to the middle element.
4. This is the implementation we did in the above code.

Time complexity

Time Complexity = O(no of rows * log( max of column ))

Which solution is better?

Whenever we perform any search operation in an array or list, it is always to follow binary search because it reduces time complexity. Always remember that a good code is the one with less time consumption. So for this problem too, follow binary search 🙂

Conclusion

In this article we have seen a problem regarding binary search. We also learnt the solution for the same problem in a linear search way too. We discussed the algorithm and solutions for both the ways. Hop this article helped. Leave your comments below to let us know if you have any queries!