An array is monotonic if it is either monotone increasing or monotone decreasing.
More formally if all the elements are either in increasing order or decreasing order.
That is for an given array nums[], it is monotone increasing if all i <= j, nums[i] <= nums[j].
it is monotone decreasing if for all i <= j, nums[i] >= nums[j].
In in article we will see how to efficiently decide if a given array is monotonic or not.
Examples
Examples of Monotonic arrays
Increasing monotonic array:
[1, 2, 20, 30]
[1, 2, 20, 20, 30]
decreasing monotonic array:
[66, 50, 40, 4]
[66, 50, 40, 40]
Increasing monotonic array:
[1, 2, 20, 30]
[1, 2, 20, 20, 30]
decreasing monotonic array:
[66, 50, 40, 4]
[66, 50, 40, 40]
Algorithm
Iterate over the array and keep track of the first nonequal comparison to a variable signal. And once the signal is set check if holds true for the next set of array items.
Implementation
Implementation of the monotonic array is not very tough. Here we will see how to implement it in a single pass (single iteration of the input array) in Java.
MonotonicArray
Following Java, the class implement is a monotonic method that checks if an array is monotonic in a single pass.
public class MonotonicArray {
public boolean isMonotonic(int[] nums) {
int signal = -1; // -1 = not set, 0 = increasing, 1 = decreasing
// iterate over the array till the arry.length-1 from 0
for (int i = 0; i < nums.length - 1; i++) {
// if signal is not initialized and we see either increasing or decreasing array
// initialize it accordingly
if (signal == -1) {
if (nums[i] < nums[i + 1]) {
signal = 0; // increasing
} else if (nums[i] > nums[i + 1]) {
signal = 1; // decreasing
}
} else {
// once the signal is already initialized
// then check if for other elements it holds true or not
if (signal == 0 && nums[i] > nums[i + 1]) {
return false;
}
if (signal == 1 && nums[i] < nums[i + 1]) {
return false;
}
}
}
return true;
}
}
Code Complexity
Runtime complexity: O(n) where n is the number of elements in the array. As we are iterating the array once.
Space complexity: O(1) as we are not using extra storage
