Java - Count remaining false in a 2D Boolean Array

Question

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)

I think you'll need to define your rule more precisely. I don't really understand this: "reduce the count by the whole row and column in which it appears". How can you reduce the count by row or column? Count is an interer and row or column is an array. — lexicore
– lexicore, Commented Apr 6, 2018 at 14:14

muzzlator · Accepted Answer · 2018-04-06 14:53:46Z

1

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

edited Apr 6, 2018 at 14:53

answered Apr 6, 2018 at 14:36

muzzlator

7424 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Bohan · Accepted Answer · 2018-04-06 14:38:58Z

0

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;
}

answered Apr 6, 2018 at 14:38

Bohan

11 bronze badge

2 Comments

muzzlator Over a year ago

I'm skeptical that this will work. A single true value eliminates the entire row and column, but this is only considering columns

antimuon Over a year ago

This doesn't work but I will have a look to see why it doesn't.

Collectives™ on Stack Overflow

Java - Count remaining false in a 2D Boolean Array

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related