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