Leetcode 896. Monotonic Array
Problem Explanation
Given an array, we are supposed to determine if it is monotonic. By definition, an array is monotonic if it is either entirely non-increasing or entirely non-decreasing.
More explicitly, a non-decreasing array meets the requirement where every element at position i
, is less than or equal to the next element i+1
. On the other hand, a non-increasing array is one where each element at position i
is greater than or equal to next element i+1
.
We should return True
if the array is monotonic and False
if it is not.
Approach
The solution to this problem is straightforward because we just need to determine if the array is either entirely non-increasing or entirely non-decreasing. This can be achieved in a single pass through the array.
- We could start by assuming the array is both non-increasing and non-decreasing.
- Then, for every pair of adjacent elements, we check if they are in non-decreasing order or non-increasing order.
- If they are not in non-decreasing order, we discard the possibility that the entire array could be non-decreasing and vice versa.
- At the end of the traversal, if either of the possibilities still remain, we conclude that the array is monotonic.
Example
Consider this array [1, 2, 2, 3], we start by assuming that it is both non-decreasing and non-increasing. We then check each pair of elements as follows:
Looking at 1
and 2
, we can see that 1 <= 2
, so the array could be non-decreasing. However, 1 >= 2
is not true so we discard the possibility that the array could be non-increasing.
We follow the same procedure for the pairs 2 and 2
, 2 and 3
. At the end, we realize that the array is non-decreasing.
Solutions
Python
1 2python 3class Solution: 4 def isMonotonic(self, A): 5 return (all(A[i] <= A[i + 1] for i in range(len(A) - 1)) or 6 all(A[i] >= A[i + 1] for i in range(len(A) - 1)))
Java
1 2java 3class Solution { 4 public boolean isMonotonic(int[] A) { 5 boolean increasing = true; 6 boolean decreasing = true; 7 8 for (int i = 0; i < A.length - 1; ++i) { 9 if (A[i] > A[i+1]) 10 increasing = false; 11 if (A[i] < A[i+1]) 12 decreasing = false; 13 } 14 15 return increasing || decreasing; 16 } 17}
JavaScript
1 2javascript 3var isMonotonic = function(A) { 4 let increasing = decreasing = true; 5 6 for(let i = 0; i < A.length - 1; i++) { 7 if(A[i] > A[i+1]) increasing = false; 8 if(A[i] < A[i+1]) decreasing = false; 9 } 10 11 return increasing || decreasing; 12};
C++
1 2c++ 3class Solution { 4public: 5 bool isMonotonic(vector<int>& A) { 6 bool increasing = true; 7 bool decreasing = true; 8 9 for (int i = 1; i < A.size(); ++i) { 10 if (A[i] > A[i - 1]) 11 increasing = false; 12 if (A[i] < A[i - 1]) 13 decreasing = false; 14 } 15 16 return increasing || decreasing; 17 } 18};
C#
1 2csharp 3public class Solution { 4 public bool IsMonotonic(int[] A) { 5 bool increasing = true; 6 bool decreasing = true; 7 8 for (int i = 0; i < A.Length - 1; ++i) { 9 if (A[i] > A[i+1]) 10 increasing = false; 11 if (A[i] < A[i+1]) 12 decreasing = false; 13 } 14 15 return increasing || decreasing; 16 } 17}
In the solutions above we check if the array is non-increasing or non-decreasing.
For each pair of adjacent elements, we check if they are in non-increasing or non-decreasing order. If the elements are not in non-increasing, the array cannot be non-increasing, so we set increasing
to false. If the elements are not in non-decreasing order, then it cannot be non-decreasing, so we set decreasing
to false.
If at the end of the loop, either increasing
or decreasing
is true
, the array is monotonic.# Time and Space Complexity Analysis
The time complexity of the solution is O(n), where n is the number of elements in the array. This is because we make a single pass through all elements of array to check if they meet the given conditions.
The space complexity is O(1) as we have used a constant amount of space to store our variables (increasing and decreasing). We did not use any extra data structures whose size scales with the input size.
Summary
Checking if an array is monotonic involves determining whether the array is entirely non-increasing or non-decreasing. This can be checked in a single pass through the array, making comparisons between adjacent elements. If the array meets the conditions for either or both of these definitions, it is considered monotonic. The solutions provided have a linear time complexity and a constant space complexity making them efficient.
In the examples offered above, the logic remains mostly similar across Python, Java, JavaScript, C++ and C#. All the codes initialize two boolean variables as true to keep track of whether the array is increasing or decreasing and depending on these two variables, the final verdict whether the array is monotonic or not is decided. This problem can serve as a great example of array traversal while handling two scenarios simultaneously, something you often face while tackling algorithmic problems.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.