N Queens Problem in DSA Typescript - Time & Space Complexity

Time Complexity: N Queens Problem

O(n!)

Understanding Time Complexity

We want to understand how the time needed to solve the N Queens problem grows as the board size increases.

Specifically, how does the number of steps change when we try to place queens on larger boards?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function solveNQueens(board: number[][], row: number, n: number): boolean {
  if (row === n) return true;
  for (let col = 0; col < n; col++) {
    if (isSafe(board, row, col, n)) {
      board[row][col] = 1;
      if (solveNQueens(board, row + 1, n)) return true;
      board[row][col] = 0;
    }
  }
  return false;
}

This code tries to place queens row by row, checking if each position is safe, and uses backtracking to find a solution.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop tries all columns in a row, and the recursive call tries to place queens in the next row.
• How many times: For each row, it tries up to n columns, and this repeats recursively for n rows, exploring many board states.

How Execution Grows With Input

As the board size n grows, the number of ways to place queens grows very fast because each row tries many columns and backtracks often.

Input Size (n)	Approx. Operations
4	Hundreds of checks
8	Thousands to tens of thousands of checks
12	Millions of checks

Pattern observation: The operations grow faster than just multiplying by n; it grows roughly like n factorial because of the many possible queen placements.

Final Time Complexity

Time Complexity: O(n!)

This means the time needed grows very fast, roughly like the number of ways to arrange queens on the board, making it hard for large n.

Common Mistake

[X] Wrong: "The algorithm only checks n positions per row, so it should be O(n^2)."

[OK] Correct: Because it tries many combinations recursively, the total checks multiply across rows, leading to factorial growth, not just squared.

Interview Connect

Understanding this problem's time complexity helps you explain why backtracking can be expensive and when to expect slow solutions, a useful skill in interviews.

Self-Check

"What if we added pruning to stop early when conflicts are detected? How would the time complexity change?"