Count Negative Numbers in a Sorted Matrix

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

Example 1:

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

Approach

Java

import java.util.Arrays;

public class CountNegativeInSortedMatrix {
    public static void main(String[] args) {
        int[][] grid = { { 4, 3, 2, -1 }, { 3, 2, 1, -1 }, 
                    { 1, 1, -1, -2 }, { -1, -1, -2, -3 } };
        System.out.println(countNegatives(grid));
    }

    static int countNegatives(int[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {

            Arrays.sort(grid[i]);
            int index = lower_bound(grid[i], 0);

            count += Math.abs(index);

        }
        return count;
    }

    public static int lower_bound(int[] ar, int k) {
        int s = 0;
        int e = ar.length;
        while (s != e) {
            int mid = s + e >> 1;
            if (ar[mid] < k) {
                s = mid + 1;
            } else {
                e = mid;
            }
        }

        return s;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int countNegatives(vector<vector<int>>& grid) 
{
     int count=0;
     for(int i=0;i<grid.size();i++)
     {
         
         sort(grid[i].begin(),grid[i].end());
         int index=lower_bound(grid[i].begin(),grid[i].end(),0)-grid[i].begin();

         count+=abs(index);
         
     }
        return count;
}
int main()
{
    vector<vector<int>> grid ={{4,3,2,-1},
                              {3,2,1,-1},
                              {1,1,-1,-2},
                              {-1,-1,-2,-3}};
    cout<<countNegatives(grid);
    return 0;
}