CODEWITHSUNDEEP
javaarrays
antimuon
antimuon

Reputation: 262

Java - Count remaining false in a 2D Boolean Array

I have a 2D Boolean array array and I am looking to count the number of false remaining after applying a rule with respect to where a row or column has a true.

If a row or column has a true value then I need to reduce the count of the number of false occurrences in the 2D array by the row and column in which the true appears.

e.g.

If a true arrears in the first row and column matrix[0][0] and all other entries in matrix[0][j] and matrix[i][0] are false then I need to exclude those false in the count of false remaining. 

    [0],  [1]
[0] TRUE, FALSE
[1] FALSE FALSE

So when I apply the rule there is only one false that doesn't have a true in its row or column, i.e, matrix[1][1].

I can't generalize the the loop iteration, it works in some situations but not others. The first two examples below are correct but the third example is not correct as it should be 6 not 4.

The reason I can see is that in third array there is a true that is in the same column (matrix3[2][4]) (highlighted in matrix3) which was already knocked out of the calculation so the answer is getting reduced by two too many.

Is there a way I can keep track of columns and rows that where already taken out of the count?

public class CountRemainingFalse {
    public int countRemainingFalse (int n, boolean[][] matrix) {
        int count = n * n;

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                if (matrix[i][j]) {
                    count = count - (2 * n - 1);
                    n--;
                    break;
                }
            }
        }
        return count;
    }
}

class CountFalseRemainingApp {
    public static void main(String[] args) {
        CountRemainingFalse crf = new CountRemainingFalse();

        boolean matrix1[][] = {
                {false, false, false, false, false, false},
                {false, false, true, true, false, false},
                {false, false, true, true, false, false},
                {false, false, false, false, false, false},
                {false, false, false, false, false, false},
                {false, false, false, false, false, false} };

        boolean matrix2[][] = {
                {false, false, false, false, true, false},
                {false, false, true, true, false, false},
                {false, false, true, true, false, false},
                {false, false, false, false, false, false},
                {false, false, false, false, false, false},
                {false, false, false, false, false, false} };

        boolean matrix3[][] = {
                {false, false, false, false, true, false},
                {false, false, false, true, false, false},
                {false, false, false, false, **true**, false},
                {false, true, false, false, false, false},
                {false, false, false, false, false, false},
                {false, false, false, false, false, false} };


        System.out.println(crf.countRemainingFalse(6, matrix1));
        System.out.println(crf.countRemainingFalse(6, matrix2));
        System.out.println(crf.countRemainingFalse(6, matrix3));
    }
}

Output is:

16 // correct
9  // correct
4  // incorrect should be 6 (matrix3[0][4] was already accounted for but matrix3[2][4] also has a true)

Upvotes: 0

Views: 597

Answers (2)

muzzlator
muzzlator

Reputation: 742

You can just do two passes, first part to find out which rows and columns are banned, second pass to count:

boolean[] bannedRows = new boolean[n];
boolean[] bannedColumns = new boolean[n];
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    if (matrix[i][j]) {
      bannedRows[i] = true;
      bannedColumns[j] = true;
    }
  }
}
int count = 0;
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    if (!bannedRows[i] && !bannedColumns[j]) {
      count++;
    }
  }
}
return count;

Edit: A note on premature optimization: Prefer simple, obviously correct code over unnecessarily optimized code that is hard to read and hard to understand if it's correct. Optimize once there is a pressing need to optimize and you've verified that this function is a cause of the slowness

Upvotes: 1

Bohan
Bohan

Reputation: 1

You could use an array of booleans to keep track of columns. I believe your code will run into the problem you stated when there is more than one true in a column of your matrix. The array would have the same size as your columns, and when you run into a true, set the value in the array to true. So this way, once you run into another true that is presented in the same column, the code won't execute.

Here is an example implementation: 

boolean[] alreadyPresent = new boolean[matrix[0].length];    
for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix.length; j++) {
            if (matrix[i][j] && !alreadyPresent[j]) {
                alreadyPresent[j] = true;
                count = count - (2 * n - 1);
                n--;
                break;
            }
        }
    }
    return count;
}

Upvotes: 0

Related Questions