LeetCode 52: N-Queens II Solution

Master LeetCode problem 52 (N-Queens II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

52. N-Queens II

Hard

Backtracking

Problem Explanation

Explanation:

To solve the N-Queens II problem, we can utilize backtracking. The goal is to place N queens on an N x N chessboard such that no two queens attack each other. We can use recursion to explore all possible placements of queens on each row and backtrack when a solution is not valid.

Algorithm:

Create a board of size N x N to represent the chessboard.
Define a helper method that takes the current row as a parameter.
In the helper method, iterate through each column in the current row and try to place a queen.
Check if the placement is valid by ensuring no queens are attacking each other horizontally, vertically, or diagonally.
If the placement is valid, mark the cell as a queen and recursively move to the next row.
If all rows are filled without conflicts, increment the count of valid solutions.
Backtrack by removing the queen and continue exploring other placements.
Return the count of valid solutions.

Time Complexity:

The time complexity of this approach is O(N!) where N is the number of queens or the size of the chessboard.

Space Complexity:

The space complexity is O(N) for storing the board and the recursive call stack.

: :

Solution Code

class Solution {
    int count = 0;
    
    public int totalNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }
        solveNQueens(board, 0);
        return count;
    }
    
    private void solveNQueens(char[][] board, int row) {
        if (row == board.length) {
            count++;
            return;
        }
        
        for (int col = 0; col < board.length; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                solveNQueens(board, row + 1);
                board[row][col] = '.';
            }
        }
    }
    
    private boolean isValid(char[][] board, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
            int diff = row - i;
            if (col - diff >= 0 && board[i][col - diff] == 'Q') return false;
            if (col + diff < board.length && board[i][col + diff] == 'Q') return false;
        }
        return true;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 52 (N-Queens II)?

This page provides optimized solutions for LeetCode problem 52 (N-Queens II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 52 (N-Queens II)?

The time complexity for LeetCode 52 (N-Queens II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 52 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 52 in Java, C++, or Python.

Back to LeetCode Solutions