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.
Example 1:
Input: nums = [1,2,2,3]
Output: true
Example 2:
Input: nums = [6,5,4,4]
Output: true
Example 3:
Input: nums = [1,3,2]
Output: false
Constraints:
-
1 <= nums.length <= 105
-
-105 <= nums[i] <= 105
Approach 1: Two Pass
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; } }
Complexity Analysis
Time Complexity: O(N), where NN is the length of A.
Space Complexity: O(1)
Approach 2: One Pass
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 \{-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; } }
Complexity Analysis
Time Complexity: O(N), where NN is the length of A.
Space Complexity: O(1)
Approach 3: One Pass (Simple Variant)
class Solution { public boolean isMonotonic(int[] A) { boolean increasing = true; boolean decreasing = true; for (int i = 0; i < A.length - 1; ++i) { if (A[i] > A[i+1]) increasing = false; if (A[i] < A[i+1]) decreasing = false; } return increasing || decreasing; } }
Complexity Analysis
Time Complexity: O(N) where NN is the length of A.
Space Complexity: O(1)