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

An array nums is monotone increasing if for all i <= j, nums[i] <= nums[j]. An array nums is monotone decreasing if for all i <= j, nums[i] >= nums[j].

Given an integer array nums, return true if the given array is monotonic, or false otherwise.

Overview

Optimal Solution

Flow Diagram

Simply checking each element with the previous element and keeping track of the trend, is a perfect and elegant solution.

Time Complexity

As we are traversing the whole array once, the time complexity is O(n). No other complex operation needed.

Space Complexity

No extra space is needed for this algorithm. Space complexity is constant O(1). I like it.

Java Source Code

    public boolean isMonotonic(int[] array) {
        boolean isNonDecresing = true;
        boolean isNonIncreasing = true;

        for(int i=1;i<array.length;i++) {
            if(array[i] < array[i-1]) {
                isNonDecresing = false;
            }

            if(array[i] > array[i-1]) {
                isNonIncreasing = false;
            }
        }

        return isNonDecresing || isNonIncreasing;
    }

Conclusion

The trend is your friend.

Martin Zweig