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 non-zero 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.