1
00:00:01,000 --> 00:00:08,320
Let's first discuss why the previous approach, the approach that we have discussed for solving the

2
00:00:08,320 --> 00:00:14,770
permutations question will not work over here, or why we need to make a few changes to that approach.

3
00:00:14,770 --> 00:00:19,660
So let's say the array which is given to us is one, one, two.

4
00:00:19,660 --> 00:00:24,250
And as in the previous approach we would have two pointers.

5
00:00:24,250 --> 00:00:27,130
So let's say initially I is equal to zero.

6
00:00:27,130 --> 00:00:32,110
So when I is equal to zero j will take the values from 0 to 2.

7
00:00:32,110 --> 00:00:35,770
So initially I is equal to zero and j is equal to zero.

8
00:00:35,770 --> 00:00:40,960
Now if we swap the elements at zero and zero we will again get 112.

9
00:00:40,990 --> 00:00:43,360
Then j is going to take the value one.

10
00:00:43,360 --> 00:00:47,950
So we're going to swap the elements at zero and one indexes zero and one.

11
00:00:47,950 --> 00:00:55,330
So at this point the array becomes again 112 because we just swapped these two elements again.

12
00:00:55,330 --> 00:00:55,660
Right.

13
00:00:55,660 --> 00:00:56,950
And this is also a one.

14
00:00:56,950 --> 00:00:58,240
And this is also a one.

15
00:00:58,240 --> 00:01:00,400
So again we are getting 112.

16
00:01:00,400 --> 00:01:04,900
And then J is going to take the value two which is the next branch.

17
00:01:04,900 --> 00:01:11,080
And over here we're going to swap the elements at index zero and two which are these two elements.

18
00:01:11,080 --> 00:01:15,820
And when we do the swap the array looks like this which is 211.

19
00:01:15,820 --> 00:01:22,420
Now notice over here the problem with this approach is that whatever we get from this branch and this

20
00:01:22,420 --> 00:01:25,090
branch is going to be the same, right?

21
00:01:25,090 --> 00:01:28,870
It's going to be duplicates because these two are one and the same.

22
00:01:28,870 --> 00:01:30,460
So it's repeating over here.

23
00:01:30,460 --> 00:01:37,120
And this is why the previous approach will not work as it is for this question.

24
00:01:37,120 --> 00:01:41,320
And we need to make slight changes to avoid this branch over here.

25
00:01:41,320 --> 00:01:43,480
So let's take a look at how we can do that.

26
00:01:43,480 --> 00:01:48,790
So we need to avoid this branch because whatever comes over here is going to be a duplicate of what

27
00:01:48,790 --> 00:01:49,390
is over here.

28
00:01:49,390 --> 00:01:57,280
So to avoid this the approach that we can take is for this level over here where we have the value of

29
00:01:57,280 --> 00:02:01,600
I as zero, we will create a hash table or a dictionary.

30
00:02:01,600 --> 00:02:10,990
And initially when j takes the value zero, we will insert the value at index zero into this dictionary

31
00:02:10,990 --> 00:02:12,160
or hash table.

32
00:02:12,160 --> 00:02:14,980
So we will add one to this hash table.

33
00:02:14,980 --> 00:02:20,830
And then when we come over here j has the value one.

34
00:02:20,830 --> 00:02:25,810
So the value in the numb's array at index one is one.

35
00:02:25,810 --> 00:02:31,870
And because one is already there in the hash table or the dictionary because that's what we did over

36
00:02:31,870 --> 00:02:32,110
here.

37
00:02:32,110 --> 00:02:32,380
Right.

38
00:02:32,380 --> 00:02:38,230
So the hash table already has a value of one therefore because over here, because it's a repetition

39
00:02:38,230 --> 00:02:42,460
of the value, we will not go deeper in this branch.

40
00:02:42,460 --> 00:02:49,750
So if one is in the hash table we prune this branch and we go to the next branch and we proceed with

41
00:02:49,750 --> 00:02:51,520
j is equal to two.

42
00:02:51,550 --> 00:02:55,570
So this is how we can avoid this problem and solve this question.

43
00:02:55,570 --> 00:02:58,600
So let's walk through the code and see what happens.

44
00:02:58,600 --> 00:03:05,350
So at this point when j is equal to one we see that this value which is one is already there in the

45
00:03:05,350 --> 00:03:06,910
dictionary or the hash table.

46
00:03:06,910 --> 00:03:09,550
And therefore this branch is pruned.

47
00:03:09,550 --> 00:03:17,590
And we come to this branch over here where j is two and we get 211 by swapping the values at index zero

48
00:03:17,590 --> 00:03:18,280
and two.

49
00:03:18,310 --> 00:03:20,590
Now let's proceed over here.

50
00:03:21,070 --> 00:03:23,710
When I is equal to zero j is equal to zero.

51
00:03:23,710 --> 00:03:24,850
We swap the elements.

52
00:03:24,850 --> 00:03:30,520
We get one, one, two, and then we recursively call the same function the helper function again.

53
00:03:30,520 --> 00:03:33,790
And at this point I is going to be equal to one.

54
00:03:33,790 --> 00:03:38,200
And when I is equal to one, j will take the values from 1 to 2.

55
00:03:38,230 --> 00:03:42,280
So again over here we have 012.

56
00:03:42,280 --> 00:03:45,400
Now initially I is equal to one j is equal to one.

57
00:03:45,400 --> 00:03:50,560
So we are just swapping the element at index one with the element at index one.

58
00:03:50,560 --> 00:03:53,500
So we get 112 itself.

59
00:03:53,500 --> 00:03:56,320
And then I is going to be equal to one.

60
00:03:56,320 --> 00:03:58,150
And j is going to be equal to two.

61
00:03:58,180 --> 00:04:00,340
So these two elements will be swapped.

62
00:04:00,340 --> 00:04:02,620
And we get 121.

63
00:04:02,770 --> 00:04:05,260
Now let's see what happens over here.

64
00:04:05,260 --> 00:04:06,790
This branch anyway was pruned.

65
00:04:06,790 --> 00:04:12,220
So in this branch when we get 211 we'll recursively call the helper function.

66
00:04:12,220 --> 00:04:15,250
Again we will pass I is equal to one.

67
00:04:15,250 --> 00:04:19,330
And when I is equal to one j will take the values from 1 to 2.

68
00:04:19,330 --> 00:04:22,540
So initially I is equal to one j is equal to one.

69
00:04:22,540 --> 00:04:24,460
So this over here does not change.

70
00:04:24,460 --> 00:04:26,710
We get 211 itself.

71
00:04:26,710 --> 00:04:33,340
But when it comes to the next branch over here and I is equal to one, j is equal to two.

72
00:04:33,370 --> 00:04:40,600
Notice that when j is equal to one, the value one would have been added in the dictionary or the hash

73
00:04:40,600 --> 00:04:43,810
table for this particular instance.

74
00:04:43,810 --> 00:04:44,260
Right.

75
00:04:44,260 --> 00:04:46,030
For this particular instance.

76
00:04:46,030 --> 00:04:53,620
Now in this instance, the hash table over here when j is equal to one, would have added this value

77
00:04:53,620 --> 00:04:55,240
over here one to it.

78
00:04:55,240 --> 00:05:00,400
And when j is equal to two it will see that this value over here which is one.

79
00:05:00,700 --> 00:05:02,920
Is already there in the hash table.

80
00:05:02,920 --> 00:05:07,450
So we will not proceed in this branch and this would be pruned.

81
00:05:07,480 --> 00:05:13,930
Now it's necessary to do that because if you don't do that we would again get 211 over here, which

82
00:05:13,930 --> 00:05:15,010
is a repetition.

83
00:05:15,010 --> 00:05:16,660
And we don't want repetitions.

84
00:05:16,660 --> 00:05:19,060
We only want unique permutations.

85
00:05:19,060 --> 00:05:23,920
So this again is going to be pruned through the same methodology that we have discussed.

86
00:05:23,920 --> 00:05:29,020
And finally over here this will recursively call the same helper function again.

87
00:05:29,020 --> 00:05:31,030
And I would be equal to two.

88
00:05:31,030 --> 00:05:33,610
And at that point we would have hit the base case.

89
00:05:33,610 --> 00:05:38,380
And this instance of the Nums array will be added to the results array.

90
00:05:38,380 --> 00:05:42,670
Similarly this also gets added and this also gets added.

91
00:05:42,670 --> 00:05:46,000
So you can see we were able to eliminate duplicates.

92
00:05:46,000 --> 00:05:53,200
And we are getting the three unique permutations which are available for this particular input array.