# Monotonic Arrays

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

— 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 $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: -

## 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 $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

.Published —