1
00:00:00,640 --> 00:00:07,600
Let's now take a look at the space and time complexity of the approach that we have discussed to solve

2
00:00:07,600 --> 00:00:09,130
the N-queens problem.

3
00:00:09,160 --> 00:00:16,210
Now, the time complexity of this solution is going to be of the order of n factorial.

4
00:00:16,240 --> 00:00:17,470
Now why is that so?

5
00:00:17,500 --> 00:00:19,840
Let's develop an intuition for this.

6
00:00:19,840 --> 00:00:27,490
Now the first row for example, we will be able to fill the first row in n ways because as of now,

7
00:00:27,490 --> 00:00:28,330
nothing is filled.

8
00:00:28,330 --> 00:00:34,570
So we can place a queen in any of these positions so we can fill the first row in n ways.

9
00:00:35,080 --> 00:00:39,820
When it comes to the second row, let's say we had filled a queen over here.

10
00:00:39,820 --> 00:00:47,950
Now notice that we can only fill a queen in approximately N minus two places, because over here we

11
00:00:47,950 --> 00:00:49,990
would not be able to fill a queen.

12
00:00:51,140 --> 00:00:53,060
Because this queen would attack it.

13
00:00:53,060 --> 00:00:56,990
And over here also, we will not be able to fill a queen because it would attack it.

14
00:00:56,990 --> 00:01:03,080
So in the second row we would be able to fill a queen in n minus two positions.

15
00:01:03,080 --> 00:01:10,250
And when it comes to the third row, we would be able to fill queens in n minus four positions based

16
00:01:10,250 --> 00:01:13,730
on where we fill a queen in the two above positions.

17
00:01:13,730 --> 00:01:18,020
So notice over here in row one, we could do it in n ways.

18
00:01:18,020 --> 00:01:23,780
In row two, we can do it in n minus two ways, and in row three it's n minus four.

19
00:01:23,780 --> 00:01:31,520
So approximately or roughly you can see that the time complexity is n into n minus two etc..

20
00:01:31,520 --> 00:01:37,550
So this is approximately n factorial or the upper bound can be taken as n factorial.

21
00:01:37,550 --> 00:01:42,050
So that's why the time complexity of this approach is n factorial.

22
00:01:42,050 --> 00:01:46,370
Now notice that it's not n to the power n.

23
00:01:47,220 --> 00:01:49,110
Because of pruning.

24
00:01:49,110 --> 00:01:55,650
So the time complexity is not n to the power, n because of pruning, because again, notice we are

25
00:01:55,650 --> 00:02:03,630
not trying to fill queens in all the positions in all the rows, because whenever we encounter a scenario

26
00:02:03,630 --> 00:02:08,100
where filling a queen over there is not valid, we prune that branch.

27
00:02:08,100 --> 00:02:11,790
So that's why the time complexity is not n to the power n.

28
00:02:11,790 --> 00:02:18,630
And when I say n to the power n, this n accounts for n rows, and this n accounts for the n choices

29
00:02:18,630 --> 00:02:21,600
you can do in each row, which is the n columns.

30
00:02:21,600 --> 00:02:25,560
So it's not n to the power of n because of pruning.

31
00:02:25,560 --> 00:02:26,130
All right.

32
00:02:26,130 --> 00:02:29,760
So the time complexity is of the order of n factorial.

33
00:02:29,760 --> 00:02:32,400
And when it comes to the space complexity.

34
00:02:33,330 --> 00:02:36,270
It's going to be off the order of N square.

35
00:02:36,300 --> 00:02:37,620
Now, why is that so?

36
00:02:37,650 --> 00:02:39,480
What all takes up space?

37
00:02:39,480 --> 00:02:45,090
Now, as we build solutions, we will have to hold the state of a board.

38
00:02:45,090 --> 00:02:49,050
And a board takes space of the order of N into n.

39
00:02:49,050 --> 00:02:52,410
So this takes space of the order of n square.

40
00:02:52,410 --> 00:02:57,300
And then we know that every row will have only one queen.

41
00:02:57,810 --> 00:03:05,130
So if there are n rows, we will have to call the recursive function n times, or the maximum depth

42
00:03:05,130 --> 00:03:12,000
of the recursion tree at any point is going to be of the order of n, so the recursive call stack will

43
00:03:12,000 --> 00:03:19,350
take space of the order of n, and because n square is greater than n, we can say that the space complexity

44
00:03:19,350 --> 00:03:21,450
is of the order of n square.

45
00:03:21,450 --> 00:03:30,270
Also do remember in coding interview questions, if space is used just to return the output, that space

46
00:03:30,270 --> 00:03:36,630
is not counted as auxiliary space and it's not counted as part of the space complexity.

47
00:03:36,630 --> 00:03:43,170
So over here we may have multiple boats that we will need to return in the results array, but that

48
00:03:43,170 --> 00:03:46,470
is not counted as part of the space complexity.

49
00:03:46,470 --> 00:03:51,270
So the space complexity of this approach is of the order of n square.