Let’s say we want to write a function that takes in an array of integers and returns a boolean representing whether the array is monotonic or not. An array is said to be monotonic if its elements, from left to right, are entirely non-increasing or entirely non-decreasing.
Well, what’s non-increasing and non-decreasing?! It’s confusing at first. So, before we interpret the problem statement, first, we need to understand what we mean by monotonic mathematically.
In mathematics, a monotonic function is a function that is either non-increasing (decreasing) or non-decreasing (increasing). A function is monotonic if its first derivative does not change the sign.
A function is called monotonically increasing (also called increasing, constantly increasing, and non-decreasing), if for all and such that one has , so preserves the order.
A function is called monotonically decreasing (also called decreasing or constantly decreasing, and non-increasing) if, whenever then , so it reverses the order.
Say, if the order in the definition of monotonicity is replaced by the strict order , one obtains a stronger requirement. A function with this property is called strictly increasing, distinguished by a series of continuously increasing sets of values. In the same way, if we invert the symbol ( to ), we get a strictly decreasing set of values.
Suppose we are given the array
[ -1, -5, -10, -22, -22, -74, -75, -99 ] and required
return a boolean representing whether the array is monotonic or not. Seems pretty easy, right?
Well, how can we tackle it? Can we solve it in linear time?
First, let’s break down what we have to solve.
- Iterate through the entire array from left to right.
- Determine if the array is non-increasing or non-decreasing.
- If either of the conditions is
true, return true, else false.
We can try iterating through the input array from left to right in search of two adjacent integers that can indicate whether the array is trending upwards or downwards.
Hmm, it seems like this challenge's deduction process is a bit tricky, isn’t it? How can we tell whether it’s non-increasing or non-decreasing simultaneously? Should we use two for-loops or just one?
First, we can assume that the array is both entirely non-decreasing and entirely non-increasing. As we iterate through each element, we can see if we can invalidate one or both assumptions. Now, let's write the algorithm.
The above algorithm runs in steps with input array
[ -1, -5, -10, -22, -22, -74, -75, -99 ].
It is equivalent to in time complexity, and since we don't use any auxiliary space,
our algorithm takes only constant space . But can we improve this a little more, huh?
Even though this algorithm runs in linear time and uses constant space, we iterate till the last element regardless of our invalidation logic. Say, for example, if we input a non-monotonic series, iterates the entire array even when we invalidate our assumption.
Here's what I mean: -
Switching Inputs — I'm changing the input array a bit. The element at index 1 is now 5 making it the array
[ -1, 5, -10, -22, -22, -74, -75, -99 ].
We can take the same approach by iterating through the input array from left to right in search of two adjacent integers that indicate whether the array is trending upward or downward. Once we have found the tentative trend of the array, at each element after that, compare the element to the previous one; if this comparison breaks the previously identified trend, the array isn't monotonic.
You can think of the variable
trending as an enumeration. I used it to keep track of the direction
of the algorithm, where is
downward, and as
upwards. With the direction
in place, we can place each monotonic condition with a comparison breaker logic to stop the
algorithm if the previously identified trend differs from the current.
We can ensure our algorithm does not iterate a redundant amount of times by placing assumption-based exit conditions.
That's it, folks! Thank you for reading 🥰.
Well, now what?
You can navigate to more writings from here. Connect with me on LinkedIn for a chat.