A matrix is a collection of data elements arranged in a two-dimensional array-like structure, consisting of rows and columns. A matrix with a lot of zero values is called a sparse matrix. The program aims to count the number of zero values present in the matrix. If the number of zero values is more than half of the total number of elements in the matrix, then the matrix is considered sparse, and the output is “YES.” Otherwise, the matrix is not sparse, and the output is “NO.” This program determines whether a matrix is sparse or not by comparing the number of zero values to half of the total number of elements in the matrix.
Examples:
Input: 1 0 3
0 0 4
6 0 0
Output: Yes
Explanation:There are 5 zeros in the matrix which
is more than half of the matrix size.
Input: 1 2 3
0 7 8
5 0 7
Output: No
Explanation:There are 2 zeros in the matrix which
is less than half of the matrix size.
To check whether a matrix is a sparse matrix we only need to check the total number of elements that are equal to zero. If this count is more than (m * n)/2 then print Yes else No. There are two approaches to do so.
In this approach, we will check whether a matrix is a sparse matrix or not.
- Take the matrix.
- Traverse the matrix’s element one by one and counting the number of zeros.
- Checking if the count is more than (m*n)/2, if yes else no.
Below is the implementation of the above approach:
Java
// Java Program to Determine if a given// Matrix is a Sparse Matrix// Importing Librariesimport java.io.*;class GFG { // Driver Function public static void main(String args[]) { // Initialising and declaring // variables and array int array[][] = { { 1, 0, 3 }, { 0, 0, 4 }, { 6, 0, 0 } }; int m = 3; int n = 3; int counter = 0; // Count number of zeros in the matrix for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (array[i][j] == 0) ++counter; // Printing result if (counter > ((m * n) / 2)) System.out.println("Yes"); else System.out.println("No"); }} |
Yes
Time Complexity: O(m*n) where m is no of rows and n is no of columns in matrix
Auxiliary Space: O(1)
Space complexity: Space complexity of this code is O(1) because the space used by the program is constant, regardless of the input size. The program only uses a fixed amount of space to declare and initialize variables and arrays, and does not create any new objects or data structures that grow in size with the input. Therefore, the space used by the program remains constant, and the space complexity is O(1).
