# Counting negative numbers in a matrix column-wise and row-wise

Python Methods and Functions

Example:

` Input: M = [-3, -2, -1, 1] [-2, 2, 3, 4] [4, 5, 7, 8] Output: 4 We have 4 negative numbers in this matrix `

We strongly recommend that you minimize your browser and try this first.

Naive solution
Here's a naive, suboptimal solution.

We start at the top left corner and count the number of negative numbers one at a time, from left to right and top to bottom.

With the above example:

` [-3, -2, -1, 1] [-2, 2, 3, 4] [4, 5, 7, 8] Evaluation process [?,?,?, 1] [? , 2, 3, 4] [4, 5, 7, 8] `

Below is the implementation of the above idea.

C++

 ` // CPP implementation of the Naive method ` ` // for counting negative numbers in ` ` // M [n] [m] ` ` # include & lt; bits / stdC++. H & gt; ` ` using ` ` namespace ` ` std; `   ` int ` ` countNegative (` ` int ` ` M [] [4], ` ` int ` ` n, ` ` int ` ` m) ` ` {` ` int ` ` count = 0; `   ` // Follow the path indicated by ` ` ` ` // arrows above ` ` for ` ` (` ` int ` ` i = 0; i & lt; n; i ++) {` ` ` ` for ` ` (` ` int ` ` j = 0; j & lt; m; j ++) {` ` if ` ` (M [i] [j] & lt; 0) ` ` count + = 1; `   ` // no more negative numbers ` ` ` ` // on this line ` ` else ` ` break ` `; ` `} ` `} ` ` ` ` return ` ` count; ` `} `   ` // Driver program for checking the above functions ` ` int ` ` main () ` ` {` ` int ` ` M [3] [4] = {{-3, -2, -1, 1}, ` ` {-2, 2, 3, 4}, ` ` ` ` {4, 5, 7, 8}}; `   ` cout & lt; & lt; countNegative (M, 3, 4); ` ` return ` ` 0; ` `} ` ` // This code is provided by Nitesh Kumar `

Java

 ` // Java implementation of the Naive method ` ` // to count negative numbers in ` ` // M [n] [m] ` ` import ` ` java.util. *; ` ` import ` ` java.lang. *; ` ` import ` ` java.io. *; `   ` class ` ` GFG {` ` ` ` static ` ` int ` ` countNegative (` ` int ` ` M [] [], ` ` int ` ` n, ` ` int ` ` m) ` ` {` ` int ` ` count = ` ` 0 ` `; `   ` // Follow the path indicated by ` ` ` ` // arrows above ` ` for ` ` (` ` int ` ` i = ` ` 0 ` `; i & lt; n; i ++) {` ` for ` ` (` ` int ` ` j = ` ` 0 ` `; j & lt; m; j ++) {` ` if ` ` (M [i] [j] & lt; ` ` 0 ` `) ` ` count + = ` ` 1 ` `; `   ` // no more negative numbers ` ` ` ` // on this line ` ` else ` ` break ` `; ` `} ` `} ` ` ` ` return ` ` count; ` `} `   ` ` ` // Driver program to check the above functions ` ` public ` ` static ` ` void ` ` main (String [] args) ` ` {` ` ` ` int ` ` M [] [] = {{- ` ` 3 ` `, - ` ` 2 ` `, - ` ` 1 ` `, ` ` 1 ` `}, ` ` {- ` ` 2 ` `, ` ` 2 ` `, ` ` 3 ` `, ` ` 4 ` `}, ` ` {` ` 4 ` `, ` ` 5 ` `, ` ` 7 ` `, ` ` 8 ` `}}; `   ` System.out.println (countNegative (M, ` ` 3 ` `, ` ` 4 ` `)); ` `} ` `} ` ` // This code is provided by Chhavi `

python

 ` # Python implementation of the Naive method for counting ` ` # negative numbers in M ​​[n] [m] `   ` def ` ` countNegative (M, n, m): ` ` count ` ` = ` ` 0 ` ` `  ` # Follow the path indicated by the arrows above ` ` for i in range ( n): `` for j in range (m):    if M [i] [j] & lt; 0 : count + = 1   else : # no more negative ones numbers in this line break return count      # Driver code M = [  [ - 3 , - 2 , - 1 ,  1 ] , [ - 2 ,  2 ,  3 ,  4 ], [ 4 ,  5 ,  7 ,  8 ]   ] print ( countNegative (M, 3 , 4 )) `

C #

 ` // C # implementation of the Naive method ` ` // for counting negative numbers in ` ` // M [n] [m] ` ` using ` ` System; `   ` class ` ` GFG {` ` `  ` ` ` // Function for counting ` ` // negative number ` ` static ` ` int ` ` countNegative (` ` int ` ` [,] M, ` ` int ` ` n, ` ` int ` ` m) ` ` {` ` int ` ` count = 0; `   ` // Follow the specified path ` ` ` ` // using the arrows above ` ` for ` ` (` ` int ` ` i = 0; i & lt; n; i ++) {` ` ` ` for ` ` (` ` int ` ` j = 0; j & lt; m; j ++) {` ` if ` ` (M [i, j] & lt; 0) ` ` count + = 1; `   ` // no more negative numbers ` ` ` ` // on this line ` ` else ` ` break ` `; ` `} ` `} ` ` ` ` return ` ` count; ` `} `   ` ` ` // Driver code ` ` public ` ` static ` ` void ` ` Main () ` ` {` ` int ` ` [,] M = {{-3 , -2, -1, 1}, ` ` {-2, 2, 3, 4}, ` ` {4, 5, 7, 8}}; `   ` Console.WriteLine (countNegative (M, 3, 4)); ` `} ` `} ` ` `  ` // This code is provided by Sam007 `

PHP

` `

 ` & lt;? php ` ` // PHP implementation of the Naive method ` ` // for counting negative numbers in ` ` // M [n] [m] `   ` function ` ` countNegative (` ` \$ M ` `, ` ` \$ n ` `, ` ` \$ m ` `) ` ` {` ` \$ count ` ` = 0; `   ` // Follow the path indicated by ` ` ` ` // arrows above ` ` for ` ` (` ` \$ i ` ` = 0; ` ` \$ i ` ` & lt; ` ` \$ n ` `; ` ` \$ i ` ` ++) ` ` ` ` {` ` for ` ` (` ` \$ j ` ` = 0; ` ` \$ j ` ` & lt; ` ` \$ m ` `; ` ` \$ j ` ` ++) ` ` {` ` if ` ` (` ` \$ M ` ` [` ` \$ i ` `] [` ` \$ j ` `] & lt; 0) ` ` \$ count ` ` + = one; `   ` // no more negative numbers ` ` ` ` // on this line ` ` else ` ` break ` `; ` `} ` `} ` ` ` ` return ` ` \$ count ` `; ` `} `   ` // Driver code ` ` \$ M ` ` = ` ` array ` ` (` ` array ` ` (- 3, -2, -1, 1), ` ` array ` ` (- 2, 2, 3, 4), ` ` array ` ` (4, 5, 7, 8)); `   ` echo ` ` countNegative (` ` \$ M ` `, 3, 4); `   ` // This code is provided by anuj_67. ` `? & gt; `

Exit:

`4`

In this approach we go through all the elements and therefore in the worst case (when all numbers are negative in the matrix), it takes O (n * m) time.

Optimal solution

Here is a more efficient solution:

1. We start at the top right corner and find the position of the last negative number in the first row.
2. Using this information, we find the position of the last negative number in the second row.
3. We keep repeating this process until we run out of negative numbers or get to the last row.
` With the given example: [-3, -2, -1, 1] [-2, 2, 3, 4] [4, 5, 7, 8 ] Here's the idea: [-3, -2,?,?] - & gt; Found 3 negative numbers in this row [?,?,?, 4] - & gt; Found 1 negative number in this row [?, 5, 7, 8] - & gt; No negative numbers in this row `

C++

` `

` // CPP implementation Efficient // method for counting negative numbers // in M ​​[n] [m ] # include & lt; bits / stdC++. h & gt; using namespace std;   int countNegative ( int M [] [4], int n, int m) { // initialize the result int count = 0;   // Start at the top right corner   int i = 0; int j = m - one;   // Follow the path indicated by   // arrows above while (j & gt; = 0 & amp; & amp; i & lt; n) { if (M [i] [j] & lt; 0) { / / j - index // last negative number // in this row. Here // should be (j + 1) count + = j + 1;   // negative numbers in   // this row i + = 1; }     // move left and see // if we can find negative // number there else j - = 1; }     return count ; }   // Driver program for checking the above functions int main () { int M [3] [4] = {{-3, -2, -1, 1}, {-2, 2, 3, 4},   {4, 5, 7, 8}};   cout & lt; & lt; countNegative (M, 3, 4);   return 0; } // This code is provided by Nitesh Kumar `

` ` Java

 ` // Java implementation Efficient ` ` // method for counting negative numbers ` ` // in M ​​[n] [m] ` ` import ` ` java.util. *; ` ` import ` ` java.lang. *; ` ` import ` ` java.io. *; `   ` class ` ` GFG {` ` ` ` static ` ` int ` ` countNegative (` ` int ` ` M [] [], ` ` int ` ` n, ` `/ code> // number there `` else j - = 1; }     return count ; }   // Driver program for checking the above functions int main () { int M [3] [4] = {{-3, -2, -1, 1}, {-2, 2, 3, 4},   {4, 5, 7, 8}};   cout & lt; & lt; countNegative (M, 3, 4);   return 0; } // This code is provided by Nitesh Kumar `

Java