1
00:00:00,810 --> 00:00:01,740
Hi everyone.

2
00:00:01,740 --> 00:00:07,290
So we have got a good understanding of the question and in this video let's try to think through how

3
00:00:07,290 --> 00:00:08,490
to solve this question.

4
00:00:08,490 --> 00:00:12,060
Now we have seen that there are two possibilities.

5
00:00:12,060 --> 00:00:15,930
One is that the given node is part of the doubly linked list.

6
00:00:15,930 --> 00:00:21,210
And there is another possibility where the given node is not part of the doubly linked list.

7
00:00:21,240 --> 00:00:24,150
Now there is an interesting thing that we can notice over here.

8
00:00:24,150 --> 00:00:30,720
Let's say that this is the case where the given node is part of the doubly linked list, and previously

9
00:00:30,720 --> 00:00:36,810
we have written a function where if we input a node, that function removes that node from the doubly

10
00:00:36,810 --> 00:00:37,320
linked list.

11
00:00:37,320 --> 00:00:42,270
Let's say we are passing this particular node to that function which we have written.

12
00:00:42,270 --> 00:00:43,440
Write the remove function.

13
00:00:43,440 --> 00:00:47,700
So what would be the case after we run that we call that function.

14
00:00:47,700 --> 00:00:50,490
This would be taken out of the doubly linked list.

15
00:00:50,490 --> 00:00:50,760
Right.

16
00:00:50,760 --> 00:00:55,740
So we would have this scenario over here where we have one two and four and three is removed out.

17
00:00:55,740 --> 00:00:56,160
Right.

18
00:00:56,160 --> 00:00:58,110
And then we have three separately.

19
00:00:58,110 --> 00:01:05,280
We have three taken out now when you compare this scenario and this scenario these were the two scenarios.

20
00:01:05,280 --> 00:01:08,490
One is the scenario where the given node is part of the doubly linked list.

21
00:01:08,490 --> 00:01:11,970
This is the scenario where the given node is not part of the doubly linked list.

22
00:01:11,970 --> 00:01:18,180
But in the first case, after we have called the remove function, we can see that these two scenarios

23
00:01:18,180 --> 00:01:19,800
are now one and the same.

24
00:01:19,800 --> 00:01:25,380
Right over here we can see we have a doubly linked list and we have node five which is not part of it.

25
00:01:25,380 --> 00:01:30,870
Similarly over here also we have a doubly linked list and we have node three because we have removed

26
00:01:30,870 --> 00:01:31,020
it.

27
00:01:31,020 --> 00:01:33,870
It is no longer part of the doubly linked list.

28
00:01:33,900 --> 00:01:36,060
Now it's just one and the same.

29
00:01:36,060 --> 00:01:36,240
Right.

30
00:01:36,240 --> 00:01:42,240
So we have converted both the cases into the same case by calling the remove function, which we have

31
00:01:42,240 --> 00:01:43,110
already written.

32
00:01:43,590 --> 00:01:44,010
All right.

33
00:01:44,010 --> 00:01:45,210
So this is step one.

34
00:01:45,210 --> 00:01:46,920
We will call the remove function.

35
00:01:46,920 --> 00:01:53,520
And if the node which is given to us is part of of the doubly linked list, we will take it out of the

36
00:01:53,520 --> 00:01:54,360
doubly linked list.

37
00:01:54,360 --> 00:01:59,970
Now again remember if the node which is given is not part of the doubly linked list, and if we call

38
00:01:59,970 --> 00:02:02,460
the remove function, it does not do anything right.

39
00:02:02,460 --> 00:02:09,570
It will just make sure that the node in this case node five, is pointing to null in both the directions,

40
00:02:09,570 --> 00:02:14,550
so it will not do anything, and it will ensure that in case this node was pointing somewhere else,

41
00:02:14,550 --> 00:02:18,150
we will make it point to null in both the cases, both the directions.

42
00:02:18,150 --> 00:02:19,020
So that's it.

43
00:02:19,020 --> 00:02:22,470
So step one is to call the remove function irrespective.

44
00:02:22,470 --> 00:02:26,220
So we don't know whether the given node is part of the doubly linked list or not.

45
00:02:26,220 --> 00:02:29,190
So that's the clarification that we've got from the interviewer.

46
00:02:29,190 --> 00:02:34,350
So irrespective of that like it doesn't matter whether it's part of the doubly linked list or whether

47
00:02:34,350 --> 00:02:39,420
it's not part of the doubly linked list, we will call the remove function and we will pass the given

48
00:02:39,420 --> 00:02:40,080
node to us.

49
00:02:40,080 --> 00:02:44,280
And we will ensure that if it is part of the doubly linked list, it is removed.

50
00:02:44,280 --> 00:02:45,780
So it will become like this.

51
00:02:45,780 --> 00:02:48,660
Now we are dealing with the same scenario right now.

52
00:02:48,660 --> 00:02:49,560
Let's proceed.

53
00:02:50,040 --> 00:02:55,950
So we are now at this point where we have a doubly linked list, and we are given a node which is not

54
00:02:55,950 --> 00:02:57,300
part of the doubly linked list.

55
00:02:57,300 --> 00:02:57,960
Why is that?

56
00:02:57,960 --> 00:03:01,410
So in case it's part of the doubly linked list, we have called the remove function.

57
00:03:01,410 --> 00:03:03,060
And we have removed it outside.

58
00:03:03,060 --> 00:03:05,220
So let me just write five over here.

59
00:03:05,220 --> 00:03:09,360
And it's given that we need to insert this node ahead of two.

60
00:03:09,360 --> 00:03:09,660
Right.

61
00:03:09,660 --> 00:03:11,430
So it should be inserted over here.

62
00:03:11,430 --> 00:03:13,440
Now there are two possibilities.

63
00:03:13,440 --> 00:03:15,360
Again I'm just taking a generic scenario.

64
00:03:15,360 --> 00:03:17,730
And we will look at the case where we are.

65
00:03:17,880 --> 00:03:20,670
We have to insert ahead of the head before the head.

66
00:03:20,670 --> 00:03:22,650
So those are the two cases.

67
00:03:22,650 --> 00:03:25,230
Now let's say it's not the head.

68
00:03:25,230 --> 00:03:28,440
So we have one over here and we have no two over here.

69
00:03:28,440 --> 00:03:32,700
Now this is the given node and this will be the previous node.

70
00:03:32,700 --> 00:03:34,320
So this is node dot previous.

71
00:03:34,320 --> 00:03:41,640
Right now you can see that this node over here at at the current moment is pointing to null right in

72
00:03:41,640 --> 00:03:46,020
both directions left and right or previous and next right.

73
00:03:46,020 --> 00:03:48,150
So previous and next is pointing to null.

74
00:03:48,150 --> 00:03:53,580
So what we can now do is let's make this point to these two nodes over here.

75
00:03:53,580 --> 00:03:54,030
Again.

76
00:03:54,030 --> 00:03:58,260
Remember don't think of it in terms of code like Node.prev or node.

77
00:03:58,260 --> 00:04:01,380
So I'm just I've just written it so that it becomes familiar to you to you.

78
00:04:01,380 --> 00:04:03,780
But the important thing is that you visualize this.

79
00:04:03,780 --> 00:04:04,020
Right?

80
00:04:04,020 --> 00:04:09,750
So once you're very clear with what you want your code to accomplish, it's very easy to go ahead and

81
00:04:09,750 --> 00:04:10,740
write out that code.

82
00:04:10,740 --> 00:04:15,150
So we are now going to change these two directions which were pointing to null.

83
00:04:15,150 --> 00:04:19,800
We are going to change these two and make them to point to this node and this node.

84
00:04:20,010 --> 00:04:20,580
Right.

85
00:04:20,940 --> 00:04:22,350
So we have node.

86
00:04:22,350 --> 00:04:25,020
So we make this node.

87
00:04:25,020 --> 00:04:27,300
This is the let's call node insert.

88
00:04:27,300 --> 00:04:29,100
Let me call this node insert.

89
00:04:29,100 --> 00:04:30,930
So node insert dot.

90
00:04:30,930 --> 00:04:35,670
Next will be node and node insert dot prev will be node dot prev.

91
00:04:35,670 --> 00:04:38,190
So I'm connecting these two connections right.

92
00:04:38,190 --> 00:04:43,080
So that can be done without any danger of losing anything or doing anything wrong.

93
00:04:43,080 --> 00:04:46,500
So there is nothing to be checked whether it's the head or not.

94
00:04:46,500 --> 00:04:49,110
Like let me again draw that conditionals over here.

95
00:04:49,110 --> 00:04:53,250
Now again let's say we did not have this node one over here.

96
00:04:53,250 --> 00:04:56,250
And again we want to insert node five ahead of node two.

97
00:04:56,250 --> 00:04:56,550
Right.

98
00:04:56,550 --> 00:04:58,110
So we have five again over here.

99
00:04:58,110 --> 00:05:00,390
In this case also you can see that the same.

100
00:05:00,530 --> 00:05:01,610
Thing can be done right.

101
00:05:01,820 --> 00:05:03,170
We can connect these two.

102
00:05:03,200 --> 00:05:05,180
That is again we have node over here.

103
00:05:05,180 --> 00:05:08,000
This is node and this is node dot pref.

104
00:05:10,100 --> 00:05:10,490
Right.

105
00:05:10,490 --> 00:05:16,610
So whether it's the head, whether we are inserting before the head or not, it does not matter in both

106
00:05:16,610 --> 00:05:17,990
the cases we can.

107
00:05:17,990 --> 00:05:19,520
So let me call this node insert.

108
00:05:19,520 --> 00:05:23,360
Let me just write it again so it's easier to speak about it.

109
00:05:23,360 --> 00:05:25,520
But as I speak keep visualizing it.

110
00:05:25,520 --> 00:05:26,630
That's the important thing.

111
00:05:26,630 --> 00:05:28,520
So node insert dot.

112
00:05:28,520 --> 00:05:33,950
Next is node in both the cases and node insert dot prev is node dot prev over here.

113
00:05:33,950 --> 00:05:36,350
And node.prev in this case is null right.

114
00:05:36,350 --> 00:05:39,650
So in both the cases we make these two connections.

115
00:05:39,650 --> 00:05:41,600
So that can be done straight forward.

116
00:05:42,080 --> 00:05:46,730
Now we need to see whether we are dealing with this scenario or this scenario.

117
00:05:46,730 --> 00:05:50,450
In this scenario over here we are trying to insert before the head.

118
00:05:50,450 --> 00:05:50,810
Right.

119
00:05:50,810 --> 00:05:54,980
So in that case we need to make this node over here the new head.

120
00:05:55,810 --> 00:05:56,350
All right.

121
00:05:56,350 --> 00:06:00,220
Now, if we are not inserting before the head, like for example, over here.

122
00:06:00,220 --> 00:06:04,660
So we don't need to make it the new head and we have something over here, right?

123
00:06:04,660 --> 00:06:09,820
In this case, the previous node, the node.prev gives us null.

124
00:06:09,820 --> 00:06:10,090
Right.

125
00:06:10,090 --> 00:06:12,340
But in this case node dot prev is a node.

126
00:06:12,340 --> 00:06:16,240
Because this node over here is not the head, this is not the head, right.

127
00:06:16,240 --> 00:06:21,670
So in this case, when it is not the head, when we are not inserting before the head, we can do no

128
00:06:21,670 --> 00:06:22,720
dot prev dot.

129
00:06:22,720 --> 00:06:24,520
Next that is this connection over here.

130
00:06:24,520 --> 00:06:24,910
Right?

131
00:06:24,910 --> 00:06:30,250
We can disconnect this connection and make it connect to node insert.

132
00:06:30,250 --> 00:06:31,450
So that's the next step.

133
00:06:31,450 --> 00:06:35,170
So again this the first step was to do these two connections.

134
00:06:35,170 --> 00:06:38,860
That was irrespective of whether we are inserting before the head or not.

135
00:06:38,860 --> 00:06:41,680
So this red this these red arrows.

136
00:06:41,680 --> 00:06:43,090
That was the first step.

137
00:06:43,390 --> 00:06:43,750
Right.

138
00:06:43,750 --> 00:06:46,180
So these two red arrows.

139
00:06:46,180 --> 00:06:48,460
Now the second case is the blue arrows.

140
00:06:49,090 --> 00:06:50,650
So we check whether it's the head.

141
00:06:50,680 --> 00:06:52,600
If it's the head we make this the head.

142
00:06:52,600 --> 00:06:57,700
If it's not the head we disconnect this connection and we make this connection right.

143
00:06:57,700 --> 00:06:58,570
So how do we do this.

144
00:06:58,570 --> 00:06:59,710
No dot dot.

145
00:06:59,710 --> 00:07:01,480
Next is node insert.

146
00:07:01,480 --> 00:07:04,030
So we change this connection to this one over here.

147
00:07:04,030 --> 00:07:05,740
Now what's remaining.

148
00:07:05,740 --> 00:07:08,800
You can see that over here we have a connection right.

149
00:07:08,800 --> 00:07:14,140
This connection should no longer point to null but it should point to this node over here.

150
00:07:14,140 --> 00:07:14,530
Right.

151
00:07:14,530 --> 00:07:19,510
And the same thing is also over here this this connection, which is the same connection which we have

152
00:07:19,510 --> 00:07:19,960
over here.

153
00:07:19,960 --> 00:07:24,790
So this connection or this connection should no longer point to here or here, but rather it should

154
00:07:24,790 --> 00:07:26,320
point to node insert.

155
00:07:26,320 --> 00:07:27,070
So let's do that.

156
00:07:27,070 --> 00:07:29,830
We disconnect this connection and make this connection.

157
00:07:29,830 --> 00:07:30,640
How do we do that.

158
00:07:30,640 --> 00:07:33,610
No dot prev is equal to node insert.

159
00:07:33,610 --> 00:07:35,890
The same thing is applicable over here.

160
00:07:35,890 --> 00:07:40,390
Also node dot prev is equal to node insert.

161
00:07:40,390 --> 00:07:40,870
All right.

162
00:07:40,870 --> 00:07:42,640
And we are done with our solution.

163
00:07:42,640 --> 00:07:45,100
You can see that we have null.

164
00:07:45,100 --> 00:07:48,430
Then one then five two and three four and null right.

165
00:07:48,430 --> 00:07:49,150
Which is correct.

166
00:07:49,150 --> 00:07:53,170
And in this case where we were inserting before the head we have null.

167
00:07:53,170 --> 00:07:55,600
Then we have five, two, three, four and null.

168
00:07:55,600 --> 00:07:58,180
So yes we have our solution.

169
00:07:58,210 --> 00:07:58,870
All right.

170
00:07:58,870 --> 00:08:03,520
So now let's quickly look at the complexity analysis of this solution.

171
00:08:03,520 --> 00:08:08,890
Now the time and space complexity of this solution is O of one or this solution.

172
00:08:08,890 --> 00:08:12,130
This method runs in constant time and space.

173
00:08:12,130 --> 00:08:12,820
Why is that.

174
00:08:12,820 --> 00:08:17,320
So you can see that we are not traversing the doubly linked list, right?

175
00:08:17,320 --> 00:08:21,820
The node is given to us as input and the position node is also given to us.

176
00:08:22,450 --> 00:08:28,090
So there is no need to traverse the doubly linked list, and hence this solution runs in constant time

177
00:08:28,090 --> 00:08:28,840
and space.