Welcome back.
Let's now think through how we can solve this question.
Now first let's think of the condition of non increasing.
Now let's say we have an array.
Now we have an element at the index I and we have an element at index I plus one.
Now if the given array is non increasing what would it mean with respect to these two values.
Right.
We can say that over here.
Whatever comes over here has to be greater than or equal to what comes to the right of it.
Right.
Only then it will be non increasing.
That means this value over here can definitely not be greater than what we have over here right now.
Similarly what is the case of non decreasing.
Again we have an element at index I and we have an element at index I plus one.
Now if it is non decreasing then whatever we have at I plus one can be greater than or equal to what
we have over here.
Right.
For example now if let's just take an example I have two elements over here.
Now if I have two and two yes I can say that it's non increasing.
Right.
And if I have let's say seven and one in this case also I can say it is non increasing.
That is when you go from left to right you're sure that the value is not increasing.
So that what.
That's what we can talk say about it in plain English.
Similarly over here also if I have two and two it is still non decreasing.
And if I have let's say I have ten over here and I have one over here right now.
In this case it's, it's decreasing.
So I should have something greater than this right.
So let's say I have 12 over here, ten over here and 12 over here.
Now in this case when you go from left to right, right, you can be sure that the value is not decreasing
or it is not decreasing.
All right.
So that is what we have understood over here.
So we have understood what we mean with non increasing and non decreasing.
All right.
Now let's proceed.
Now let's say we look at three possible scenarios.
So I have three arrays over here.
Now we look at the first element and the last element of the given array.
So in this instance where the array which is given to us has three as the first element and seven as
the last element.
Right now this is the second case where we have three and three over here.
And then we have three and minus five over here.
So these are the three cases right?
I'm just writing one two and three over here.
Now let's think through what we can identify in each of these cases.
When we compare an element at the ith index and at the I plus one index which is the next element right
in the given array.
Now let's look at the first case.
Now if the first element is three and the last element is seven, this array over here can be monotonic
only if it is monotonic increasing right.
So it can only be monotonic if it is monotonic increasing.
And for it to be monotonic increasing it should be non decreasing.
Right.
That means as you go to the right, the value can either be greater than the previous value or it can
be equal to the previous value.
But it cannot be uh, it cannot be lesser.
Right.
Because if it is lesser then it's no longer non decreasing.
All right.
So what is it that we can do when we let's say we loop through the elements of the array.
And if we compare array at I and array at I plus one, we can be sure that if we find two values where
array at I plus one is less than array at I, or the right element is less than the previous element.
Then we can definitely be sure that this array over here is not monotonic, right?
So we can say false right now.
Similarly, if we have and again remember why are we checking whether it's false.
Because it's easy right.
So the value has to be non decreasing.
We have seen that right now.
What is the opposite of non decreasing.
The opposite of non decreasing is just decreasing.
Right.
So that's why we are checking over here.
The opposite which is decreasing.
And if it is decreasing definitely it's not monotonic.
And we can just return false.
All right.
Now let's proceed.
Let me just clear this up over here.
Now what about the second case.
Over here we have three as the first element.
And the last element is also three.
Now the only way for this array to be monotonic is if all these elements they have to be three.
Right.
We have to get three over here.
And we have to get three over here.
Only then we can say that this array is monotonic.
Right.
If we let's, let's say we have four over here and then five six and again three.
Right.
So then definitely it will not be non increasing or non decreasing.
Right.
So the only possibility is if all of these are three.
So as we loop through the array right.
As we compare array at I and array at I plus one, we just need to check if all of them are equal right.
So these two should be equal.
These two should be equal.
These two should be equal and these two should be equal.
Now if any of these conditions is violated then this array will definitely not be monotonic.
And we can just return false.
Right.
So if all of them are not equal then we can just return false.
All right.
Now let's look at the last case again.
We are comparing the first element and the last element.
Now over here we.
We can see that the last element is less than the first element, right?
So if that is the case, then this array over here can only be monotonic decreasing.
Right.
And for this for it to be monotonic decreasing it has to be non increasing.
That is as you go to the right you should not get a value greater than the previous value.
Now what is the opposite of it.
You just have to check as you go to the right as you compare these two, if you are getting a greater
value right?
So as you check these values, as you loop through the array, if you see that the element at I plus
one index is greater than the element at I, then it cannot be non increasing or it cannot be monotonic
decreasing.
Therefore it is false.
Right.
So we have seen how we can solve this right.
So we we just have these three possibilities.
Now we are going to identify which of these possibilities is the case with respect to the array which
is given to us.
And then we are going to loop through the array.
And we are going to check whether it is false.
Now if you are not able to return false, then we can be sure that the given array is monotonic.
So this is how we can solve this question.
It's pretty straightforward and pretty easy.
The only thing is like we have many terms like non increasing and monotonic decreasing etc. right.
So that should not confuse us.
We understand that the only reason why it's it's saying not plainly increasing is because there is a
possibility of two values to be equal.
So you just need to factor in that possibility also.
Now let's go ahead and look at the time and space complexity of this solution.
Now the time complexity of this solution is clearly o of N right.
Why is that?
So we are just identifying what is the case based on these three cases one two, three.
And for that we just need to read the first and last value and compare them.
That's a constant time operation.
Now once we have identified whether the scenario is one, 2 or 3, then we just loop through the array
one time, right?
To compare the elements at array at ith index and array at I plus one index, which is a for loop,
right.
So we are just looping through the array one time.
And that's why the time complexity of this solution is of the order of n, where n is the length of
the given array.
Now what about the space complexity?
The space complexity of this solution will be constant space or O of one, because we are not using
any auxiliary space.