1
00:00:00,110 --> 00:00:01,220
Welcome back.

2
00:00:01,520 --> 00:00:09,650
Notice that when the input array had three distinct elements, there were six permutations that we needed

3
00:00:09,650 --> 00:00:10,760
to identify.

4
00:00:10,790 --> 00:00:18,860
Now why is this number six or how can we identify this without writing out all the possible permutations?

5
00:00:18,890 --> 00:00:24,860
Now, this probably is not required for solving this question, but it's a good thing to know.

6
00:00:24,860 --> 00:00:27,290
So over here we have three elements.

7
00:00:27,290 --> 00:00:31,880
And notice that in each of these permutations we have three elements.

8
00:00:31,880 --> 00:00:36,440
For example over here also we have three elements over here also we have three elements.

9
00:00:36,440 --> 00:00:38,750
So there are three positions.

10
00:00:39,610 --> 00:00:47,200
And it's just about the different ways in which I can fill these positions with these three numbers,

11
00:00:47,200 --> 00:00:48,580
because this is the input.

12
00:00:48,580 --> 00:00:53,470
So the first position over here can be filled in three different ways.

13
00:00:53,470 --> 00:00:57,610
Notice over here I have one, I have two and I have three.

14
00:00:57,610 --> 00:01:04,270
So again if you take a look at all these six permutations, there are only these three ways of filling

15
00:01:04,270 --> 00:01:05,500
the first position.

16
00:01:05,500 --> 00:01:12,820
Now once I have filled the first position, I would be left with only two elements because I would have

17
00:01:12,820 --> 00:01:20,890
used one of the three elements to fill and put it over here so the next position can be filled in two

18
00:01:20,890 --> 00:01:21,550
ways.

19
00:01:23,090 --> 00:01:27,710
Now again, notice over here, let's say I filled the first position with one.

20
00:01:27,710 --> 00:01:30,410
Now that's these two cases over here.

21
00:01:30,410 --> 00:01:37,310
Now in these two cases, I have only two ways of filling the second position.

22
00:01:37,310 --> 00:01:43,130
So that's why once I'm done with filling the first position with one value, I can only fill the next

23
00:01:43,130 --> 00:01:45,020
position in two ways.

24
00:01:45,020 --> 00:01:52,250
And then once I've used two elements to place them over here and here, I'm just left with one way.

25
00:01:52,250 --> 00:01:56,990
So that's why I will be able to fill this place only in one way.

26
00:01:56,990 --> 00:02:03,170
So notice over here, once I filled one over here and two over here, there's just one way of filling

27
00:02:03,170 --> 00:02:05,330
the last position, which is with three.

28
00:02:05,330 --> 00:02:07,850
So that's why I can do this only in one way.

29
00:02:07,850 --> 00:02:15,560
Therefore, the total number of ways in which I can fill these three positions with these three unique

30
00:02:15,560 --> 00:02:20,000
values is this three into two into one.

31
00:02:20,480 --> 00:02:24,290
So that's three into two into one, which gives me the answer as six.

32
00:02:24,290 --> 00:02:30,680
And that's why we have six distinct permutations over here when we have three elements.

33
00:02:31,820 --> 00:02:38,810
Now also notice that this six over here is nothing but three factorial, because again, we know that

34
00:02:38,810 --> 00:02:41,990
three factorial is three into two into one.

35
00:02:42,110 --> 00:02:48,650
Now that we have learned to identify the number of distinct permutations that are expected, what would

36
00:02:48,650 --> 00:02:51,080
be the case if we have four elements?

37
00:02:51,080 --> 00:02:54,170
Let's say the input is one, two, three, four.

38
00:02:54,200 --> 00:03:00,530
In that case we would have four factorial permutations or 24 permutations.

39
00:03:00,560 --> 00:03:01,130
All right.

40
00:03:01,130 --> 00:03:05,300
So we have understood how to identify the number of permutations.

41
00:03:05,300 --> 00:03:07,280
And this is a good to know thing.

42
00:03:07,280 --> 00:03:11,810
Now let's proceed and try to think about how to solve this question.

43
00:03:12,410 --> 00:03:16,490
So let's say the input which is given to us is one two, three.

44
00:03:16,490 --> 00:03:20,900
And we need to identify all the permutations of this array.

45
00:03:20,900 --> 00:03:25,190
If I were to write the indices that's zero one and two.

46
00:03:25,220 --> 00:03:31,910
Now the approach that we can take is notice that if I just swap elements among themselves, like for

47
00:03:31,910 --> 00:03:38,810
example, if I swap three and one, I can get three, two, one, which is one of the permutations.

48
00:03:38,810 --> 00:03:46,730
Or if I can just swap two and three, I'll get one, three, two, which is again another valid permutation.

49
00:03:46,730 --> 00:03:53,090
Or if I swap two and one I would get two, one three, which is again another valid permutation.

50
00:03:53,090 --> 00:04:00,950
So I just need a systematic way of swapping elements among themselves so that I can identify all the

51
00:04:00,950 --> 00:04:02,330
possible permutations.

52
00:04:02,330 --> 00:04:05,060
So this is the approach that we will discuss over here.

53
00:04:05,060 --> 00:04:10,790
And once I have identified a valid permutation let me add it to an array.

54
00:04:11,300 --> 00:04:14,060
Let's say we can call that array permutations.

55
00:04:14,060 --> 00:04:20,210
And then finally, once we are done identifying all the permutations we will just return this array.

56
00:04:20,210 --> 00:04:22,520
So this is the approach that we are going to take.

57
00:04:22,520 --> 00:04:30,080
So to identify all the permutations I need a systematic way of swapping elements among themselves.

58
00:04:30,080 --> 00:04:32,690
And let me take two pointers for this.

59
00:04:32,690 --> 00:04:34,430
So that's I and J.

60
00:04:35,060 --> 00:04:42,290
Now J again will help me to swap the element at I with the element at j.

61
00:04:42,530 --> 00:04:51,200
And for each value of I, j is going to start from the value of I till the last index, which is two

62
00:04:51,230 --> 00:04:52,040
in this case.

63
00:04:52,040 --> 00:04:55,430
So to start with we'll say that I is equal to zero.

64
00:04:55,430 --> 00:05:02,150
And j is going to take the values from I, that is from zero till the last index which is index two.

65
00:05:02,180 --> 00:05:07,970
So I'm going to swap zero and zero zero and one and zero and two.

66
00:05:08,030 --> 00:05:14,570
If I swap the element at zero with the element at zero itself, that's swapping one with one itself.

67
00:05:14,570 --> 00:05:17,810
So over here I'll have 123 itself.

68
00:05:19,990 --> 00:05:20,800
Next.

69
00:05:20,800 --> 00:05:27,310
If I swap the element at index zero with the element at index one, then I would have swapped these

70
00:05:27,310 --> 00:05:28,090
two elements.

71
00:05:28,090 --> 00:05:30,940
So I will get two, one, three.

72
00:05:30,940 --> 00:05:38,410
And finally, if I swap the element at index zero with the element at index two, I will get 321.

73
00:05:38,950 --> 00:05:43,570
Now again, this is not the way that the algorithm would go.

74
00:05:43,570 --> 00:05:46,480
It would go deeper and then only it will go to the next branch.

75
00:05:46,480 --> 00:05:51,850
But over here, I'm writing it down for our understanding, and at a later point we will once again

76
00:05:51,850 --> 00:05:54,850
quickly trace how the algorithm would actually work.

77
00:05:54,850 --> 00:06:01,780
So once we have done swapping zero with zero, we will increment the value of I and call the same function

78
00:06:01,780 --> 00:06:02,980
recursively again.

79
00:06:02,980 --> 00:06:09,970
So I is going to be equal to one and j in that case is going to start at the value of I which is one,

80
00:06:09,970 --> 00:06:13,240
and it will go till the last index which is two.

81
00:06:13,270 --> 00:06:19,720
So there are going to be two cases one where J is one, and the second case where j is two.

82
00:06:19,720 --> 00:06:26,380
So for the case where I is equal to one, I am going to swap one and one and one and two.

83
00:06:26,380 --> 00:06:29,590
And this is going to happen in each of these branches.

84
00:06:31,090 --> 00:06:37,540
So for this branch where the instance of numb's at this point looks like this.

85
00:06:37,540 --> 00:06:41,110
When I swap one and one, I will again get one, two, three.

86
00:06:41,110 --> 00:06:46,810
And when I swap one and two, these two elements are going to be swapped, because this is index one

87
00:06:46,810 --> 00:06:48,070
and this is index two.

88
00:06:48,070 --> 00:06:50,260
So I will get 132.

89
00:06:51,250 --> 00:06:51,760
All right.

90
00:06:51,760 --> 00:06:54,940
And in a similar manner over here I'll get again two, one three.

91
00:06:54,940 --> 00:06:59,020
And then I'll get two, three, one over here when I swap these two values.

92
00:06:59,020 --> 00:07:01,390
And over here I'll get three, two, one.

93
00:07:01,390 --> 00:07:04,030
And I will get 312.

94
00:07:04,360 --> 00:07:10,300
Now once this is done this part over here will again recursively call the same function incrementing

95
00:07:10,300 --> 00:07:10,630
I.

96
00:07:10,660 --> 00:07:13,180
So I at that point will become two.

97
00:07:13,750 --> 00:07:21,070
And when I is equal to two, I will hit the base case because j can can take nothing more, right?

98
00:07:21,070 --> 00:07:25,330
J can just take the value two and there is no point in just swapping two with two.

99
00:07:25,330 --> 00:07:33,220
So at this point I would have hit the base case and I will take a copy of this and add it to the permutations

100
00:07:33,220 --> 00:07:33,610
array.

101
00:07:35,020 --> 00:07:40,780
So over here, the same thing will happen in this case as well, because when I get one, three, two

102
00:07:40,780 --> 00:07:44,830
and recursively call the same function again, I would be equal to two.

103
00:07:44,860 --> 00:07:47,410
Therefore, I make a copy of it and put it over here.

104
00:07:47,410 --> 00:07:51,610
And in a similar manner I'll make a copy of this and this as well.

105
00:07:53,340 --> 00:07:59,850
And notice over here, when I'm done with this, I would have added all the permutations, all the valid

106
00:07:59,850 --> 00:08:04,470
unique permutations to this array over here, and I can just return it.

107
00:08:04,470 --> 00:08:08,160
So this is the approach that we will take to solve this question.

108
00:08:08,160 --> 00:08:15,450
Notice that we are solving the question in place or changes to the state of the problem are made in

109
00:08:15,450 --> 00:08:19,500
place, or all of these are actually the same array we have over here.

110
00:08:19,500 --> 00:08:23,850
This and this, for example, are not two different arrays.

111
00:08:23,850 --> 00:08:31,890
It's the same array, but we are just swapping it and making copies to get all the possible permutations.