1
00:00:00,710 --> 00:00:01,640
Hi everyone.

2
00:00:01,640 --> 00:00:05,690
In this video, let's think together how we can solve this question.

3
00:00:05,690 --> 00:00:09,680
Now let's say that the given singly linked list is this one over here.

4
00:00:09,680 --> 00:00:14,870
Now, as mentioned in the question, the input to the function is going to be the head of the singly

5
00:00:14,870 --> 00:00:15,380
linked list.

6
00:00:15,380 --> 00:00:15,770
Right.

7
00:00:15,770 --> 00:00:17,630
So that's this node over here.

8
00:00:17,630 --> 00:00:25,070
Now let's define a variable cur and let's point it to the head of the singly linked list.

9
00:00:25,070 --> 00:00:28,520
Now we will look at the remaining part of the singly linked list.

10
00:00:28,520 --> 00:00:32,060
And let's find the next distinct node.

11
00:00:32,420 --> 00:00:32,840
All right.

12
00:00:32,840 --> 00:00:36,620
So in this case the next node itself is different right.

13
00:00:36,620 --> 00:00:41,180
So distinct means the next node which is different from the current node.

14
00:00:41,180 --> 00:00:44,000
Now remember to remove all the duplicates.

15
00:00:44,000 --> 00:00:48,230
We are trying to remove all the duplicates together as the input is sorted.

16
00:00:48,230 --> 00:00:49,730
Now what do I mean with that?

17
00:00:49,730 --> 00:00:51,500
Let's say we are over here.

18
00:00:51,500 --> 00:00:57,020
Let's say current is over here at some point now we can or we could remove one at a time.

19
00:00:57,020 --> 00:01:00,440
Like when we look at the next node we see we see that it's not distinct.

20
00:01:00,440 --> 00:01:01,790
So we could remove that.

21
00:01:01,790 --> 00:01:04,940
Then again we look at the next one and we could remove that.

22
00:01:04,940 --> 00:01:05,780
We can do that.

23
00:01:05,780 --> 00:01:07,310
We can do it in that way also.

24
00:01:07,310 --> 00:01:13,670
But over here, as the singly linked list over here is sorted, now we can remove all the duplicates

25
00:01:13,670 --> 00:01:14,120
together.

26
00:01:14,120 --> 00:01:20,990
For example, if the input was one pointing to one pointing to one, and that's pointing to, let's

27
00:01:20,990 --> 00:01:24,170
say three, and let's say that points to null.

28
00:01:24,170 --> 00:01:30,530
In this case we could remove one at a time like we current current is pointing over here at the beginning.

29
00:01:30,530 --> 00:01:35,870
Then the next node of uh after this one is a duplicate.

30
00:01:35,870 --> 00:01:36,920
So we could remove it.

31
00:01:36,920 --> 00:01:39,800
Then we again check the next one which is a duplicate.

32
00:01:39,800 --> 00:01:41,810
We remove it and we go on like that.

33
00:01:41,810 --> 00:01:42,920
So that's possible.

34
00:01:42,920 --> 00:01:47,660
But in this approach let's try to find the next distinct node.

35
00:01:47,660 --> 00:01:52,310
So we would go ahead and find that the next distinct node is three in this case.

36
00:01:52,310 --> 00:01:54,740
And then we will remove everything in between together.

37
00:01:54,740 --> 00:01:59,270
So that's how we will approach this because the given singly linked list is sorted.

38
00:01:59,270 --> 00:01:59,540
Right.

39
00:01:59,540 --> 00:02:04,760
So there is no possibility that you'll have one over here, then three over here and then two and then

40
00:02:04,760 --> 00:02:05,840
somewhere over here one.

41
00:02:05,840 --> 00:02:09,470
So this is not possible because it's mentioned that it's sorted.

42
00:02:09,470 --> 00:02:10,070
All right.

43
00:02:10,070 --> 00:02:16,310
So the current variable is pointing to the node where the value is one or the it's the head right.

44
00:02:16,310 --> 00:02:23,300
And after this let's define another variable next distinct and let it point to the next node.

45
00:02:23,980 --> 00:02:27,010
Now we will check whether these two are the same.

46
00:02:27,010 --> 00:02:29,020
Now in this case, these two are the same.

47
00:02:29,020 --> 00:02:30,460
So there's nothing to be.

48
00:02:30,460 --> 00:02:32,710
They are not the same, so there's nothing to be removed.

49
00:02:32,710 --> 00:02:36,070
Therefore, we shift current to the next place.

50
00:02:36,070 --> 00:02:41,560
And when we shift current along with that, in the next step we will also shift next distinct.

51
00:02:41,560 --> 00:02:42,520
So let's do that.

52
00:02:42,520 --> 00:02:48,700
So current shifts over here and over along with that next distinct is the next one after current.

53
00:02:48,700 --> 00:02:51,790
Now in this case we see that these two are the same right.

54
00:02:51,790 --> 00:02:57,130
So instead of removing this at this point we move next distinct one more time.

55
00:02:57,130 --> 00:02:58,690
So we move this one more time.

56
00:02:58,690 --> 00:02:59,860
So it comes over here.

57
00:02:59,860 --> 00:03:02,800
Now we see that these two are not the same right.

58
00:03:02,800 --> 00:03:06,370
So we can remove just whatever comes in between them.

59
00:03:06,370 --> 00:03:11,410
That means we will make this node over here point to this one over here.

60
00:03:11,410 --> 00:03:13,630
So we will make it point to three.

61
00:03:13,630 --> 00:03:17,410
This node will point to three and this connection will be disconnected.

62
00:03:17,680 --> 00:03:18,100
All right.

63
00:03:18,100 --> 00:03:22,360
And for this we will do cur dot next is equal to next distinct right.

64
00:03:22,360 --> 00:03:27,610
So using this operation over here we will make this node point to this one.

65
00:03:27,610 --> 00:03:31,390
And in that way we have removed effectively this node is removed.

66
00:03:31,390 --> 00:03:31,990
All right.

67
00:03:32,020 --> 00:03:35,770
Now once this is done we will again move current to the next node.

68
00:03:35,770 --> 00:03:38,200
And at this point the next node is this one.

69
00:03:38,200 --> 00:03:38,500
Right.

70
00:03:38,500 --> 00:03:41,170
Because this connection over here is severed or it's removed.

71
00:03:41,170 --> 00:03:43,960
So we move current to this place.

72
00:03:43,960 --> 00:03:46,600
And next distinct is the next node.

73
00:03:46,600 --> 00:03:47,080
Right.

74
00:03:47,080 --> 00:03:49,180
And we check whether these two are the same.

75
00:03:49,180 --> 00:03:50,950
Now in this case they are not the same.

76
00:03:50,950 --> 00:03:52,810
So there's nothing to be removed right.

77
00:03:52,810 --> 00:03:59,560
So let me just write the singly linked list one more time below so that it does not get crowded.

78
00:03:59,560 --> 00:03:59,920
Right.

79
00:03:59,920 --> 00:04:01,960
So we have reached till here.

80
00:04:01,960 --> 00:04:03,970
The pointer is at this point over here.

81
00:04:03,970 --> 00:04:08,590
And we've seen that these two that is current and next distinct are different.

82
00:04:08,590 --> 00:04:10,390
So again we move current.

83
00:04:10,390 --> 00:04:12,160
We move current from here to here.

84
00:04:12,160 --> 00:04:12,400
Right.

85
00:04:12,400 --> 00:04:13,540
So current is over here.

86
00:04:13,540 --> 00:04:16,780
And next distinct is the next node which is over here.

87
00:04:16,780 --> 00:04:17,950
Now we compare them.

88
00:04:17,950 --> 00:04:20,740
And at this point we see that they are the same.

89
00:04:20,740 --> 00:04:23,590
So we again move next distinct.

90
00:04:23,590 --> 00:04:25,180
So again it comes over here.

91
00:04:25,180 --> 00:04:27,010
And again we compare these two.

92
00:04:27,040 --> 00:04:28,120
Again they are the same.

93
00:04:28,120 --> 00:04:30,880
Therefore we move next distinct again.

94
00:04:30,880 --> 00:04:32,620
So it comes over here right.

95
00:04:32,620 --> 00:04:35,410
At this point these two are not the same right.

96
00:04:35,410 --> 00:04:37,270
Four and null are not the same.

97
00:04:37,270 --> 00:04:40,480
Therefore we remove everything which is in between.

98
00:04:40,480 --> 00:04:45,400
That means we make this node over here point to next distinct.

99
00:04:45,400 --> 00:04:49,690
So four will point to null and this connection is removed right.

100
00:04:49,690 --> 00:04:54,040
So after this we again move current and current comes to null right.

101
00:04:54,040 --> 00:05:00,280
So when we see that current comes to null in the next iteration, we get the condition to stop the loop.

102
00:05:00,280 --> 00:05:01,750
So we come out of the loop.

103
00:05:01,750 --> 00:05:05,050
And at this point we have removed all the duplicates.

104
00:05:05,050 --> 00:05:05,260
Right.

105
00:05:05,260 --> 00:05:09,040
We have removed this one over here, and we have removed these two over here.

106
00:05:09,040 --> 00:05:13,330
So we have one pointing to two pointing to three pointing to four.

107
00:05:13,330 --> 00:05:14,950
And that points to null.

108
00:05:14,950 --> 00:05:17,140
So there we have our solution.

109
00:05:17,530 --> 00:05:22,210
So what we are doing over here, the interesting part is that we have a pointer.

110
00:05:22,210 --> 00:05:24,100
And then we keep moving.

111
00:05:24,100 --> 00:05:27,850
The next distinct pointer till we get a distinct value.

112
00:05:27,850 --> 00:05:33,640
And if we have let's say two nodes in between over here we have seen that over here.

113
00:05:33,640 --> 00:05:33,910
Right.

114
00:05:33,910 --> 00:05:34,960
We had current over here.

115
00:05:34,960 --> 00:05:36,190
And then we had two nodes.

116
00:05:36,190 --> 00:05:38,380
And after that only we got the next distinct.

117
00:05:38,380 --> 00:05:43,240
So once we find the next distinct we just connect current and next distinct.

118
00:05:43,240 --> 00:05:45,430
And we remove everything which is in between.

119
00:05:45,430 --> 00:05:45,610
Right.

120
00:05:45,610 --> 00:05:50,650
Because this connection is removed and we make this node point to the next distinct node.

121
00:05:50,650 --> 00:05:52,900
So that's how we solve this question.

122
00:05:52,900 --> 00:05:57,670
And the output would be one pointing to two pointing to three pointing to four.

123
00:05:57,670 --> 00:05:59,230
And that points to null.

124
00:05:59,230 --> 00:06:02,860
Now let's quickly look at the complexity of this solution.

125
00:06:02,860 --> 00:06:06,190
The time complexity of this solution is O of n.

126
00:06:06,190 --> 00:06:07,180
Why is that so?

127
00:06:07,180 --> 00:06:10,960
Because we are traversing the singly linked list once right.

128
00:06:10,960 --> 00:06:15,550
So we have we we have seen that initially current was pointing to the head.

129
00:06:15,550 --> 00:06:19,480
And then we kept on moving it right till it reaches over here.

130
00:06:19,480 --> 00:06:21,790
Finally current would be pointing to null.

131
00:06:21,790 --> 00:06:24,370
And it's at that time that we come out of the loop.

132
00:06:24,370 --> 00:06:27,520
So we are traversing the singly linked list once.

133
00:06:27,520 --> 00:06:31,210
Therefore, the time complexity of this solution is O of n.

134
00:06:31,210 --> 00:06:33,550
Now what about the space complexity?

135
00:06:33,550 --> 00:06:40,330
The space complexity of this solution is O of one, or this algorithm runs in constant space because

136
00:06:40,330 --> 00:06:42,490
we are not using any additional space, right?

137
00:06:42,490 --> 00:06:45,400
We are just using pointers and we are just moving the pointers.

138
00:06:45,400 --> 00:06:48,160
So there is no scaling space which we are using.

139
00:06:48,160 --> 00:06:48,670
Right?

140
00:06:48,670 --> 00:06:51,430
And again these nodes are already there in memory.

141
00:06:51,430 --> 00:06:54,550
We are just having pointers to the existing nodes in memory.

142
00:06:54,550 --> 00:06:57,010
So there is no additional space used.

143
00:06:57,010 --> 00:07:01,120
Therefore the space complexity of this solution is O of one.