How can we lower the time complexity of this solution of NxN queens matrix validator? I have this solution while I check every row and every column and every diagonal of the matrix. If every row and column has exactly 1 queen, and the matrix has no more than 1 queen the output is true. This solution works but I think it’s brute force.
public static boolean solveMatrix(int[][] matrix) {
int row, col;
int rowCount = matrix.length;
int columnCount = matrix[0].length;
int counter = 0;
// Checking if there is 1 queen per row
for (int i = 0; i < 8; i++) {
counter = 0;
for (int j = 0; j < 8; j++) {
if (matrix[i][j] == 1) {
counter++;
}
}
if (counter != 1) {
return false;
}
}
// Checking if there is 1 queen per column
for (int i = 0; i < 8; i++) {
counter = 0;
for (int j = 0; j < 8; j++) {
if (matrix[j][i] == 1) {
counter++;
}
}
if (counter != 1) {
return false;
}
}
// Checking first side diagonals
for (int k = 0; k < rowCount; k++) {
counter = 0;
for (row = k, col = 0; row >= 0 && col < columnCount; row--, col++) {
if (matrix[row][col] == 1) {
counter++;
}
}
if (counter > 1) {
return false;
}
}
// Checking first side diagonals
for (int k = 1; k < columnCount; k++) {
counter = 0;
for (row = rowCount - 1, col = k; row >= 0 && col < columnCount; row--, col++) {
if (matrix[row][col] == 1) {
counter++;
}
}
if (counter > 1) {
return false;
}
}
// Checking second side diagonals
for (int k = rowCount - 1; k >= 0; k--) {
counter = 0;
for (row = k, col = columnCount - 1; row >= 0 && col >= 0; row--, col--) {
if (matrix[row][col] == 1) {
counter++;
}
}
if (counter > 1) {
return false;
}
}
// Checking second side diagonals
for (int k = rowCount - 1; k >= 0; k--) {
counter = 0;
for (row = k, col = columnCount - 1; row >= 0 && col >= 0; row--, col--) {
if (matrix[row][col] == 1) {
counter++;
}
}
if (counter > 1) {
return false;
}
}
return true;
}
Advertisement
Answer
You need to use 4 hashmaps, one for columns, one for rows, one for left to right diagonals, and one for right to left diagonals.
Now, do just one nested loop for rows and columns. When you find a queen do the following 4 steps:
- Check if at that row index there is a queen in the row hashmap. If not, add the row index. If there is already one, return false.
- Check if at that col index there is a queen in the col hashmap. If not, add the col index. If there is already one, return false.
- Check if at that left to right diagonal, there is one queen in the left to right diagonal hashmap and act accordingly. Note that for each left to right diagonal
rowIndex-columnIndexis always the same. - Check if at that right to left diagonal, there is one queen in the right to left diagonal hashmap and act accordingly. Note that for each right to left diagonal
rowIndex+columnIndexis always the same.
If you successfully completed the above nested loop, it means that the board is valid. Return true.
This algorithm runs in O(n^2) where n is the length of one side of the square matrix.
It has a linear space complexity in the length of the side of the matrix n, since we are using 4 hashmaps with each n elements at most.