How to Check If An Array is Monotonic?

An array is called monotonic if it is either monotone increasing or monotone decreasing.

An array A is monotone increasing if for all i <= j, A[i] <= A[j]. An array A is monotone decreasing if for all i <= j, A[i] >= A[j]. Return true if and only if the given array A is monotonic.

Example 1:
Input: [6,5,4,4]
Output: true
Example 2:
Input: [1,3,2]
Output: false

Two Passes Algorithm to Test if Array is Monotonic

We can scan the array twice (two passes) with O(N) complexity (with space complexity O(1) – constant) – one to test if array is monotonic increasing and another to test if array is monotonic decreasing, based on the definition. The C++ implementation is straightforward, as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    bool isMonotonicIncreasing(vector<int>& A) {
        for (int i = 1; i < A.size(); ++ i) {
            if (A[i] < A[i - 1]) {
                return false;
            }
        }
        return true;
    }
 
    bool isMonotonicDecreasing(vector<int>& A) {
        for (int i = 1; i < A.size(); ++ i) {
            if (A[i] > A[i - 1]) {
                return false;
            }
        }
        return true;
    }
    
    bool isMonotonic(vector<int>& A) {
        return isMonotonicIncreasing(A) || isMonotonicDecreasing(A);
    }
};

class Solution {
public:
    bool isMonotonicIncreasing(vector<int>& A) {
        for (int i = 1; i < A.size(); ++ i) {
            if (A[i] < A[i - 1]) {
                return false;
            }
        }
        return true;
    }

    bool isMonotonicDecreasing(vector<int>& A) {
        for (int i = 1; i < A.size(); ++ i) {
            if (A[i] > A[i - 1]) {
                return false;
            }
        }
        return true;
    }
    
    bool isMonotonic(vector<int>& A) {
        return isMonotonicIncreasing(A) || isMonotonicDecreasing(A);
    }
};

Alternatively, we define a integer comparison function sgn which returns -1, 0 or 1 to represent the relations between two integers, smaller, equal or bigger.

Next, we keep track of the prev variable which stores a non-zero comparison result. If we see the opposite, the answer is false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:    
    bool isMonotonic(vector<int>& A) {
        auto sgn = [](int a, int b) { // local functions
            return a < b ? -1 : (a == b) ? 0 : 1;
        };
        int prev = 0;
        for (int i = 0; i < A.size() - 1; ++ i) {
            int c = sgn(A[i], A[i + 1]);
            if (c != 0) {
                if (c != prev && prev != 0) {
                    return false;
                }
                prev = c;
            }
        }
        return true;
    }
};

class Solution {
public:    
    bool isMonotonic(vector<int>& A) {
        auto sgn = [](int a, int b) { // local functions
            return a < b ? -1 : (a == b) ? 0 : 1;
        };
        int prev = 0;
        for (int i = 0; i < A.size() - 1; ++ i) {
            int c = sgn(A[i], A[i + 1]);
            if (c != 0) {
                if (c != prev && prev != 0) {
                    return false;
                }
                prev = c;
            }
        }
        return true;
    }
};

One pass algorithm costs O(N) with space O(1) – constant.

For a Single Pass Algorithm that is written in Python: Teaching Kids Programming – Algorithm to Check If Array is Monotonic

–EOF (The Ultimate Computing & Technology Blog) —