Solution
Approach 1: Two Pass
Intuition
An array is monotonic if it is monotone increasing, or monotone decreasing. Since a <= b
and b <= c
implies a <= c
, we only need to check adjacent elements to determine if the array is monotone increasing (or decreasing, respectively). We can check each of these properties in one pass.
Algorithm
To check whether an array A
is monotone increasing, we'll check A[i] <= A[i+1]
for all i
. The check for monotone decreasing is similar.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: .
Approach 2: One Pass
Intuition
To perform this check in one pass, we want to handle a stream of comparisons from , corresponding to <
, ==
, or >
. For example, with the array [1, 2, 2, 3, 0]
, we will see the stream (1, 0, 1, 1)
.
Algorithm
Keep track of store
, equal to the first nonzero comparison seen (if it exists.) If we see the opposite comparison, the answer is False
.
Otherwise, every comparison was (necessarily) in the set , or every comparison was in the set , and therefore the array is monotonic.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: .
Approach 3: One Pass (Simple Variant)
Intuition and Algorithm
To perform this check in one pass, we want to remember if it is monotone increasing or monotone decreasing.
It's monotone increasing if there aren't some adjacent values A[i], A[i+1]
with A[i] > A[i+1]
, and similarly for monotone decreasing.
If it is either monotone increasing or monotone decreasing, then A
is monotonic.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: .
Analysis written by: @awice.