Count Negative Numbers in a Sorted Matrix LeetCode Solution



LeetCode Matrix

Problem statement

In the problem “Count Negative Numbers in a Sorted Matrix” we are given a matrix of n rows and m columns. Elements are sorted in decreasing order both row-wise and column-wise. We need to find the total number of negative elements in the matrix.

Example

grid = [[8,3,2,-1],[4,2,1,-1],[3,1,-1,-2],[-1,-1,-2,-3]]
8

Explanation: As in the given matrix negative numbers are: {-1,-1,-1,-2,-1,-1,-2,-3}. So the total count of the negative numbers is 8.

Approach

To understand the approach better let us use the same example for better understanding. We will see the given matrix as a set of positive and negative values and will ignore its magnitude. So the given matrix is converted into a set of positive and negative values.

leetcode solution to Count Negative Numbers in a Sorted Matrix

So we already know that the matrix is sorted in decreasing order row-wise as well as column-wise, we will use it to solve this problem. We will start with the first row and will start traversing from right to left until we encounter a positive element(let’s call it col). The total number of negative elements in the first row will be => m – col – 1. Now we will jump to the next row. Here comes the use of the fact that elements are sorted. We need not traverse elements that are to the left of the col because the value of matrix[0][col]>=matrix[1][col] and all elements right to the matrix[1][col] is smaller than it.

Now if matrix[1][col] is positive then The total number of negative elements in the first row will be => m – col – 1 else we will keep traversing from right to left until we encounter a positive element. We will follow these steps until we visit all the rows. The final total count of negative numbers from all the rows will be our answer.

Code

C++ code for Count Negative Numbers in a Sorted Matrix LeetCode Solution

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

 int count(vector<vector<int>>& grid)
 {
  int n=grid.size(),m=grid[0].size(), row=0, column=m - 1,ans=0;
        while (row < n) {
            while (column >= 0 && grid[row][column] < 0) column--;
            ans += m - column - 1;
            row++;
        }
        return ans; 
 }

int main() 
{ 
 vector<vector<int> > arr = { { 8,3,2,-1 }, 
                              { 4,2,1,-1 }, 
                              { 3,1,-1,-2 },
                              { -1,-1,-2,-3 }}; 
 cout<<count(arr)<<endl; 
 return 0;
}
8

Java code for Count Negative Numbers in a Sorted Matrix LeetCode Solution

public class Tutorialcup {
  public static int countNegatives(int[][] grid) {
         int n=grid.length,m=grid[0].length, row=0, column=m - 1,ans=0;
          while (row < n) {
              while (column >= 0 && grid[row][column] < 0) column--;
              ans += m - column - 1;
              row++;
          }
          return ans; 
      }
  public static void main(String[] args) {
    int [][] grid = {
              {8,3,2,-1},
              {4,2,1,-1},
              {3,1,-1,2},
              {-1,-1-2,-3}
            };
    int ans= countNegatives(grid);
    System.out.println(ans);
  }
}

 

8

Complexity Analysis

Time complexity

The time complexity of the above code is O(n+m) because we are traversing each row and at worst case all columns. Here n and m are the numbers of rows and number of columns respectively.

Space complexity

The space complexity of the above code is O(1) because we are using only a variable to store answer.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions