N-Queens II (Count Solutions)

🎯

N-Queens II (Count Solutions)

hardBACKTRACKINGAmazonGoogle

Imagine placing queens on a chessboard so that none can attack each other, and you want to know how many ways this can be done without listing them all.

💡 This problem is a classic example of backtracking where the challenge is to explore all valid configurations efficiently. Beginners often struggle because the search space grows exponentially and pruning invalid states early is crucial.

📋

Problem Statement

Given an integer n, return the number of distinct solutions to the n-queens puzzle. The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

1 ≤ n ≤ 14The output fits in a 32-bit integer

💡

Example

Input"4"

Output2

There are two distinct ways to place 4 queens on a 4x4 board so that none attack each other.

Input"1"

Output1

Only one queen on a 1x1 board, so one solution.

• n = 1 → 1 solution
• n = 2 → 0 solutions (no valid placements)
• n = 3 → 0 solutions (no valid placements)
• n = 14 → large input to test performance and pruning

⚠️

Common Mistakes

Not checking diagonal conflicts correctly

Incorrect solutions counted or missed

✅ Check both positive and negative diagonals using row+col and row-col

Modifying shared state without backtracking

Incorrect counts due to state pollution

✅ Always undo changes (remove queen) after recursive calls

Using inefficient conflict checks scanning all previous rows

Solution too slow for larger n

✅ Use sets or bitmasks to check conflicts in O(1)

Not handling base case correctly

Missed counting valid solutions or infinite recursion

✅ Return count when row == n

Bitmask overflow or incorrect bit shifts

Wrong results or runtime errors

✅ Ensure bit operations are within integer limits and shifts are correct

🧠

Brute Force (Pure Recursion with Board Validation)

💡 Starting with brute force helps understand the problem's exponential search space and the importance of pruning invalid states early.

Intuition

Try placing a queen in every column of the current row and recursively attempt to place queens in subsequent rows, checking for conflicts each time.

Algorithm

1. Start from the first row and try placing a queen in each column.
2. For each placement, check if it conflicts with previously placed queens.
3. If no conflict, move to the next row and repeat.
4. If all queens are placed successfully, increment the solution count.

💡 The challenge is to systematically explore all placements and backtrack when conflicts arise, which is the essence of backtracking.

</>

Code

class Solution:
    def totalNQueens(self, n: int) -> int:
        def is_safe(row, col):
            for r in range(row):
                c = queens[r]
                if c == col or abs(c - col) == abs(r - row):
                    return False
            return True

        def backtrack(row):
            if row == n:
                return 1
            count = 0
            for col in range(n):
                if is_safe(row, col):
                    queens[row] = col
                    count += backtrack(row + 1)
            return count

        queens = [-1] * n
        return backtrack(0)

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.totalNQueens(4))  # Output: 2

Line Notes

def is_safe(row, col):Defines a helper to check if placing a queen at (row, col) is valid

for r in range(row):Iterates over previously placed queens to check conflicts

if c == col or abs(c - col) == abs(r - row):Checks same column or diagonal conflicts

if row == n:Base case: all queens placed successfully

for col in range(n):Try placing queen in each column of current row

queens[row] = colRecord queen's position for current row

count += backtrack(row + 1)Recurse to next row and accumulate valid solutions

queens = [-1] * nInitialize queen positions with invalid column

public class Solution {
    private int count = 0;
    public int totalNQueens(int n) {
        int[] queens = new int[n];
        backtrack(0, n, queens);
        return count;
    }
    private void backtrack(int row, int n, int[] queens) {
        if (row == n) {
            count++;
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(row, col, queens)) {
                queens[row] = col;
                backtrack(row + 1, n, queens);
            }
        }
    }
    private boolean isSafe(int row, int col, int[] queens) {
        for (int r = 0; r < row; r++) {
            int c = queens[r];
            if (c == col || Math.abs(c - col) == Math.abs(r - row)) {
                return false;
            }
        }
        return true;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.totalNQueens(4)); // Output: 2
    }
}

Line Notes

private int count = 0;Stores total number of valid solutions

int[] queens = new int[n];Array to track queen positions by row

if (row == n)Base case: all queens placed

for (int col = 0; col < n; col++)Try each column in current row

if (isSafe(row, col, queens))Check if placing queen is valid

queens[row] = col;Place queen at current row and column

backtrack(row + 1, n, queens);Recurse to next row

for (int r = 0; r < row; r++)Check conflicts with previously placed queens

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class Solution {
public:
    int totalNQueens(int n) {
        vector<int> queens(n, -1);
        return backtrack(0, n, queens);
    }
private:
    bool isSafe(int row, int col, const vector<int>& queens) {
        for (int r = 0; r < row; r++) {
            int c = queens[r];
            if (c == col || abs(c - col) == abs(r - row))
                return false;
        }
        return true;
    }
    int backtrack(int row, int n, vector<int>& queens) {
        if (row == n) return 1;
        int count = 0;
        for (int col = 0; col < n; col++) {
            if (isSafe(row, col, queens)) {
                queens[row] = col;
                count += backtrack(row + 1, n, queens);
            }
        }
        return count;
    }
};

int main() {
    Solution sol;
    cout << sol.totalNQueens(4) << endl; // Output: 2
    return 0;
}

Line Notes

vector<int> queens(n, -1);Initialize queen positions with invalid column

if (row == n) return 1;Base case: all queens placed successfully

for (int col = 0; col < n; col++)Try placing queen in each column

if (isSafe(row, col, queens))Check if current placement is valid

count += backtrack(row + 1, n, queens);Recurse to next row and accumulate solutions

for (int r = 0; r < row; r++)Check conflicts with previously placed queens

int c = queens[r];Get column of queen in previous row

abs(c - col) == abs(r - row)Check diagonal conflicts

var totalNQueens = function(n) {
    const queens = new Array(n).fill(-1);
    function isSafe(row, col) {
        for (let r = 0; r < row; r++) {
            const c = queens[r];
            if (c === col || Math.abs(c - col) === Math.abs(r - row)) {
                return false;
            }
        }
        return true;
    }
    function backtrack(row) {
        if (row === n) return 1;
        let count = 0;
        for (let col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                queens[row] = col;
                count += backtrack(row + 1);
            }
        }
        return count;
    }
    return backtrack(0);
};

// Driver code
console.log(totalNQueens(4)); // Output: 2

Line Notes

const queens = new Array(n).fill(-1);Initialize queen positions with invalid column

if (row === n) return 1;Base case: all queens placed successfully

for (let col = 0; col < n; col++)Try placing queen in each column

if (isSafe(row, col))Check if current placement is valid

count += backtrack(row + 1);Recurse to next row and accumulate solutions

for (let r = 0; r < row; r++)Check conflicts with previously placed queens

const c = queens[r];Get column of queen in previous row

Math.abs(c - col) === Math.abs(r - row)Check diagonal conflicts

⏱

Complexity

TimeO(n!)

SpaceO(n)

Each row tries n columns, but pruning reduces the search space to roughly n! permutations.

💡 For n=8, this means about 40,000 operations, which is borderline but still feasible; for n=14, it becomes impractical.

Interview Verdict: TLE for large n

This approach is too slow for large boards but is essential to understand the problem and backtracking basics.

🧠

Backtracking with Hash Sets for Conflict Checking

💡 Using hash sets to track columns and diagonals speeds up conflict checking, reducing repeated scanning of previous rows.

Intuition

Instead of scanning all previous rows for conflicts, maintain sets of occupied columns and diagonals to check conflicts in O(1).

Algorithm

1. Initialize sets to track columns, positive diagonals, and negative diagonals under attack.
2. For each row, try placing a queen in columns not in the attacked sets.
3. If safe, add the column and diagonals to the sets and recurse to next row.
4. Backtrack by removing the queen and updating sets accordingly.
5. Count solutions when all rows are processed.

💡 This approach avoids scanning all previous queens by using sets, making conflict checks much faster.

</>

Code

class Solution:
    def totalNQueens(self, n: int) -> int:
        cols = set()
        pos_diags = set()  # r + c
        neg_diags = set()  # r - c

        def backtrack(row):
            if row == n:
                return 1
            count = 0
            for col in range(n):
                if col in cols or (row + col) in pos_diags or (row - col) in neg_diags:
                    continue
                cols.add(col)
                pos_diags.add(row + col)
                neg_diags.add(row - col)
                count += backtrack(row + 1)
                cols.remove(col)
                pos_diags.remove(row + col)
                neg_diags.remove(row - col)
            return count

        return backtrack(0)

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.totalNQueens(4))  # Output: 2

Line Notes

cols = set()Tracks columns already occupied by queens

pos_diags = set() # r + cTracks positive diagonals under attack

neg_diags = set() # r - cTracks negative diagonals under attack

if col in cols or (row + col) in pos_diags or (row - col) in neg_diags:Skip if placing queen causes conflict

cols.add(col)Mark column as occupied

pos_diags.add(row + col)Mark positive diagonal as occupied

neg_diags.add(row - col)Mark negative diagonal as occupied

cols.remove(col)Backtrack: unmark column

return backtrack(0)Start backtracking from first row

import java.util.HashSet;

public class Solution {
    private int count = 0;
    public int totalNQueens(int n) {
        HashSet<Integer> cols = new HashSet<>();
        HashSet<Integer> posDiags = new HashSet<>(); // r + c
        HashSet<Integer> negDiags = new HashSet<>(); // r - c
        backtrack(0, n, cols, posDiags, negDiags);
        return count;
    }
    private void backtrack(int row, int n, HashSet<Integer> cols, HashSet<Integer> posDiags, HashSet<Integer> negDiags) {
        if (row == n) {
            count++;
            return;
        }
        for (int col = 0; col < n; col++) {
            if (cols.contains(col) || posDiags.contains(row + col) || negDiags.contains(row - col))
                continue;
            cols.add(col);
            posDiags.add(row + col);
            negDiags.add(row - col);
            backtrack(row + 1, n, cols, posDiags, negDiags);
            cols.remove(col);
            posDiags.remove(row + col);
            negDiags.remove(row - col);
        }
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.totalNQueens(4)); // Output: 2
    }
}

Line Notes

HashSet<Integer> cols = new HashSet<>();Tracks occupied columns

HashSet<Integer> posDiags = new HashSet<>();Tracks positive diagonals under attack

HashSet<Integer> negDiags = new HashSet<>();Tracks negative diagonals under attack

if (cols.contains(col) || posDiags.contains(row + col) || negDiags.contains(row - col))Skip invalid placements

cols.add(col);Mark column as occupied

posDiags.add(row + col);Mark positive diagonal as occupied

negDiags.add(row - col);Mark negative diagonal as occupied

cols.remove(col);Backtrack: unmark column

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int totalNQueens(int n) {
        unordered_set<int> cols, posDiags, negDiags;
        return backtrack(0, n, cols, posDiags, negDiags);
    }
private:
    int backtrack(int row, int n, unordered_set<int>& cols, unordered_set<int>& posDiags, unordered_set<int>& negDiags) {
        if (row == n) return 1;
        int count = 0;
        for (int col = 0; col < n; col++) {
            if (cols.count(col) || posDiags.count(row + col) || negDiags.count(row - col))
                continue;
            cols.insert(col);
            posDiags.insert(row + col);
            negDiags.insert(row - col);
            count += backtrack(row + 1, n, cols, posDiags, negDiags);
            cols.erase(col);
            posDiags.erase(row + col);
            negDiags.erase(row - col);
        }
        return count;
    }
};

int main() {
    Solution sol;
    cout << sol.totalNQueens(4) << endl; // Output: 2
    return 0;
}

Line Notes

unordered_set<int> cols, posDiags, negDiags;Sets to track attacked columns and diagonals

if (cols.count(col) || posDiags.count(row + col) || negDiags.count(row - col))Skip invalid queen placements

cols.insert(col);Mark column as occupied

posDiags.insert(row + col);Mark positive diagonal as occupied

negDiags.insert(row - col);Mark negative diagonal as occupied

cols.erase(col);Backtrack: unmark column

return backtrack(0, n, cols, posDiags, negDiags);Start backtracking from first row

if (row == n) return 1;Base case: all queens placed

var totalNQueens = function(n) {
    const cols = new Set();
    const posDiags = new Set(); // r + c
    const negDiags = new Set(); // r - c

    function backtrack(row) {
        if (row === n) return 1;
        let count = 0;
        for (let col = 0; col < n; col++) {
            if (cols.has(col) || posDiags.has(row + col) || negDiags.has(row - col)) continue;
            cols.add(col);
            posDiags.add(row + col);
            negDiags.add(row - col);
            count += backtrack(row + 1);
            cols.delete(col);
            posDiags.delete(row + col);
            negDiags.delete(row - col);
        }
        return count;
    }

    return backtrack(0);
};

// Driver code
console.log(totalNQueens(4)); // Output: 2

Line Notes

const cols = new Set();Tracks occupied columns

const posDiags = new Set();Tracks positive diagonals under attack

const negDiags = new Set();Tracks negative diagonals under attack

if (cols.has(col) || posDiags.has(row + col) || negDiags.has(row - col))Skip invalid queen placements

cols.add(col);Mark column as occupied

posDiags.add(row + col);Mark positive diagonal as occupied

negDiags.add(row - col);Mark negative diagonal as occupied

cols.delete(col);Backtrack: unmark column

⏱

Complexity

TimeO(n!)

SpaceO(n)

Conflict checks are O(1) due to sets, but the search space remains factorial in n.

💡 This optimization makes the solution practical for n up to around 14, which is the problem constraint.

Interview Verdict: Accepted

This approach is efficient enough for the problem constraints and is a common interview solution.

🧠

Backtracking with Bitmask Optimization

💡 Using bitmasks to represent columns and diagonals reduces memory and speeds up conflict checks, enabling very fast pruning.

Intuition

Represent columns and diagonals as bits in integers; use bitwise operations to quickly check and update attacked positions.

Algorithm

1. Use three integers to track columns, positive diagonals, and negative diagonals under attack.
2. At each row, compute available positions by bitwise negation and AND with mask.
3. Iterate over each available position by extracting the rightmost set bit.
4. Place queen by updating bitmasks and recurse to next row.
5. Backtrack by restoring bitmasks; count solutions when all rows are placed.

💡 Bitmasking allows constant-time conflict checks and efficient iteration over valid positions, drastically reducing overhead.

</>

Code

class Solution:
    def totalNQueens(self, n: int) -> int:
        def backtrack(row, cols, pos_diags, neg_diags):
            if row == n:
                return 1
            count = 0
            available_positions = ((1 << n) - 1) & ~(cols | pos_diags | neg_diags)
            while available_positions:
                position = available_positions & -available_positions  # rightmost 1-bit
                available_positions &= available_positions - 1  # remove rightmost 1-bit
                count += backtrack(row + 1,
                                   cols | position,
                                   (pos_diags | position) << 1,
                                   (neg_diags | position) >> 1)
            return count

        return backtrack(0, 0, 0, 0)

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.totalNQueens(4))  # Output: 2

Line Notes

available_positions = ((1 << n) - 1) & ~(cols | pos_diags | neg_diags)Calculate all free columns for current row

position = available_positions & -available_positionsExtract rightmost available position to try

available_positions &= available_positions - 1Remove the tried position from available positions

count += backtrack(row + 1, cols | position, (pos_diags | position) << 1, (neg_diags | position) >> 1)Recurse with updated attacked positions

if row == n:Base case: all queens placed

return backtrack(0, 0, 0, 0)Start recursion with empty board

public class Solution {
    private int count = 0;
    public int totalNQueens(int n) {
        backtrack(n, 0, 0, 0, 0);
        return count;
    }
    private void backtrack(int n, int row, int cols, int posDiags, int negDiags) {
        if (row == n) {
            count++;
            return;
        }
        int availablePositions = ((1 << n) - 1) & ~(cols | posDiags | negDiags);
        while (availablePositions != 0) {
            int position = availablePositions & (-availablePositions);
            availablePositions &= availablePositions - 1;
            backtrack(n, row + 1, cols | position, (posDiags | position) << 1, (negDiags | position) >> 1);
        }
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.totalNQueens(4)); // Output: 2
    }
}

Line Notes

int availablePositions = ((1 << n) - 1) & ~(cols | posDiags | negDiags);Calculate free columns for current row

int position = availablePositions & (-availablePositions);Extract rightmost available position

availablePositions &= availablePositions - 1;Remove tried position

backtrack(n, row + 1, cols | position, (posDiags | position) << 1, (negDiags | position) >> 1);Recurse with updated attacked positions

if (row == n)Base case: all queens placed

count++Increment solution count

#include <iostream>
using namespace std;

class Solution {
public:
    int count = 0;
    int totalNQueens(int n) {
        backtrack(n, 0, 0, 0, 0);
        return count;
    }
private:
    void backtrack(int n, int row, int cols, int posDiags, int negDiags) {
        if (row == n) {
            count++;
            return;
        }
        int availablePositions = ((1 << n) - 1) & ~(cols | posDiags | negDiags);
        while (availablePositions) {
            int position = availablePositions & (-availablePositions);
            availablePositions &= availablePositions - 1;
            backtrack(n, row + 1, cols | position, (posDiags | position) << 1, (negDiags | position) >> 1);
        }
    }
};

int main() {
    Solution sol;
    cout << sol.totalNQueens(4) << endl; // Output: 2
    return 0;
}

Line Notes

int availablePositions = ((1 << n) - 1) & ~(cols | posDiags | negDiags);Calculate free columns for current row

int position = availablePositions & (-availablePositions);Extract rightmost available position

availablePositions &= availablePositions - 1;Remove tried position

backtrack(n, row + 1, cols | position, (posDiags | position) << 1, (negDiags | position) >> 1);Recurse with updated attacked positions

if (row == n)Base case: all queens placed

count++Increment solution count

var totalNQueens = function(n) {
    let count = 0;
    function backtrack(row, cols, posDiags, negDiags) {
        if (row === n) {
            count++;
            return;
        }
        let availablePositions = ((1 << n) - 1) & ~(cols | posDiags | negDiags);
        while (availablePositions) {
            let position = availablePositions & (-availablePositions);
            availablePositions &= availablePositions - 1;
            backtrack(row + 1, cols | position, (posDiags | position) << 1, (negDiags | position) >> 1);
        }
    }
    backtrack(0, 0, 0, 0);
    return count;
};

// Driver code
console.log(totalNQueens(4)); // Output: 2

Line Notes

let availablePositions = ((1 << n) - 1) & ~(cols | posDiags | negDiags);Calculate free columns for current row

let position = availablePositions & (-availablePositions);Extract rightmost available position

availablePositions &= availablePositions - 1;Remove tried position

backtrack(row + 1, cols | position, (posDiags | position) << 1, (negDiags | position) >> 1);Recurse with updated attacked positions

if (row === n)Base case: all queens placed

count++Increment solution count

⏱

Complexity

TimeO(n!)

SpaceO(n)

Bitmasking reduces overhead of conflict checks to O(1), but the search space remains factorial.

💡 This approach is the fastest practical solution for n up to 14, the problem's upper limit.

Interview Verdict: Accepted

This is the optimal approach for this problem and is often expected in high-level interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, approach 2 or 3 is usually best to code; approach 1 is good to explain but not to implement fully.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n!)	O(n)	Yes (deep recursion)	Yes	Mention only - never code
2. Backtracking with Sets	O(n!)	O(n)	Yes	Yes	Code this for clarity and efficiency
3. Bitmask Optimization	O(n!)	O(n)	Yes	Yes	Code this for optimal performance if comfortable with bit operations

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force approach to show understanding of the problem.Step 3: Optimize conflict checking using sets for faster pruning.Step 4: Present bitmask optimization for maximum efficiency.Step 5: Code the chosen approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of backtracking, pruning invalid states, and optimizing conflict checks to handle large inputs efficiently.

Common Follow-ups

• How would you print all solutions instead of counting? → Modify to store board states.
• Can you optimize space usage? → Use bitmasking to reduce memory.
• What if n is very large? → Problem becomes infeasible; discuss heuristics or approximations.
• How to handle symmetry to reduce computations? → Prune symmetric solutions by fixing first queen.

💡 These follow-ups test your ability to adapt the solution, optimize further, and understand problem variations.

🔍

Pattern Recognition

When to Use

1) Problem involves placing items on a grid with constraints; 2) Need to explore all valid configurations; 3) Constraints involve rows, columns, diagonals; 4) Counting or listing solutions.

Signature Phrases

place n queensno two queens attackcount distinct solutions

NOT This Pattern When

Problems that only require greedy or DP without backtracking, e.g., longest increasing subsequence.

Similar Problems

N-Queens I - prints all solutions instead of countingSudoku Solver - similar constraint satisfaction on gridWord Search II - backtracking with pruning on grid

Practice

1. You need to generate all combinations of balanced parentheses pairs for a given number n. Which algorithmic approach guarantees generating only valid sequences without generating invalid ones first?

easy

A. Brute force: generate all possible sequences of '(' and ')' of length 2n, then filter valid ones

B. Backtracking with pruning: build sequences by adding '(' or ')' only when it keeps the sequence valid

C. Greedy approach: always add '(' until n is reached, then add ')' to close all opened parentheses

D. Dynamic programming: count the number of valid sequences using Catalan number formula

Solution

1. Step 1: Understand problem constraints

   We want to generate all valid parentheses sequences without generating invalid ones first.

2. Step 2: Analyze approaches

   Brute force generates all sequences including invalid ones, greedy fails to generate all valid sequences, DP counts sequences but does not generate them. Backtracking with pruning adds '(' or ')' only when valid, thus generating only valid sequences.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Backtracking with pruning avoids invalid sequences [OK]

Hint: Backtracking prunes invalid sequences early [OK]

Common Mistakes:

• Thinking greedy can generate all valid sequences
• Confusing counting with generating sequences

2. You need to place n queens on an nxn chessboard so that no two queens threaten each other (no two queens share the same row, column, or diagonal). Which algorithmic approach guarantees finding all valid solutions efficiently by pruning invalid partial placements early?

easy

A. Backtracking with pruning to avoid columns and diagonals already attacked

B. Greedy algorithm that places queens row by row choosing the first safe column

C. Dynamic programming to count valid queen placements using subproblems

D. Breadth-first search exploring all board states level by level

Solution

1. Step 1: Understand problem constraints

   The problem requires placing queens so none attack each other, which involves checking columns and diagonals.

2. Step 2: Identify algorithm that prunes invalid states early

   Backtracking with pruning efficiently avoids exploring invalid partial solutions by tracking attacked columns and diagonals.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking prunes invalid states early [OK]

Hint: Pruning columns and diagonals is key to efficient search [OK]

Common Mistakes:

• Thinking greedy placement always works
• Assuming DP applies directly
• Confusing BFS with pruning

3. You need to generate all unique permutations of an array that may contain duplicate elements. Which approach guarantees generating all unique permutations efficiently without producing duplicates during generation?

easy

A. Use a greedy algorithm that picks the smallest unused element at each step.

B. Use backtracking with sorting and a mechanism to skip duplicates during recursion.

C. Use dynamic programming to build permutations from smaller subproblems.

D. Generate all permutations and then filter duplicates using a hash set.

Solution

1. Step 1: Understand the problem constraints

   The problem requires generating all unique permutations of an array with duplicates, so duplicates must be avoided during generation to be efficient.

2. Step 2: Evaluate approaches

   Greedy algorithms do not guarantee all permutations; DP is not suitable here; generating all permutations and filtering duplicates is correct but inefficient. Backtracking with sorting and skipping duplicates during recursion ensures duplicates are pruned early.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Backtracking with duplicate skipping is the standard optimal approach [OK]

Hint: Skip duplicates during backtracking after sorting [OK]

Common Mistakes:

• Thinking greedy or DP can generate unique permutations efficiently

4. What is the time complexity of the optimal in-place next permutation algorithm for an input array of length n?

medium

A. O(n) because it scans the array a constant number of times

B. O(n log n) because it sorts the suffix after the pivot

C. O(n!) due to generating all permutations

D. O(n^2) because it swaps elements multiple times in nested loops

Solution

1. Step 1: Identify the main operations

   The algorithm scans from the end to find the pivot (O(n)), then scans again to find the swap element (O(n)), and finally reverses the suffix (O(n)).

2. Step 2: Sum up the operations

   All steps are linear scans or swaps, so total time complexity is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No sorting or factorial generation involved, linear scans only [OK]

Hint: Next permutation scans array linearly multiple times [OK]

Common Mistakes:

• Confusing suffix reversal with sorting
• Assuming factorial due to permutations

5. What is the time complexity of the optimal factorial-based algorithm to find the k-th permutation of n numbers, and why?

medium

A. O(n^2) because each of the n iterations involves removing an element from a list of size up to n.

B. O(n!) because it generates all permutations internally.

C. O(n log n) due to sorting operations inside the algorithm.

D. O(n) because factorial computations and indexing are constant time per iteration.

Solution

1. Step 1: Analyze the main loop

   The algorithm runs a loop n times to select each digit of the permutation.

2. Step 2: Consider list removal cost

   Removing an element from the numbers list is O(n) in worst case, so total is O(n * n) = O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each iteration's pop is linear, leading to quadratic time [OK]

Hint: List pop at arbitrary index costs O(n), not O(1) [OK]

Common Mistakes:

• Assuming factorial computations dominate time
• Thinking it's O(n) due to fixed loop count
• Confusing factorial precomputation with sorting