A sparse matrix, is a matrix where greater that half of total elements of matrix are 0. Given input matrix mat, check if it is a sparse matrix.
| Input |
Expected outputs |
mat = {
{1,0,0},
{1,0,0},
{1,0,0}}
|
The matrix is a Sparse Matrix.
|
mat= {
{0,2,4,0},
{0,1,2,0},
{0,3,1,0}}
|
The matrix is *not* a Sparse Matrix.
|
mat = {
{1,0},
{0,0},
{1,0},
{0,1}};
|
The matrix is a Sparse Matrix.
|
mat = {
{1,1,0,0},
{0,1,1,0},
{0,0,1,1},
{0,0,0,1}};
|
The matrix is a Sparse Matrix.
|
| The java method should accept following input parameters: mat (integer matrix).
|
| Initialize an int variable size with value equal to count of total elements in mat.
|
| Initialize an int variable zeroCnt to hold the count of 0s found in mat.
|
| Iterate through mat using a for loop, using variable rIdx as loop counter. Loop variable rIdx will be initialized with value 0 and will iterate through all the matrix’s columns one by one till rIdx < mat.length:
Iterate through mat using a for loop, using variable cIdx as loop counter. Loop variable cIdx will be initialized with value 0 and will iterate through all the matrix’s columns one by one till cIdx < mat[0].length:
If mat[rIdx][cIdx] == 0 negative, increment zeroCnt by 1.
If zeroCnt > size/2, return true from the program as the matrix is a sparse matrix.
|
| Once above loops are completed, and the program has not exited then this indicates zeroCnt is less than or equal to size/2, so return false from the program as the matrix is not a sparse matrix.
|
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding !
You can also tweak the code to optimize or add enhancements and custom features.
public class MdArraySparseMatrix {
public boolean matArraySparseMatrix(int[][] mat) throws Exception{
int size = mat.length * mat[0].length;
int zeroCnt=0;
for (int rIdx=0; rIdx < mat.length; rIdx++) {
for (int cIdx=0; cIdx < mat[0].length; cIdx++) {
if (mat[rIdx][cIdx] == 0) {
zeroCnt++;
}
if (zeroCnt > size/2) {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
MdArraySparseMatrix ap=new MdArraySparseMatrix();
boolean ret;
try {
int[][] arr = { {1,0,0},
{1,0,0},
{1,0,0}
};
print2dArray(arr, "The 2d Array");
ret=ap.matArraySparseMatrix(arr);
if (ret) {
System.out.println("\n The matrix is an Sparse Matrix");
}else {
System.out.println("\n The matrix is *not* an Sparse Matrix");
}
int[][] arr1 = { {0,2,4,0},
{0,1,2,0},
{0,3,1,0},
};
print2dArray(arr1, "The 2d Array");
ret=ap.matArraySparseMatrix(arr1);
if (ret) {
System.out.println("\n The matrix is an Sparse Matrix");
}else {
System.out.println("\n The matrix is *not* an Sparse Matrix");
}
int[][] arr2 = { {1,0},
{0,0},
{1,0},
{0,1}
};
print2dArray(arr2, "The 2d Array");
ret=ap.matArraySparseMatrix(arr2);
if (ret) {
System.out.println("\n The matrix is an Sparse Matrix");
}else {
System.out.println("\n The matrix is *not* an Sparse Matrix");
}
int[][] arr3 = { {1,1,0,0},
{0,1,1,0},
{0,0,1,1},
{0,0,0,1}
};
print2dArray(arr3, "The 2d Array");
ret=ap.matArraySparseMatrix(arr3);
if (ret) {
System.out.println("\n The matrix is an Sparse Matrix");
}else {
System.out.println("\n The matrix is *not* an Sparse Matrix");
}
}catch (Exception exception) {
System.out.print("Exception,"+ exception);
exception.printStackTrace();
}
}
public static void print2dArray(int[][] intArray, String label) throws Exception {
// Case 1: The input Array is null !!
if (intArray == null) { System.out.println("\n\n Input 2d Array was null !! \n"); return; }
// Case 2: Print input Array by index (first to last)
System.out.println();
System.out.println("*********************************************************************");
System.out.print(label+" : \n");
int rIdx=0; int cIdx=0;
for (rIdx=0; rIdx < intArray.length; rIdx++) {
for (cIdx=0; cIdx < intArray[rIdx].length; cIdx++) {
System.out.print(intArray[rIdx][cIdx]);
if (cIdx < intArray[rIdx].length) System.out.print(",");
}
System.out.print("\n");
}
System.out.println();
System.out.println("**********************************************************************");
System.out.println();
Thread.sleep(2000);
return;
}
}