Skip to main content

Count negative numbers in a sorted matrix

The problem is to count the number of negative numbers in a sorted matrix. The matrix is sorted in such a way that each row and each column is sorted in ascending order.

Example

Consider the following 5x5 matrix:

-4  -3  -1  1  8
-3  -2   2  4  6
 5   6   7  7  9
-1  -1   1  5  8
-2   4   7  8  9

In this matrix, there are 8 negative numbers: -4, -3, -3, -2, -1, -1, -2, and -1.

Idea to Solve the Problem

To count the number of negative numbers in the sorted matrix, we can follow these steps:

  1. Initialize a count variable to keep track of the number of negative numbers.
  2. Iterate through each row of the matrix: a. For each row, iterate through the columns while checking if the current element is negative. b. When a positive number is encountered in a row, we know that all subsequent elements in that row will also be positive, so we stop counting. c. Add the count of negative numbers in the current row to the total count.
  3. Print the total count of negative numbers.

Pseudocode

countNegative(matrix):
    count = 0
    for i from 0 to N:
        j = 0
        while j < M and matrix[i][j] < 0:
            j++
        count += j
    print "Total negative number is:", count

main:
    matrix = {
        {-4, -3, -1, 1, 8},
        {-3, -2, 2, 4, 6},
        {5, 6, 7, 7, 9},
        {-1, -1, 1, 5, 8},
        {-2, 4, 7, 8, 9}
    }
    countNegative(matrix)

Code Solution

/*
   C program for
   Count negative numbers in a sorted matrix
*/
#include <stdio.h>

#define N 5
#define M 5
// Print matrix elements
void printMatrix(int matrix[N][M])
{
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			printf("  %d", matrix[i][j]);
		}
		printf("\n");
	}
}
void countNegative(int matrix[N][M])
{
	int count = 0;
	int j = 0;
	for (int i = 0; i < N; ++i)
	{
		// Count negative element at beginning of ith row
		while (j < M && matrix[i][j] < 0)
		{
			j++;
		}
		// Update count
		count += j;
		// Reset j
		j = 0;
	}
	// Display calculated result
	printf("\n Total negative number is : %d", count);
}
int main()
{
	int matrix[N][M] = {
		{
			-4, -3, -1, 1, 8
		},
		{
			-3 , -2 , 2 , 4 , 6
		},
		{
			5 , 6 , 7 , 7 , 9
		},
		{
			-1 , -1 , 1 , 5 , 8
		},
		{
			-2 , 4 , 7 , 8 , 9
		}
	};
	// Display matrix element
	printMatrix(matrix);
	// Display number of negative element in sorted matrix
	countNegative(matrix);
	return 0;
}

Output

  -4  -3  -1  1  8
  -3  -2  2  4  6
  5  6  7  7  9
  -1  -1  1  5  8
  -2  4  7  8  9

 Total negative number is : 8
/*
    Java Program for
    Count negative numbers in a sorted matrix
*/
public class Counting
{
	// Print matrix elements
	public void printMatrix(int[][] matrix)
	{
      	int n = matrix.length; 
        int m = matrix[0].length; 
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				System.out.print(" " + matrix[i][j]);
			}
			System.out.print("\n");
		}
	}
	public void countNegative(int[][] matrix)
	{
		int count = 0;
		int j = 0;
      	int n = matrix.length; 
        int m = matrix[0].length; 
		for (int i = 0; i < n; ++i)
		{
			// Count negative element at beginning of ith row
			while (j < m && matrix[i][j] < 0)
			{
				j++;
			}
			// Update count
			count += j;
			// Reset j
			j = 0;
		}
		// Display calculated result
		System.out.print("\n Total negative number is : " + count);
	}
	public static void main(String[] args)
	{
		Counting task = new Counting();
		int[][] matrix = {
			{
				-4, -3, -1, 1, 8
			},
			{
				-3 , -2 , 2 , 4 , 6
			},
			{
				5 , 6 , 7 , 7 , 9
			},
			{
				-1 , -1 , 1 , 5 , 8
			},
			{
				-2 , 4 , 7 , 8 , 9
			}
		};
		// Display matrix element
		task.printMatrix(matrix);
		// Display number of negative element in sorted matrix
		task.countNegative(matrix);
	}
}

Output

 -4 -3 -1 1 8
 -3 -2 2 4 6
 5 6 7 7 9
 -1 -1 1 5 8
 -2 4 7 8 9

 Total negative number is : 8
// Include header file
#include <iostream>
using namespace std;

/*
    C++ Program for
    Count negative numbers in a sorted matrix
*/
#define N 5
#define M 5
class Counting
{
	public:
		// Print matrix elements
		void printMatrix(int matrix[N][M])
		{

			for (int i = 0; i < N; ++i)
			{
				for (int j = 0; j < M; ++j)
				{
					cout << " " << matrix[i][j];
				}
				cout << "\n";
			}
		}
	void countNegative(int matrix[N][M])
	{
		int count = 0;
		int j = 0;

		for (int i = 0; i < N; ++i)
		{
			// Count negative element at beginning of ith row
			while (j < M && matrix[i][j] < 0)
			{
				j++;
			}
			// Update count
			count += j;
			// Reset j
			j = 0;
		}
		// Display calculated result
		cout << "\n Total negative number is : " << count;
	}
};
int main()
{
	Counting *task = new Counting();
	int matrix[N][M] = {
		{
			-4, -3, -1, 1, 8
		} , {
			-3 , -2 , 2 , 4 , 6
		} , {
			5 , 6 , 7 , 7 , 9
		} , {
			-1 , -1 , 1 , 5 , 8
		} , {
			-2 , 4 , 7 , 8 , 9
		}
	};
	// Display matrix element
	task->printMatrix(matrix);
	// Display number of negative element in sorted matrix
	task->countNegative(matrix);
	return 0;
}

Output

 -4 -3 -1 1 8
 -3 -2 2 4 6
 5 6 7 7 9
 -1 -1 1 5 8
 -2 4 7 8 9

 Total negative number is : 8
// Include namespace system
using System;
/*
    Csharp Program for
    Count negative numbers in a sorted matrix
*/
public class Counting
{
	// Print matrix elements
	public void printMatrix(int[,] matrix)
	{
		int n = matrix.GetLength(0);
		int m = matrix.GetLength(0);
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				Console.Write(" " + matrix[i,j]);
			}
			Console.Write("\n");
		}
	}
	public void countNegative(int[,] matrix)
	{
		int count = 0;
		int j = 0;
		int n = matrix.GetLength(0);
		int m = matrix.GetLength(0);
		for (int i = 0; i < n; ++i)
		{
			// Count negative element at beginning of ith row
			while (j < m && matrix[i,j] < 0)
			{
				j++;
			}
			// Update count
			count += j;
			// Reset j
			j = 0;
		}
		// Display calculated result
		Console.Write("\n Total negative number is : " + count);
	}
	public static void Main(String[] args)
	{
		Counting task = new Counting();
		int[,] matrix = {
			{
				-4, -3, -1, 1, 8
			},
{
				-3 , -2 , 2 , 4 , 6
			},
{
				5 , 6 , 7 , 7 , 9
			},
{
				-1 , -1 , 1 , 5 , 8
			},
{
				-2 , 4 , 7 , 8 , 9
			}
		};
		// Display matrix element
		task.printMatrix(matrix);
		// Display number of negative element in sorted matrix
		task.countNegative(matrix);
	}
}

Output

 -4 -3 -1 1 8
 -3 -2 2 4 6
 5 6 7 7 9
 -1 -1 1 5 8
 -2 4 7 8 9

 Total negative number is : 8
package main
import "fmt"
/*
    Go Program for
    Count negative numbers in a sorted matrix
*/

// Print matrix elements
func  printMatrix(matrix[][] int) {
	var n int = len(matrix)
	var m int = len(matrix[0])
	for i := 0 ; i < n ; i++ {
		for j := 0 ; j < m ; j++ {
			fmt.Print(" ", matrix[i][j])
		}
		fmt.Print("\n")
	}
}
func  countNegative(matrix[][] int) {
	var count int = 0
	var j int = 0
	var n int = len(matrix)
	var m int = len(matrix[0])
	for i := 0 ; i < n ; i++ {
		// Count negative element at beginning of ith row
		for (j < m && matrix[i][j] < 0) {
			j++
		}
		// Update count
		count += j
		// Reset j
		j = 0
	}
	// Display calculated result
	fmt.Print("\n Total negative number is : ", count)
}
func main() {
	
	var matrix = [][] int {
        {
            -4, -3, -1, 1, 8,
        } , {
            -3 , -2 , 2 , 4 , 6,
        } , {
            5 , 6 , 7 , 7 , 9,
        } , {
            -1 , -1 , 1 , 5 , 8,
        } , {
            -2 , 4 , 7 , 8 , 9,
        },
    };
	// Display matrix element
	printMatrix(matrix)
	// Display number of negative element in sorted matrix
	countNegative(matrix)
}

Output

 -4 -3 -1 1 8
 -3 -2 2 4 6
 5 6 7 7 9
 -1 -1 1 5 8
 -2 4 7 8 9

 Total negative number is : 8
<?php
/*
    Php Program for
    Count negative numbers in a sorted matrix
*/
class Counting
{
	// Print matrix elements
	public	function printMatrix($matrix)
	{
		$n = count($matrix);
		$m = count($matrix[0]);
		for ($i = 0; $i < $n; ++$i)
		{
			for ($j = 0; $j < $m; ++$j)
			{
				echo(" ".$matrix[$i][$j]);
			}
			echo("\n");
		}
	}
	public	function countNegative($matrix)
	{
		$count = 0;
		$j = 0;
		$n = count($matrix);
		$m = count($matrix[0]);
		for ($i = 0; $i < $n; ++$i)
		{
			// Count negative element at beginning of ith row
			while ($j < $m && $matrix[$i][$j] < 0)
			{
				$j++;
			}
			// Update count
			$count += $j;
			// Reset j
			$j = 0;
		}
		// Display calculated result
		echo("\n Total negative number is : ".$count);
	}
}

function main()
{
	$task = new Counting();
	$matrix = array(
      array(-4, -3, -1, 1, 8), 
      array(-3, -2, 2, 4, 6), 
      array(5, 6, 7, 7, 9), 
      array(-1, -1, 1, 5, 8), 
      array(-2, 4, 7, 8, 9)
    );
	// Display matrix element
	$task->printMatrix($matrix);
	// Display number of negative element in sorted matrix
	$task->countNegative($matrix);
}
main();

Output

 -4 -3 -1 1 8
 -3 -2 2 4 6
 5 6 7 7 9
 -1 -1 1 5 8
 -2 4 7 8 9

 Total negative number is : 8
/*
    Node JS Program for
    Count negative numbers in a sorted matrix
*/
class Counting
{
	// Print matrix elements
	printMatrix(matrix)
	{
		var n = matrix.length;
		var m = matrix[0].length;
		for (var i = 0; i < n; ++i)
		{
			for (var j = 0; j < m; ++j)
			{
				process.stdout.write(" " + matrix[i][j]);
			}
			process.stdout.write("\n");
		}
	}
	countNegative(matrix)
	{
		var count = 0;
		var j = 0;
		var n = matrix.length;
		var m = matrix[0].length;
		for (var i = 0; i < n; ++i)
		{
			// Count negative element at beginning of ith row
			while (j < m && matrix[i][j] < 0)
			{
				j++;
			}
			// Update count
			count += j;
			// Reset j
			j = 0;
		}
		// Display calculated result
		process.stdout.write("\n Total negative number is : " + count);
	}
}

function main()
{
	var task = new Counting();
	var matrix = [
		[-4, -3, -1, 1, 8],
		[-3, -2, 2, 4, 6],
		[5, 6, 7, 7, 9],
		[-1, -1, 1, 5, 8],
		[-2, 4, 7, 8, 9]
	];
	// Display matrix element
	task.printMatrix(matrix);
	// Display number of negative element in sorted matrix
	task.countNegative(matrix);
}
main();

Output

 -4 -3 -1 1 8
 -3 -2 2 4 6
 5 6 7 7 9
 -1 -1 1 5 8
 -2 4 7 8 9

 Total negative number is : 8
#    Python 3 Program for
#    Count negative numbers in a sorted matrix
class Counting :
	#  Print matrix elements
	def printMatrix(self, matrix) :
		n = len(matrix)
		m = len(matrix[0])
		i = 0
		while (i < n) :
			j = 0
			while (j < m) :
				print(" ", matrix[i][j], end = "")
				j += 1
			
			print(end = "\n")
			i += 1
		
	
	def countNegative(self, matrix) :
		count = 0
		j = 0
		n = len(matrix)
		m = len(matrix[0])
		i = 0
		while (i < n) :
			#  Count negative element at beginning of ith row
			while (j < m and matrix[i][j] < 0) :
				j += 1
			
			#  Update count
			count += j
			#  Reset j
			j = 0
			i += 1
		
		#  Display calculated result
		print("\n Total negative number is : ", count, end = "")
	

def main() :
	task = Counting()
	matrix = [
		[-4, -3, -1, 1, 8],
		[-3, -2, 2, 4, 6],
		[5, 6, 7, 7, 9],
		[-1, -1, 1, 5, 8],
		[-2, 4, 7, 8, 9]
	]
	#  Display matrix element
	task.printMatrix(matrix)
	#  Display number of negative element in sorted matrix
	task.countNegative(matrix)

if __name__ == "__main__": main()

Output

  -4  -3  -1  1  8
  -3  -2  2  4  6
  5  6  7  7  9
  -1  -1  1  5  8
  -2  4  7  8  9

 Total negative number is :  8
#    Ruby Program for
#    Count negative numbers in a sorted matrix
class Counting 
	#  Print matrix elements
	def printMatrix(matrix) 
		n = matrix.length
		m = matrix[0].length
		i = 0
		while (i < n) 
			j = 0
			while (j < m) 
				print(" ", matrix[i][j])
				j += 1
			end

			print("\n")
			i += 1
		end

	end

	def countNegative(matrix) 
		count = 0
		j = 0
		n = matrix.length
		m = matrix[0].length
		i = 0
		while (i < n) 
			#  Count negative element at beginning of ith row
			while (j < m && matrix[i][j] < 0) 
				j += 1
			end

			#  Update count
			count += j
			#  Reset j
			j = 0
			i += 1
		end

		#  Display calculated result
		print("\n Total negative number is : ", count)
	end

end

def main() 
	task = Counting.new()
	matrix = [
		[-4, -3, -1, 1, 8],
		[-3, -2, 2, 4, 6],
		[5, 6, 7, 7, 9],
		[-1, -1, 1, 5, 8],
		[-2, 4, 7, 8, 9]
	]
	#  Display matrix element
	task.printMatrix(matrix)
	#  Display number of negative element in sorted matrix
	task.countNegative(matrix)
end

main()

Output

 -4 -3 -1 1 8
 -3 -2 2 4 6
 5 6 7 7 9
 -1 -1 1 5 8
 -2 4 7 8 9

 Total negative number is : 8
/*
    Scala Program for
    Count negative numbers in a sorted matrix
*/
class Counting()
{
	// Print matrix elements
	def printMatrix(matrix: Array[Array[Int]]): Unit = {
		var n: Int = matrix.length;
		var m: Int = matrix(0).length;
		var i: Int = 0;
		while (i < n)
		{
			var j: Int = 0;
			while (j < m)
			{
				print(" " + matrix(i)(j));
				j += 1;
			}
			print("\n");
			i += 1;
		}
	}
	def countNegative(matrix: Array[Array[Int]]): Unit = {
		var count: Int = 0;
		var j: Int = 0;
		var n: Int = matrix.length;
		var m: Int = matrix(0).length;
		var i: Int = 0;
		while (i < n)
		{
			// Count negative element at beginning of ith row
			while (j < m && matrix(i)(j) < 0)
			{
				j += 1;
			}
			// Update count
			count += j;
			// Reset j
			j = 0;
			i += 1;
		}
		// Display calculated result
		print("\n Total negative number is : " + count);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Counting = new Counting();
		var matrix: Array[Array[Int]] = Array(
          Array(-4, -3, -1, 1, 8), 
          Array(-3, -2, 2, 4, 6), 
          Array(5, 6, 7, 7, 9), 
          Array(-1, -1, 1, 5, 8), 
          Array(-2, 4, 7, 8, 9)
        );
		// Display matrix element
		task.printMatrix(matrix);
		// Display number of negative element in sorted matrix
		task.countNegative(matrix);
	}
}

Output

 -4 -3 -1 1 8
 -3 -2 2 4 6
 5 6 7 7 9
 -1 -1 1 5 8
 -2 4 7 8 9

 Total negative number is : 8
import Foundation;
/*
    Swift 4 Program for
    Count negative numbers in a sorted matrix
*/
class Counting
{
	// Print matrix elements
	func printMatrix(_ matrix: [
		[Int]
	])
	{
		let n: Int = matrix.count;
		let m: Int = matrix[0].count;
		var i: Int = 0;
		while (i < n)
		{
			var j: Int = 0;
			while (j < m)
			{
				print(" ", matrix[i][j], terminator: "");
				j += 1;
			}
			print(terminator: "\n");
			i += 1;
		}
	}
	func countNegative(_ matrix: [
		[Int]
	])
	{
		var count: Int = 0;
		var j: Int = 0;
		let n: Int = matrix.count;
		let m: Int = matrix[0].count;
		var i: Int = 0;
		while (i < n)
		{
			// Count negative element at beginning of ith row
			while (j < m && matrix[i][j] < 0)
			{
				j += 1;
			}
			// Update count
			count += j;
			// Reset j
			j = 0;
			i += 1;
		}
		// Display calculated result
		print("\n Total negative number is : ", count, terminator: "");
	}
}
func main()
{
	let task: Counting = Counting();
	let matrix: [
		[Int]
	] = [
		[-4, -3, -1, 1, 8],
		[-3, -2, 2, 4, 6],
		[5, 6, 7, 7, 9],
		[-1, -1, 1, 5, 8],
		[-2, 4, 7, 8, 9]
	];
	// Display matrix element
	task.printMatrix(matrix);
	// Display number of negative element in sorted matrix
	task.countNegative(matrix);
}
main();

Output

  -4  -3  -1  1  8
  -3  -2  2  4  6
  5  6  7  7  9
  -1  -1  1  5  8
  -2  4  7  8  9

 Total negative number is :  8
/*
    Kotlin Program for
    Count negative numbers in a sorted matrix
*/
class Counting
{
	// Print matrix elements
	fun printMatrix(matrix: Array < Array < Int >> ): Unit
	{
		val n: Int = matrix.count();
		val m: Int = matrix[0].count();
		var i: Int = 0;
		while (i < n)
		{
			var j: Int = 0;
			while (j < m)
			{
				print(" " + matrix[i][j]);
				j += 1;
			}
			print("\n");
			i += 1;
		}
	}
	fun countNegative(matrix: Array < Array < Int >> ): Unit
	{
		var count: Int = 0;
		var j: Int = 0;
		val n: Int = matrix.count();
		val m: Int = matrix[0].count();
		var i: Int = 0;
		while (i < n)
		{
			// Count negative element at beginning of ith row
			while (j < m && matrix[i][j] < 0)
			{
				j += 1;
			}
			// Update count
			count += j;
			// Reset j
			j = 0;
			i += 1;
		}
		// Display calculated result
		print("\n Total negative number is : " + count);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Counting = Counting();
	val matrix: Array < Array < Int >> = arrayOf(
      arrayOf(-4, -3, -1, 1, 8), 
      arrayOf(-3, -2, 2, 4, 6), 
      arrayOf(5, 6, 7, 7, 9), 
      arrayOf(-1, -1, 1, 5, 8), 
      arrayOf(-2, 4, 7, 8, 9)
    );
	// Display matrix element
	task.printMatrix(matrix);
	// Display number of negative element in sorted matrix
	task.countNegative(matrix);
}

Output

 -4 -3 -1 1 8
 -3 -2 2 4 6
 5 6 7 7 9
 -1 -1 1 5 8
 -2 4 7 8 9

 Total negative number is : 8

Output Explanation

The mentioned C code correctly implements the above algorithm to count the number of negative numbers in the sorted matrix. It defines the countNegative function to iterate through each row of the matrix and count the negative numbers. The output of the code is "Total negative number is: 8," which is the count of negative numbers in the given matrix.

Time Complexity

The time complexity of the mentioned solution is O(N * M), where N is the number of rows and M is the number of columns in the matrix. The countNegative function iterates through each row and checks the elements in each row in constant time, resulting in a total time complexity of O(N * M).

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment