1
00:00:00,760 --> 00:00:07,300
In the previous video, we saw how we could solve this problem with the time complexity of O of n log

2
00:00:07,300 --> 00:00:10,000
n and space complexity of O of n.

3
00:00:10,000 --> 00:00:14,680
Now anyway, we have to form a new array, so we cannot improve on the space complexity.

4
00:00:14,680 --> 00:00:20,500
But let's try to improve the time complexity, which is o of n log n as per the brute force method.

5
00:00:20,500 --> 00:00:26,410
Now notice that in the previous method, we did not use the fact that the input array was sorted.

6
00:00:26,410 --> 00:00:26,800
Right.

7
00:00:26,800 --> 00:00:31,900
Now let's try to make use of that fact and improve the time complexity.

8
00:00:31,900 --> 00:00:32,320
All right.

9
00:00:32,320 --> 00:00:37,900
So we're going to try to use the fact that the given array is sorted in ascending order.

10
00:00:37,900 --> 00:00:40,090
So let's look at it now.

11
00:00:40,090 --> 00:00:44,290
Now again we have an example minus three one two and seven.

12
00:00:44,290 --> 00:00:50,620
Now first let's make a new array and initialize uh, all of the indices of the new array to zero.

13
00:00:50,620 --> 00:00:55,270
And let the length of the new array be the same as the length of the initially given array.

14
00:00:55,270 --> 00:00:55,810
All right.

15
00:00:55,810 --> 00:00:57,340
So we have done that now.

16
00:00:57,970 --> 00:01:01,270
Now let's look at a property of numbers.

17
00:01:01,270 --> 00:01:03,190
Over here we have the number line.

18
00:01:03,190 --> 00:01:10,900
And notice that as you go towards the left and the right from zero the value of squares keeps increasing

19
00:01:10,900 --> 00:01:11,260
right.

20
00:01:11,260 --> 00:01:16,870
For example let's say that you have one over here, you have two over here and you have ten over here.

21
00:01:16,870 --> 00:01:22,480
So as we go from zero towards the right, the square is one 400, etc..

22
00:01:22,480 --> 00:01:26,830
So it's increasing and the same is observed when you go towards the left also.

23
00:01:26,830 --> 00:01:27,130
Right.

24
00:01:27,130 --> 00:01:28,390
So you have minus one.

25
00:01:28,390 --> 00:01:31,690
Let's say you have minus three and let's say you have minus nine.

26
00:01:31,690 --> 00:01:36,610
So as you see as you go to the extremes the square value increases.

27
00:01:36,610 --> 00:01:37,000
Right.

28
00:01:37,000 --> 00:01:43,300
So the same has to be true when we look at the sorted array which is given to us right now, we are

29
00:01:43,300 --> 00:01:50,650
more likely to find the greater value as we go to the two extremes of the given array.

30
00:01:50,650 --> 00:01:52,900
Now why do I say that we are more likely?

31
00:01:52,900 --> 00:01:57,520
It could be that our array is just one, two, five and ten.

32
00:01:57,520 --> 00:01:59,170
This also is a sorted array.

33
00:01:59,170 --> 00:02:03,970
Now over here you can see that we are only part of this part of the number line.

34
00:02:03,970 --> 00:02:07,210
So as we go towards the right the squares increase right.

35
00:02:07,210 --> 00:02:12,850
But then we could also have an array which is like minus nine, minus eight, one and two.

36
00:02:12,850 --> 00:02:13,210
Right.

37
00:02:13,210 --> 00:02:18,970
So over here we can see that we have moved more towards the left from zero in this part.

38
00:02:18,970 --> 00:02:21,760
So the square would be higher here rather than here.

39
00:02:21,760 --> 00:02:23,500
So this is an interesting property.

40
00:02:23,500 --> 00:02:27,850
So let's try to make use of this property to solve this in a better manner.

41
00:02:27,850 --> 00:02:34,750
Now because this is true if we look at the two extreme positions of the given array which is this position

42
00:02:34,750 --> 00:02:41,800
and this position, and if we square them, then one among these two definitely has to be the greatest

43
00:02:41,980 --> 00:02:43,780
or right, the greatest square.

44
00:02:44,230 --> 00:02:44,890
Now why is that?

45
00:02:44,890 --> 00:02:51,250
So now if we have a value over here and let's say we have a negative, I have minus three and I have

46
00:02:51,250 --> 00:02:51,820
minus two.

47
00:02:51,850 --> 00:02:55,120
So definitely minus three square will be greater than minus two square.

48
00:02:55,120 --> 00:02:57,580
So yes this is true.

49
00:02:57,580 --> 00:03:01,690
And again over here also if I have two and three three square is greater than two.

50
00:03:01,720 --> 00:03:07,270
So we are just looking at which is the greatest positive value or the greatest negative value.

51
00:03:07,270 --> 00:03:07,660
Right.

52
00:03:07,660 --> 00:03:10,300
So we just need to look at these two extremes.

53
00:03:10,300 --> 00:03:15,520
And we can be sure that one among these two will be the greatest when we square it.

54
00:03:15,520 --> 00:03:15,880
Right.

55
00:03:15,880 --> 00:03:21,970
So let's make use of this property to solve this question in a more time efficient manner.

56
00:03:21,970 --> 00:03:22,300
Right.

57
00:03:22,300 --> 00:03:25,360
So one among these two has to be the largest.

58
00:03:25,360 --> 00:03:30,880
When we square all these four, the largest has to be one among the squares of these two.

59
00:03:30,880 --> 00:03:31,240
Right.

60
00:03:31,240 --> 00:03:34,780
It will definitely not be one among the squares of these two.

61
00:03:34,780 --> 00:03:35,290
Right.

62
00:03:35,290 --> 00:03:36,040
All right.

63
00:03:36,220 --> 00:03:37,360
So let's look at that.

64
00:03:37,360 --> 00:03:40,780
Three square is nine and seven square is 49.

65
00:03:40,780 --> 00:03:44,470
So nine is less than 49 or the greater value is 49.

66
00:03:44,470 --> 00:03:49,720
So let's take this 49 and we fill this 49 over here.

67
00:03:49,720 --> 00:03:51,280
That is the new array.

68
00:03:51,280 --> 00:03:52,600
This is the new array which we made.

69
00:03:52,600 --> 00:03:58,360
And let's fill this 49 at the last position of the new array which is over here.

70
00:03:58,360 --> 00:04:00,340
So we write 49 over here.

71
00:04:00,340 --> 00:04:03,820
Now we got this 49 by doing seven square right.

72
00:04:03,820 --> 00:04:05,440
So we have already used this up.

73
00:04:05,440 --> 00:04:10,720
So let's move the pointer from here one to to the left which is two two.

74
00:04:11,500 --> 00:04:11,890
All right.

75
00:04:11,890 --> 00:04:16,480
So again our pointer one pointer is over here and one pointer is over here.

76
00:04:16,510 --> 00:04:20,200
Now the next greatest or the next largest.

77
00:04:20,200 --> 00:04:24,460
When we square these three has to be one among the squares of these two.

78
00:04:24,460 --> 00:04:24,850
Right.

79
00:04:24,850 --> 00:04:26,080
So let's look at that.

80
00:04:26,080 --> 00:04:29,740
Minus three square gives us nine and two square gives us four.

81
00:04:29,740 --> 00:04:31,360
Now nine is greater than four.

82
00:04:31,360 --> 00:04:35,350
So let's fill the next position in the new array which is this one.

83
00:04:35,350 --> 00:04:35,860
Over here.

84
00:04:35,860 --> 00:04:37,990
Let's fill the new position with nine.

85
00:04:38,560 --> 00:04:40,000
So we put nine over here.

86
00:04:40,000 --> 00:04:42,970
And we got nine by squaring minus three.

87
00:04:42,970 --> 00:04:44,680
So we have already used it up.

88
00:04:44,680 --> 00:04:48,460
And hence let's move this pointer one towards the right.

89
00:04:48,460 --> 00:04:48,850
Right.

90
00:04:48,850 --> 00:04:50,740
So we move the pointer over here.

91
00:04:50,740 --> 00:04:53,230
Now the two pointers are at one and two.

92
00:04:53,230 --> 00:04:57,160
Now again the next largest has to be one among the squares of these two.

93
00:04:57,190 --> 00:05:01,180
So again when we square we get one and four one is less than four.

94
00:05:01,180 --> 00:05:06,940
So we fill four over here which is at the next position in the array, the new array which we are creating.

95
00:05:06,940 --> 00:05:08,590
And we are just left with one.

96
00:05:08,590 --> 00:05:12,430
And the two pointers at this point, point at the same value.

97
00:05:12,430 --> 00:05:18,550
And we fill that over here, which is one right now we can see that we have got the array and it is

98
00:05:18,550 --> 00:05:18,910
sorted.

99
00:05:18,910 --> 00:05:21,190
We got 149 49.

100
00:05:21,190 --> 00:05:22,600
So this is the array.

101
00:05:22,600 --> 00:05:26,350
And it consists of the sorted integers of the given array.

102
00:05:26,350 --> 00:05:29,290
And this array over here is also sorted.

103
00:05:29,290 --> 00:05:36,100
So this is the better optimized solution or the better approach by which we can solve this problem.

104
00:05:36,100 --> 00:05:43,330
Again remember the property which we used is that the greatest when we square all the input like let's

105
00:05:43,330 --> 00:05:52,750
say we have an input array like minus ten of minus three, five, nine, 11, 12.

106
00:05:52,930 --> 00:06:00,160
So even irrespective of what the values are given in the array, the greatest when we square all of

107
00:06:00,160 --> 00:06:05,650
these will be one among minus ten square and 12 square, right.

108
00:06:05,650 --> 00:06:11,560
So we just need to compare these two, find the greatest and fill it at the last position of the new

109
00:06:11,560 --> 00:06:11,890
array.

110
00:06:11,890 --> 00:06:18,490
And then whichever was used up shift the pointer accordingly and keep comparing those two values and

111
00:06:18,490 --> 00:06:19,510
find the next one.

112
00:06:19,510 --> 00:06:26,620
In this way we filled the largest value at the rightmost most position, the second largest value at

113
00:06:26,620 --> 00:06:27,550
the next position.

114
00:06:27,550 --> 00:06:34,330
And we kept repeating that, and we got the sorted array, where each element was the square of the

115
00:06:34,330 --> 00:06:36,190
given elements in the initial array.

116
00:06:36,280 --> 00:06:36,850
All right.

117
00:06:36,880 --> 00:06:41,110
Now let's look at the space and time complexity of this approach.

118
00:06:41,110 --> 00:06:42,190
Initial approach.

119
00:06:42,190 --> 00:06:48,490
We have seen as per the brute force solution, the time complexity was n log n and the space complexity

120
00:06:48,490 --> 00:06:49,360
was O of n.

121
00:06:49,360 --> 00:06:53,170
Right now let's look at the space and time complexity of this solution.

122
00:06:53,170 --> 00:06:57,670
Over here we can see that we are only traversing the array once right?

123
00:06:57,670 --> 00:07:01,300
So the time complexity is only O of n.

124
00:07:01,630 --> 00:07:06,940
Now this is because we are just moving or traversing the array one time right now.

125
00:07:06,940 --> 00:07:08,830
What about the space complexity?

126
00:07:08,830 --> 00:07:14,860
The space complexity is still O of N because we are making a new array, which is this array over here.

127
00:07:14,860 --> 00:07:21,520
Now we can see that by using this property and the fact that the input array was already sorted, we

128
00:07:21,520 --> 00:07:23,440
were able to optimize the solution.

129
00:07:23,440 --> 00:07:28,690
And instead of O of n log n, we got a solution with the time complexity of O of n.