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.

Monotonicity

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.

Monotonically Increasing

A function is called monotonically increasing (also called increasing, constantly increasing, and non-decreasing), if for all $x$ and $y$ such that $x \leq y$ one has $\varDelta f(x) \leq \varDelta f(y)$, so $f$ preserves the order.

Monotonically Decreasing

A function is called monotonically decreasing (also called decreasing or constantly decreasing, and non-increasing) if, whenever $x \leq y$ then $\varDelta f(x) \geq \varDelta f(y)$, so it reverses the order.

Strictly Increasing and Strictly Decreasing

Say, if the order $\leq$ in the definition of monotonicity is replaced by the strict order $\lt$, 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 ($\geq$ to $\gt$), we get a strictly decreasing set of values.

Solution

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 $n-1$ steps with input array [ -1, -5, -10, -22, -22, -74, -75, -99 ]. It is equivalent to $O(n)$ in time complexity, and since we don't use any auxiliary space, our algorithm takes only constant space $O(1)$. 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 $0$ is equal, $-1$ as downward, and $1$ 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 $n$ times by placing assumption-based exit conditions.

That's it, folks! Thank you for reading 🥰.