# Monotonic Arrays

> Learn how to determine whether an array is either monotonically increasing or decreasing.

February 25, 2022 · 6 min read · https://yasint.dev/monotonic-arrays/
Tags: algorithms, javascript

---

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.

<p className="indent-8">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.</p>

## 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 increasing function](./mono-inc.png "This is a function that satisfies the invariant \$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 $x \leq y$ then $\varDelta f(x) \geq \varDelta f(y)$, so it reverses the order.

![Monotonically decreasing function](./mono-dec.png "This is a function that satisfies the invariant $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.

![Strictly increasing and strictly decreasing functions](./mono-strictly-inc-dec.png "Illustrates $\varDelta f(x) \gt 0 \vee \varDelta f(x) \lt 0$ respectively.")

> **Should it only be continuous or variable?**
>
> The answer is simply **no**. A monotonic series of data can be equal too. So that, **non-increasing** elements aren't necessarily _exclusively decreasing_; they simply don't increase. Similarly, non-decreasing elements aren't necessarily _exclusively increasing_; they merely don't decrease.

For example, take a series of arbitrary data points `[ 1, 1, 1, 1, 1 ]` and `[ -1, -1, -1, -1, -1 ]` are entirely valid monotonic series. Hypothetically, if we are to plot this, it would look like the following: -

![Non-continuous monotonic function](./mono-non-continuous.png "$f$ is an absolute continuous function, if every $x$ value of the series is equal.")

## 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_.

![Comparison of adjacent elements in array](./mono-comparison.png "This is a function that satisfies the invariant $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.

```js
function isMonotonic(array) {

    if (array.length === 0) return false;
	if (array.length === 1) return true;

    // Start with a truthy assumption.
	let nonIncrementing = true, nonDecrementing = true;

	for (let i = 1; i < array.length; i++) {
		const x = array[i - 1], y = array[i];
		if (x > y) {
            nonIncrementing = false;
		}
		if (x < y) {
            nonDecrementing = false;
		}
	}

	return nonIncrementing || nonDecrementing;
}
```

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 ]`.

![First iteration of algorithm](./mono-1st-iteration.png)

![Second iteration of algorithm](./mono-2nd-iteration.png)

Even after the second iteration, we still iterating until $n$. This is not an issue from a time complexity standpoint; however, it is ugly 🤣! So how can we improve it, huh? Can we immediately bail out if we figure out both conditions are invalidated?

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.

> **Trending up/down**
>
> If the array is monotonically non-decreasing, we can say its series is trending _upwards_.
> Otherwise, if it's monotonically non-increasing trending _downwards_.

```js
function isMonotonic(array) {

	if (array.length === 0) return false;
	if (array.length === 1) return true;

	let trending = 0;

	for (let i = 1; i < array.length; i++) {
		const x = array[i - 1], y = array[i];
        if (x > y) {
			if (trending === -1) return false;
			trending = 1;
		}
		if (x < y) {
			if (trending === 1) return false;
			trending = -1;
		}
	}

	return true;
}
```

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 🥰.