1
00:00:00,580 --> 00:00:01,720
Welcome back.

2
00:00:01,720 --> 00:00:04,870
Let's now think through how we can solve this question.

3
00:00:04,900 --> 00:00:08,500
Now first let's think of the condition of non increasing.

4
00:00:08,500 --> 00:00:10,150
Now let's say we have an array.

5
00:00:10,180 --> 00:00:16,090
Now we have an element at the index I and we have an element at index I plus one.

6
00:00:16,090 --> 00:00:22,780
Now if the given array is non increasing what would it mean with respect to these two values.

7
00:00:22,780 --> 00:00:23,110
Right.

8
00:00:23,110 --> 00:00:24,670
We can say that over here.

9
00:00:24,670 --> 00:00:29,980
Whatever comes over here has to be greater than or equal to what comes to the right of it.

10
00:00:29,980 --> 00:00:30,310
Right.

11
00:00:30,310 --> 00:00:32,410
Only then it will be non increasing.

12
00:00:32,410 --> 00:00:38,080
That means this value over here can definitely not be greater than what we have over here right now.

13
00:00:38,080 --> 00:00:40,720
Similarly what is the case of non decreasing.

14
00:00:40,720 --> 00:00:45,790
Again we have an element at index I and we have an element at index I plus one.

15
00:00:45,790 --> 00:00:52,780
Now if it is non decreasing then whatever we have at I plus one can be greater than or equal to what

16
00:00:52,780 --> 00:00:53,560
we have over here.

17
00:00:53,560 --> 00:00:53,950
Right.

18
00:00:53,950 --> 00:00:58,630
For example now if let's just take an example I have two elements over here.

19
00:00:58,630 --> 00:01:02,710
Now if I have two and two yes I can say that it's non increasing.

20
00:01:02,710 --> 00:01:03,100
Right.

21
00:01:03,100 --> 00:01:08,890
And if I have let's say seven and one in this case also I can say it is non increasing.

22
00:01:08,890 --> 00:01:13,360
That is when you go from left to right you're sure that the value is not increasing.

23
00:01:13,360 --> 00:01:14,140
So that what.

24
00:01:14,140 --> 00:01:17,440
That's what we can talk say about it in plain English.

25
00:01:17,440 --> 00:01:22,390
Similarly over here also if I have two and two it is still non decreasing.

26
00:01:22,390 --> 00:01:27,430
And if I have let's say I have ten over here and I have one over here right now.

27
00:01:27,430 --> 00:01:29,890
In this case it's, it's decreasing.

28
00:01:29,890 --> 00:01:31,810
So I should have something greater than this right.

29
00:01:31,810 --> 00:01:34,510
So let's say I have 12 over here, ten over here and 12 over here.

30
00:01:34,510 --> 00:01:40,900
Now in this case when you go from left to right, right, you can be sure that the value is not decreasing

31
00:01:40,900 --> 00:01:42,490
or it is not decreasing.

32
00:01:42,490 --> 00:01:42,910
All right.

33
00:01:42,910 --> 00:01:45,340
So that is what we have understood over here.

34
00:01:45,340 --> 00:01:49,360
So we have understood what we mean with non increasing and non decreasing.

35
00:01:49,360 --> 00:01:49,810
All right.

36
00:01:49,810 --> 00:01:51,010
Now let's proceed.

37
00:01:51,430 --> 00:01:54,460
Now let's say we look at three possible scenarios.

38
00:01:54,460 --> 00:01:56,050
So I have three arrays over here.

39
00:01:56,050 --> 00:02:00,520
Now we look at the first element and the last element of the given array.

40
00:02:00,520 --> 00:02:06,160
So in this instance where the array which is given to us has three as the first element and seven as

41
00:02:06,160 --> 00:02:07,120
the last element.

42
00:02:07,120 --> 00:02:10,330
Right now this is the second case where we have three and three over here.

43
00:02:10,330 --> 00:02:12,700
And then we have three and minus five over here.

44
00:02:12,700 --> 00:02:14,350
So these are the three cases right?

45
00:02:14,410 --> 00:02:16,900
I'm just writing one two and three over here.

46
00:02:16,900 --> 00:02:21,580
Now let's think through what we can identify in each of these cases.

47
00:02:21,580 --> 00:02:27,970
When we compare an element at the ith index and at the I plus one index which is the next element right

48
00:02:27,970 --> 00:02:28,930
in the given array.

49
00:02:28,930 --> 00:02:30,520
Now let's look at the first case.

50
00:02:30,520 --> 00:02:37,330
Now if the first element is three and the last element is seven, this array over here can be monotonic

51
00:02:37,330 --> 00:02:39,670
only if it is monotonic increasing right.

52
00:02:39,670 --> 00:02:43,570
So it can only be monotonic if it is monotonic increasing.

53
00:02:43,570 --> 00:02:49,000
And for it to be monotonic increasing it should be non decreasing.

54
00:02:49,000 --> 00:02:49,240
Right.

55
00:02:49,240 --> 00:02:55,150
That means as you go to the right, the value can either be greater than the previous value or it can

56
00:02:55,150 --> 00:02:56,620
be equal to the previous value.

57
00:02:56,620 --> 00:02:59,320
But it cannot be uh, it cannot be lesser.

58
00:02:59,320 --> 00:02:59,530
Right.

59
00:02:59,530 --> 00:03:03,190
Because if it is lesser then it's no longer non decreasing.

60
00:03:03,190 --> 00:03:03,640
All right.

61
00:03:03,640 --> 00:03:08,200
So what is it that we can do when we let's say we loop through the elements of the array.

62
00:03:08,200 --> 00:03:15,610
And if we compare array at I and array at I plus one, we can be sure that if we find two values where

63
00:03:15,640 --> 00:03:21,280
array at I plus one is less than array at I, or the right element is less than the previous element.

64
00:03:21,280 --> 00:03:26,200
Then we can definitely be sure that this array over here is not monotonic, right?

65
00:03:26,200 --> 00:03:28,450
So we can say false right now.

66
00:03:28,450 --> 00:03:34,270
Similarly, if we have and again remember why are we checking whether it's false.

67
00:03:34,270 --> 00:03:35,350
Because it's easy right.

68
00:03:35,350 --> 00:03:37,660
So the value has to be non decreasing.

69
00:03:37,660 --> 00:03:39,010
We have seen that right now.

70
00:03:39,010 --> 00:03:41,080
What is the opposite of non decreasing.

71
00:03:41,080 --> 00:03:43,900
The opposite of non decreasing is just decreasing.

72
00:03:43,900 --> 00:03:44,110
Right.

73
00:03:44,110 --> 00:03:45,760
So that's why we are checking over here.

74
00:03:45,760 --> 00:03:47,260
The opposite which is decreasing.

75
00:03:47,260 --> 00:03:50,830
And if it is decreasing definitely it's not monotonic.

76
00:03:50,830 --> 00:03:52,840
And we can just return false.

77
00:03:52,840 --> 00:03:53,470
All right.

78
00:03:53,500 --> 00:03:54,400
Now let's proceed.

79
00:03:54,400 --> 00:03:56,050
Let me just clear this up over here.

80
00:03:56,650 --> 00:03:58,480
Now what about the second case.

81
00:03:58,480 --> 00:04:01,000
Over here we have three as the first element.

82
00:04:01,000 --> 00:04:02,950
And the last element is also three.

83
00:04:02,950 --> 00:04:08,170
Now the only way for this array to be monotonic is if all these elements they have to be three.

84
00:04:08,170 --> 00:04:08,380
Right.

85
00:04:08,380 --> 00:04:09,760
We have to get three over here.

86
00:04:09,760 --> 00:04:11,290
And we have to get three over here.

87
00:04:11,290 --> 00:04:12,670
And we have to get three over here.

88
00:04:12,670 --> 00:04:15,400
Only then we can say that this array is monotonic.

89
00:04:15,400 --> 00:04:15,640
Right.

90
00:04:15,640 --> 00:04:19,720
If we let's, let's say we have four over here and then five six and again three.

91
00:04:19,720 --> 00:04:19,990
Right.

92
00:04:19,990 --> 00:04:23,800
So then definitely it will not be non increasing or non decreasing.

93
00:04:23,800 --> 00:04:24,070
Right.

94
00:04:24,070 --> 00:04:26,620
So the only possibility is if all of these are three.

95
00:04:26,620 --> 00:04:29,260
So as we loop through the array right.

96
00:04:29,260 --> 00:04:35,860
As we compare array at I and array at I plus one, we just need to check if all of them are equal right.

97
00:04:35,860 --> 00:04:37,540
So these two should be equal.

98
00:04:37,540 --> 00:04:38,710
These two should be equal.

99
00:04:38,710 --> 00:04:41,110
These two should be equal and these two should be equal.

100
00:04:41,110 --> 00:04:47,350
Now if any of these conditions is violated then this array will definitely not be monotonic.

101
00:04:47,350 --> 00:04:49,360
And we can just return false.

102
00:04:49,360 --> 00:04:49,660
Right.

103
00:04:49,660 --> 00:04:53,080
So if all of them are not equal then we can just return false.

104
00:04:53,080 --> 00:04:53,620
All right.

105
00:04:53,650 --> 00:04:55,960
Now let's look at the last case again.

106
00:04:55,960 --> 00:04:59,230
We are comparing the first element and the last element.

107
00:04:59,230 --> 00:05:00,160
Now over here we.

108
00:05:00,260 --> 00:05:04,130
We can see that the last element is less than the first element, right?

109
00:05:04,130 --> 00:05:09,350
So if that is the case, then this array over here can only be monotonic decreasing.

110
00:05:09,350 --> 00:05:09,680
Right.

111
00:05:09,680 --> 00:05:15,110
And for this for it to be monotonic decreasing it has to be non increasing.

112
00:05:15,110 --> 00:05:19,940
That is as you go to the right you should not get a value greater than the previous value.

113
00:05:19,940 --> 00:05:21,470
Now what is the opposite of it.

114
00:05:21,470 --> 00:05:25,790
You just have to check as you go to the right as you compare these two, if you are getting a greater

115
00:05:25,790 --> 00:05:26,330
value right?

116
00:05:26,330 --> 00:05:32,990
So as you check these values, as you loop through the array, if you see that the element at I plus

117
00:05:32,990 --> 00:05:39,620
one index is greater than the element at I, then it cannot be non increasing or it cannot be monotonic

118
00:05:39,620 --> 00:05:40,250
decreasing.

119
00:05:40,250 --> 00:05:41,990
Therefore it is false.

120
00:05:41,990 --> 00:05:42,620
Right.

121
00:05:43,010 --> 00:05:44,750
So we have seen how we can solve this right.

122
00:05:44,750 --> 00:05:47,240
So we we just have these three possibilities.

123
00:05:47,240 --> 00:05:52,220
Now we are going to identify which of these possibilities is the case with respect to the array which

124
00:05:52,220 --> 00:05:53,030
is given to us.

125
00:05:53,030 --> 00:05:55,310
And then we are going to loop through the array.

126
00:05:55,310 --> 00:05:57,980
And we are going to check whether it is false.

127
00:05:57,980 --> 00:06:03,350
Now if you are not able to return false, then we can be sure that the given array is monotonic.

128
00:06:03,350 --> 00:06:05,630
So this is how we can solve this question.

129
00:06:05,630 --> 00:06:08,150
It's pretty straightforward and pretty easy.

130
00:06:08,150 --> 00:06:13,850
The only thing is like we have many terms like non increasing and monotonic decreasing etc. right.

131
00:06:13,850 --> 00:06:15,470
So that should not confuse us.

132
00:06:15,470 --> 00:06:21,290
We understand that the only reason why it's it's saying not plainly increasing is because there is a

133
00:06:21,290 --> 00:06:23,540
possibility of two values to be equal.

134
00:06:23,540 --> 00:06:26,330
So you just need to factor in that possibility also.

135
00:06:26,330 --> 00:06:30,320
Now let's go ahead and look at the time and space complexity of this solution.

136
00:06:30,320 --> 00:06:34,490
Now the time complexity of this solution is clearly o of N right.

137
00:06:34,490 --> 00:06:35,090
Why is that?

138
00:06:35,090 --> 00:06:39,950
So we are just identifying what is the case based on these three cases one two, three.

139
00:06:39,950 --> 00:06:44,420
And for that we just need to read the first and last value and compare them.

140
00:06:44,420 --> 00:06:46,190
That's a constant time operation.

141
00:06:46,190 --> 00:06:52,370
Now once we have identified whether the scenario is one, 2 or 3, then we just loop through the array

142
00:06:52,370 --> 00:06:53,210
one time, right?

143
00:06:53,210 --> 00:06:58,730
To compare the elements at array at ith index and array at I plus one index, which is a for loop,

144
00:06:58,730 --> 00:06:59,030
right.

145
00:06:59,030 --> 00:07:01,790
So we are just looping through the array one time.

146
00:07:01,790 --> 00:07:07,190
And that's why the time complexity of this solution is of the order of n, where n is the length of

147
00:07:07,190 --> 00:07:07,940
the given array.

148
00:07:07,970 --> 00:07:10,040
Now what about the space complexity?

149
00:07:10,040 --> 00:07:15,770
The space complexity of this solution will be constant space or O of one, because we are not using

150
00:07:15,770 --> 00:07:17,330
any auxiliary space.