An array is 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.
Input: [1,2,2,3]
Output: true
Input: [6,5,4,4]
Output: true
Input: [1,3,2]
Output: false
Input: [1,2,4,5]
Output: true
Input: [1,1,1]
Output: true
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.
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.
class Solution {
public boolean isMonotonic(int[] A) {
return increasing(A) || decreasing(A);
}
public boolean increasing(int[] A) {
for (int i = 0; i < A.length - 1; ++i)
if (A[i] > A[i+1]) return false;
return true;
}
public boolean decreasing(int[] A) {
for (int i = 0; i < A.length - 1; ++i)
if (A[i] < A[i+1]) return false;
return true;
}
}
Time complexity : O(n) where N is the length of A.
Space complexity : O(1)
To perform this check in one pass, we want to handle a stream of comparisons from {-1, 0, 1}{−1,0,1}, corresponding to <, ==, or >. For example, with the array [1, 2, 2, 3, 0], we will see the stream (-1, 0, -1, 1).
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 {-1, 0}{−1,0}, or every comparison was in the set {0, 1}{0,1}, and therefore the array is monotonic
class Solution {
public boolean isMonotonic(int[] A) {
int store = 0;
for (int i = 0; i < A.length - 1; ++i) {
int c = Integer.compare(A[i], A[i+1]);
if (c != 0) {
if (c != store && store != 0)
return false;
store = c;
}
}
return true;
}
}
Time complexity : O(n) where N is the length of A.
Space complexity : O(1)