1
00:00:00,770 --> 00:00:01,670
Hi everyone.

2
00:00:01,670 --> 00:00:04,910
Let's now discuss the third method to solve this question.

3
00:00:04,910 --> 00:00:08,210
Now let's say that the input string is a b, c b a.

4
00:00:08,450 --> 00:00:14,090
Now what we'll do is we'll have two pointers one at the beginning of the input string and the other

5
00:00:14,090 --> 00:00:16,580
pointer at the end of the input string.

6
00:00:16,580 --> 00:00:20,660
Now we'll check whether the characters at these two pointers are the same.

7
00:00:20,660 --> 00:00:22,490
Now in this case we have a and a.

8
00:00:22,520 --> 00:00:28,400
Now if the characters are the same or equal then we will proceed or else we can stop.

9
00:00:28,400 --> 00:00:28,610
Right?

10
00:00:28,610 --> 00:00:33,620
If the if these two are different, then definitely the input string is not a palindrome, right?

11
00:00:33,620 --> 00:00:37,580
So if they are not the same then we stop and we return false.

12
00:00:37,580 --> 00:00:40,700
Now what we do if they are, if they are the same, what do we do?

13
00:00:40,700 --> 00:00:42,110
We have the input string over here.

14
00:00:42,110 --> 00:00:43,760
We shift the pointer.

15
00:00:43,760 --> 00:00:47,180
The left pointer is shifted to the right.

16
00:00:47,180 --> 00:00:51,080
We do I plus plus and the right pointer is shifted to the left.

17
00:00:51,080 --> 00:00:52,340
We do j minus minus.

18
00:00:52,340 --> 00:00:55,190
So our pointers are at these positions now.

19
00:00:55,190 --> 00:00:57,380
And again we check whether these are the same.

20
00:00:57,380 --> 00:00:59,450
If they are not the same we return false.

21
00:00:59,450 --> 00:01:02,660
If they are the same we proceed again we move the pointers.

22
00:01:02,660 --> 00:01:07,430
Now at this point you can see that both the pointers are pointing to the same character.

23
00:01:07,430 --> 00:01:09,140
So definitely they will be the same.

24
00:01:09,140 --> 00:01:10,520
And we can stop, right?

25
00:01:10,520 --> 00:01:11,240
We can stop.

26
00:01:11,240 --> 00:01:15,050
And we found that the answer is true and we return true.

27
00:01:15,050 --> 00:01:17,720
Now there could be also another case over here.

28
00:01:17,720 --> 00:01:20,300
You can see that the length of this string is odd right?

29
00:01:20,300 --> 00:01:22,490
It's five five characters the length.

30
00:01:22,490 --> 00:01:25,850
Now let's say it was even like a b c, c b a.

31
00:01:25,970 --> 00:01:30,800
In this case what would happen now we initially have the pointers here and here.

32
00:01:30,800 --> 00:01:33,020
Then we move them to here and here.

33
00:01:33,020 --> 00:01:36,500
And afterwards we move the pointers to these two places.

34
00:01:36,500 --> 00:01:37,490
Now they are the same.

35
00:01:37,490 --> 00:01:42,470
Now in the next iteration you can see that the pointers come like this.

36
00:01:42,470 --> 00:01:42,740
Right.

37
00:01:42,740 --> 00:01:45,110
J comes over here because we move it to the left.

38
00:01:45,110 --> 00:01:47,480
And I comes here because we move I to the right.

39
00:01:47,480 --> 00:01:51,470
Now at this point you can see that J is bigger right.

40
00:01:51,470 --> 00:01:53,660
So we we need to stop.

41
00:01:53,660 --> 00:01:53,870
Right.

42
00:01:53,870 --> 00:02:01,190
So we need to continue this iteration only as long as I is less than or equal to J.

43
00:02:01,190 --> 00:02:04,370
So that's the point which I want you to take away from this.

44
00:02:04,370 --> 00:02:09,410
Or you can say that as long as I is not greater than J, both are the one and the same.

45
00:02:09,410 --> 00:02:10,010
All right.

46
00:02:10,010 --> 00:02:15,350
So in this way we can just use two pointers and we can solve this problem.

47
00:02:15,350 --> 00:02:19,250
Now let's quickly look at the complexity of this solution.

48
00:02:19,250 --> 00:02:21,560
Now what about the time complexity.

49
00:02:21,560 --> 00:02:24,710
The time complexity of this solution is O of n.

50
00:02:24,710 --> 00:02:25,340
Why is that?

51
00:02:25,340 --> 00:02:28,430
So we are just traversing the given array once, right?

52
00:02:28,430 --> 00:02:34,070
In fact, we could say that it is o of n by two because we are traversing it from both the sides right

53
00:02:34,070 --> 00:02:34,970
with I and j.

54
00:02:34,970 --> 00:02:36,890
But then one by two is a constant.

55
00:02:36,890 --> 00:02:39,320
So we can just remove that and we get that.

56
00:02:39,320 --> 00:02:42,470
The time complexity of this solution is O of n.

57
00:02:42,470 --> 00:02:44,510
Now what about the space complexity?

58
00:02:44,750 --> 00:02:46,850
That's the interesting thing of this solution.

59
00:02:46,850 --> 00:02:49,970
The space complexity of this solution is O of one.

60
00:02:49,970 --> 00:02:50,990
Why is that so?

61
00:02:50,990 --> 00:02:53,840
Because we are not using any additional space, right?

62
00:02:53,840 --> 00:02:59,720
We are just having two pointers and we are just comparing the values that are there in these two pointers.

63
00:02:59,720 --> 00:03:05,300
So it does not scale whether the input string is of length five or 5000 or 5 million.

64
00:03:05,300 --> 00:03:09,800
We are just using these two pointers and we are traversing the given string once.

65
00:03:09,800 --> 00:03:13,100
So the space complexity of this solution is O of one.

66
00:03:13,100 --> 00:03:19,310
So we have discussed these three methods for finding whether the given string is a palindrome or not.

67
00:03:19,310 --> 00:03:22,730
The first method was creating a new string and then comparing.

68
00:03:22,730 --> 00:03:28,400
And we saw that the time complexity of this solution is O of n square, and the space complexity is

69
00:03:28,400 --> 00:03:29,120
O of n.

70
00:03:29,120 --> 00:03:31,460
The second solution was better than the first.

71
00:03:31,460 --> 00:03:36,860
Instead of creating an empty new string, we created a new array and we kept pushing to the array,

72
00:03:36,860 --> 00:03:39,410
and at the end we converted that array to a string.

73
00:03:39,410 --> 00:03:40,340
And then we compared.

74
00:03:40,370 --> 00:03:47,030
Now in this case, we found that the time complexity was O of n and the space complexity was O of n.

75
00:03:47,510 --> 00:03:51,920
So compared to the first method, we improved upon the time complexity.

76
00:03:51,950 --> 00:03:57,200
Now in the third method that we discussed, we had two pointers pointing at the beginning and the end.

77
00:03:57,200 --> 00:03:59,060
And then we kept moving them right.

78
00:03:59,060 --> 00:04:04,370
We did beginning plus, plus and end minus minus or moving the beginning pointer to the right and the

79
00:04:04,370 --> 00:04:05,510
end pointer to the left.

80
00:04:05,510 --> 00:04:09,950
And we kept checking whether the characters were the same at these two pointers.

81
00:04:09,950 --> 00:04:16,340
And for this solution we saw that the time complexity is O of n and the space complexity is O of one.

82
00:04:16,340 --> 00:04:19,550
And this is the optimum solution for this question.