Leetcode 52: N-Queens II

1. Problem Statement (Simple Explanation):

Same puzzle as N-Queens (problem 51):

Place n queens on an n x n chessboard so that no two queens attack each other:

Not in the same row
Not in the same column
Not on the same diagonal

But now:

Instead of returning all boards, you must return the number of distinct solutions.

2. Examples:

Example 1:

Input:

n = 4

There are exactly 2 valid configurations (same as problem 51’s example).

Output: 2

Example 2:

Input:

n = 1

Only one way to place a queen on 1x1 board.

Output: 1

3. Approach – Backtracking with Column & Diagonal Constraints:

This is almost identical to N-Queens (51), but we:

Don’t need to build the actual board strings.
Only need a counter of valid placements.

We still:

Place queens row by row.
Use three boolean arrays to track attacked lines:

colUsed[c] – column c is under attack.
diag1Used[row - col + n - 1] – main diagonal (top-left to bottom-right).
diag2Used[row + col] – anti-diagonal (top-right to bottom-left).

Whenever we reach row == n, we found one valid configuration → increment count.

Diagonal Indexing Recap:

For n x n board:

Main diagonal index: d1 = row - col + (n - 1) → range [0..2n-2].
Anti-diagonal index: d2 = row + col → range [0..2n-2].

So diag1Used and diag2Used are size 2n - 1.

Algorithm (Step-by-Step):

Initialize:

count = 0
colUsed[n], diag1Used[2n-1], diag2Used[2n-1] → all false.

Backtrack function dfs(row):

If row == n:

count++
return.

For each column c in 0..n-1:

d1 = row - c + n - 1
d2 = row + c
If any of colUsed[c], diag1Used[d1], diag2Used[d2] is true → skip.
Otherwise:

Set them to true (place queen).
Recurse dfs(row + 1).
Set them back to false (backtrack).

Call dfs(0) and return count.

Pseudo-code:

Complexity:

Same backtracking nature as N-Queens:

Time: Exponential in n, but n <= 9 is small enough.
Space: O(n) for recursion depth + constant-sized arrays (O(n) each).

4. Java code:

5. C++ code:

6. Python code:

7. JavaScript code:

8. C (outline) code:

In C you would:

Define bool colUsed[9], bool diag1Used[17], bool diag2Used[17], int count.
Implement dfs(row, n) similarly, updating and restoring booleans.
Return count.

Given n <= 9, fixed-size arrays are easy to use.

For brevity, full C code is omitted, but logic is identical to C++ with manual management of global or struct state.

Comments

Leetcode 1: Two Sum

Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to return the indices of two numbers in the array such that: Conditions: Each input has exactly one solution . You cannot use the same element twice . You can return the answer in any order . 2. Examples Example 1 Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Explanation: nums[0]+nums[1]=2+7=9 So we return [0, 1]. Example 2 Input: ...

Leetcode 3: Longest Substring Without Repeating Characters

Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input: s = "pwwkew" Output: 3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a single digit . The digits are stored in reverse order (i.e., the 1’s digit is at the head). You need to add the two numbers and return the sum as a linked list , also in reverse order. You can assume: There are no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input: l1 = [2,4,3] l2 = [5,6,4] Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output: [7,0,8] Explanation: ...

codesprint with rishav

Search This Blog