Tutorialspoint.dev

Count Negative Numbers in a Column-Wise and Row-Wise Sorted Matrix

Find the number of negative numbers in a column-wise / row-wise sorted matrix M[][]. Suppose M has n rows and m columns.

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 you to minimize your browser and try this yourself first.

Naive Solution
Here’s a naive, non-optimal solution.

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



With the given 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 above idea.

C++

// CPP implementation of Naive method
// to count of negative numbers in 
// M[n][m]
#include <bits/stdc++.h>
using namespace std;
  
int countNegative(int M[][4], int n, int m)
{
    int count = 0;
  
    // Follow the path shown using 
    // arrows above
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if( M[i][j] < 0 )
                count += 1;
          
            // no more negative numbers
            // in this row
            else
                break;
        }
    }
    return count;
}
  
// Driver program to test above functions
int main () 
{
    int M[3][4] = { {-3, -2, -1, 1},
                     {-2, 2, 3, 4},
                    {4, 5, 7, 8} };
      
    cout << countNegative(M, 3, 4);
    return 0;
}
// This code is contributed by Niteesh Kumar

Java

//Java implementation of Naive method
// to count of 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 shown using 
        // arrows above
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if( M[i][j] < 0 )
                    count += 1;
          
                // no more negative numbers
                // in this row
                else
                    break;
            }
        }
        return count;
    }
  
    // Driver program to test 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 contributed by Chhavi

Python

# Python implementation of Naive method to count of 
# negative numbers in M[n][m]
  
def countNegative(M, n, m):
    count = 0
  
    # Follow the path shown using arrows above
    for i in range(n):
        for j in range(m): 
  
            if M[i][j] < 0:
                count += 1
  
            else:
                # no more negative numbers in this row
                break
    return count
  
  
# Driver code
M =
      [-3, -2, -11],
      [-2234],
      [ 4578]
    ]
print(countNegative(M, 3, 4))

C#

// C# implementation of Naive method
// to count of negative numbers in 
// M[n][m]
using System;
  
class GFG
{
      
    // Function to count
    // negative number
    static int countNegative(int [,]M, int n,
                             int m)
    {
        int count = 0;
  
        // Follow the path shown  
        // using arrows above
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if( M[i, j] < 0 )
                    count += 1;
          
                // no more negative numbers
                // in this row
                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 contributed by Sam007

PHP

<?php
// PHP implementation of Naive method
// to count of negative numbers in 
// M[n][m]
  
function countNegative($M, $n, $m)
{
    $count = 0;
  
    // Follow the path shown using 
    // arrows above
    for( $i = 0; $i < $n; $i++)
    {
        for( $j = 0; $j < $m; $j++)
        {
            if( $M[$i][$j] < 0 )
                $count += 1;
          
            // no more negative numbers
            // in this row
            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 contributed by anuj_67.
?>

Output :

4

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

 

Optimal Solution

Here’s a more efficient solution:

  1. We start from 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 either run out of negative numbers or we 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,  ?,  ?] -> Found 3 negative numbers in this row
[ ?,  ?,  ?,  4] -> Found 1 negative number in this row
[ ?,  5,  7,  8] -> No negative numbers in this row 

C++

// CPP implementation of Efficient 
// method to count of negative numbers
// in M[n][m]
#include <bits/stdc++.h>
using namespace std;
  
int countNegative(int M[][4], int n, int m)
    // initialize result
    int count = 0; 
  
    // Start with top right corner
    int i = 0;
    int j = m - 1; 
  
    // Follow the path shown using
    // arrows above
    while( j >= 0 && i < n )
    {
        if( M[i][j] < 0 )
        {
            // j is the index of the
            // last negative number
            // in this row. So there
            // must be ( j+1 )
            count += j + 1;
  
            // negative numbers in 
            // this row.
            i += 1;
        }
              
        // move to the left and see 
        // if we can find a negative
        // number there
        else
        j -= 1;
    }
  
    return count;
}
  
// Driver program to test above functions
int main () 
{
    int M[3][4] = { {-3, -2, -1, 1},
                    {-2, 2, 3, 4},
                    {4, 5, 7, 8} };
      
    cout << countNegative(M, 3, 4);
      
    return 0;    
}
// This code is contributed by Niteesh Kumar

Java

// Java implementation of Efficient 
// method to count of 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)
    {   
        // initialize result
        int count = 0
  
        // Start with top right corner
        int i = 0;
        int j = m - 1
  
        // Follow the path shown using
        // arrows above
        while( j >= 0 && i < n )
        {
            if( M[i][j] < 0 )
            {
                // j is the index of the
                // last negative number
                // in this row. So there
                // must be ( j+1 )
                count += j + 1;
  
                // negative numbers in 
                // this row.
                i += 1;
            }
              
            // move to the left and see 
            // if we can find a negative
            // number there
            else
            j -= 1;
        }
        return count;
    }
  
    // Driver program to test 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 contributed by Chhavi

Python

# Python implementation of Efficient method to count of 
# negative numbers in M[n][m]
  
def countNegative(M, n, m):
  
    count = 0 # initialize result
  
    # Start with top right corner
    i = 0 
    j = m - 1  
  
    # Follow the path shown using arrows above
    while j >= 0 and i < n:
  
        if M[i][j] < 0:
  
            # j is the index of the last negative number
            # in this row.  So there must be ( j+1 )
            count += (j + 1
  
            # negative numbers in this row.
            i += 1
  
        else:
            # move to the left and see if we can
            # find a negative number there
             j -= 1
    return count
  
# Driver code
M =
      [-3, -2, -11],
      [-2234],
      [4,   578]
    ]
print(countNegative(M, 3, 4))

C#

// C# implementation of Efficient 
// method to count of negative 
// numbers in M[n][m]
using System;
  
class GFG
{
      
// Function to count 
// negative number
static int countNegative(int [,]M, int n,
                         int m)
    
          
        // initialize result
        int count = 0; 
  
        // Start with top right corner
        int i = 0;
        int j = m - 1; 
  
        // Follow the path shown 
        // using arrows above
        while( j >= 0 && i < n )
        {
            if( M[i, j] < 0 )
            {
                // j is the index of the
                // last negative number
                // in this row. So there
                // must be ( j + 1 )
                count += j + 1;
  
                // negative numbers in 
                // this row.
                i += 1;
            }
              
            // move to the left and see 
            // if we can find a negative
            // number there
            else
            j -= 1;
        }
        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 contributed by Sam007

PHP

<?php
// PHP implementation of Efficient 
// method to count of negative numbers
// in M[n][m]
  
function countNegative( $M, $n, $m)
{
      
    // initialize result
    $count = 0; 
  
    // Start with top right corner
    $i = 0;
    $j = $m - 1; 
  
    // Follow the path shown using
    // arrows above
    while( $j >= 0 and $i < $n )
    {
        if( $M[$i][$j] < 0 )
        {
            // j is the index of the
            // last negative number
            // in this row. So there
            // must be ( j+1 )
            $count += $j + 1;
  
            // negative numbers in 
            // this row.
            $i += 1;
        }
              
        // move to the left and see 
        // if we can find a negative
        // number there
        else
        $j -= 1;
    }
  
    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);
      
    return 0; 
  
// This code is contributed by anuj_67.
?>

Output :

4

With this solution, we can now solve this problem in O(n + m) time.

 

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter