Binary Search Problem |LeetCode Problem – 1|Easy

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 – 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;
        
        
        
        
    }
};
Time Complexity  = O(no of rows * log( max of column ))