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.

1. We could start by assuming the array is both non-increasing and non-decreasing.
2. Then, for every pair of adjacent elements, we check if they are in non-decreasing order or non-increasing order.
3. If they are not in non-decreasing order, we discard the possibility that the entire array could be non-decreasing and vice versa.
4. 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.