Let's now take a look at the space and time complexity of the approach that we have discussed to solve
the N-queens problem.
Now, the time complexity of this solution is going to be of the order of n factorial.
Now why is that so?
Let's develop an intuition for this.
Now the first row for example, we will be able to fill the first row in n ways because as of now,
nothing is filled.
So we can place a queen in any of these positions so we can fill the first row in n ways.
When it comes to the second row, let's say we had filled a queen over here.
Now notice that we can only fill a queen in approximately N minus two places, because over here we
would not be able to fill a queen.
Because this queen would attack it.
And over here also, we will not be able to fill a queen because it would attack it.
So in the second row we would be able to fill a queen in n minus two positions.
And when it comes to the third row, we would be able to fill queens in n minus four positions based
on where we fill a queen in the two above positions.
So notice over here in row one, we could do it in n ways.
In row two, we can do it in n minus two ways, and in row three it's n minus four.
So approximately or roughly you can see that the time complexity is n into n minus two etc..
So this is approximately n factorial or the upper bound can be taken as n factorial.
So that's why the time complexity of this approach is n factorial.
Now notice that it's not n to the power n.
Because of pruning.
So the time complexity is not n to the power, n because of pruning, because again, notice we are
not trying to fill queens in all the positions in all the rows, because whenever we encounter a scenario
where filling a queen over there is not valid, we prune that branch.
So that's why the time complexity is not n to the power n.
And when I say n to the power n, this n accounts for n rows, and this n accounts for the n choices
you can do in each row, which is the n columns.
So it's not n to the power of n because of pruning.
All right.
So the time complexity is of the order of n factorial.
And when it comes to the space complexity.
It's going to be off the order of N square.
Now, why is that so?
What all takes up space?
Now, as we build solutions, we will have to hold the state of a board.
And a board takes space of the order of N into n.
So this takes space of the order of n square.
And then we know that every row will have only one queen.
So if there are n rows, we will have to call the recursive function n times, or the maximum depth
of the recursion tree at any point is going to be of the order of n, so the recursive call stack will
take space of the order of n, and because n square is greater than n, we can say that the space complexity
is of the order of n square.
Also do remember in coding interview questions, if space is used just to return the output, that space
is not counted as auxiliary space and it's not counted as part of the space complexity.
So over here we may have multiple boats that we will need to return in the results array, but that
is not counted as part of the space complexity.
So the space complexity of this approach is of the order of n square.