By Yasin

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 xx and yy such that xyx \leq y one has Δf(x)Δf(y)\varDelta f(x) \leq \varDelta f(y), so ff preserves the order.

figure 1 — This is a function that satisfies the invariant f(x)f(y)f(x) \leq f(y). Note that in a monotonic series, values can be constant over an interval.

Monotonically Decreasing

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

figure 2 — This is a function that satisfies the invariant f(x)f(y)f(x) \geq f(y).

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.

figure 3 — Illustrates Δf(x)>0Δf(x)<0\varDelta f(x) \gt 0 \vee \varDelta f(x) \lt 0 respectively.

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.

figure 5 — This is a function that satisfies the invariant f(x)f(y)f(x) \leq f(y). Note that in a monotonic series, values can be constant over an interval.

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 n1n-1 steps with input array [ -1, -5, -10, -22, -22, -74, -75, -99 ]. It is equivalent to O(n)O(n) in time complexity, and since we don't use any auxiliary space, our algorithm takes only constant space O(1)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: -

I'm 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 00 is equal, 1-1 as downward, and 11 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 nn times by placing assumption-based exit conditions.

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

Published   

Join Newsletter 👀

If you like my articles and content, consider signing up for my monthly newsletter. You'll receive updates on new articles, gain access to exclusive posts and things I find interesting and useful.