# Monotonic Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/monotonic-array)
Canonical: https://scaleengineer.com/dsa/problems/monotonic-array
**Data structures:** Array
**Companies:** [Ozon](https://scaleengineer.com/companies/ozon)
---
## Problem
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`

# Approaches
## Two-Pass Iteration
This straightforward approach checks for the two conditions of monotonicity (non-decreasing and non-increasing) in two separate iterations. It first scans the entire array to see if it's non-decreasing. If not, it performs a second scan to check if it's non-increasing. The array is monotonic if it satisfies at least one of these conditions.
**Time:** O(N), where N is the number of elements in the array. In the worst-case scenario (e.g., for an array like `[1, 5, 2]`), we might traverse the array almost twice. For a monotonic array, we will traverse it fully once and then partially or fully a second time. · **Space:** O(1), as no extra space proportional to the input size is used. The space for helper function call stacks is constant.
**Pros:** The logic is very clear and easy to follow, as it separates the two conditions for monotonicity.; Easy to implement and debug.
**Cons:** It is less efficient than a single-pass solution because it might iterate over the array twice.
### Explanation
The core idea is to break the problem down into two subproblems: checking for a non-decreasing sequence and checking for a non-increasing sequence.
We can implement two helper functions, `isNonDecreasing` and `isNonIncreasing`.
The `isNonDecreasing` function iterates through the array from the first element to the second-to-last. If it ever finds `nums[i] > nums[i+1]`, it immediately knows the array is not non-decreasing and returns `false`. If the loop completes without finding such a pair, the array is non-decreasing, and it returns `true`.
The `isNonIncreasing` function works similarly, but it checks for the condition `nums[i] < nums[i+1]`.
The main function `isMonotonic` then simply calls both helper functions and returns `true` if either of them returns `true`.
```java
class Solution {
    public boolean isMonotonic(int[] nums) {
        return isNonDecreasing(nums) || isNonIncreasing(nums);
    }

    private boolean isNonDecreasing(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i+1]) {
                return false;
            }
        }
        return true;
    }

    private boolean isNonIncreasing(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] < nums[i+1]) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Check if the array is non-decreasing by iterating from `i = 0` to `n-2`.
- In the loop, if `nums[i] > nums[i+1]`, the condition is violated, so it's not non-decreasing.
- If the first check passes, the array is monotonic (non-decreasing), so return `true`.
- If the first check fails, check if the array is non-increasing by iterating from `i = 0` to `n-2`.
- In this second loop, if `nums[i] < nums[i+1]`, the condition is violated.
- The final result is `true` if the array is non-decreasing OR non-increasing, and `false` otherwise.

## Single-Pass Iteration
This optimized approach determines if an array is monotonic in a single pass. It maintains two boolean flags, one to track if the array could be non-decreasing and another to track if it could be non-increasing. By updating these flags while iterating through the array just once, we can efficiently arrive at the solution.
**Time:** O(N), where N is the number of elements in the array. We only need to iterate through the array once. · **Space:** O(1). We only use a constant amount of extra space for the two boolean flags.
**Pros:** This is the most efficient approach in terms of time complexity, as it guarantees a single pass.; It's optimal as we must examine each element at least once in the worst case.
**Cons:** Slightly more complex than the two-pass approach as it combines two logical checks in one loop.
### Explanation
We can improve upon the two-pass approach by combining the checks into a single loop. We initialize two boolean variables, `increasing` and `decreasing`, to `true`. We then iterate through the array from the first element to the second-to-last.
In each step, we compare `nums[i]` with `nums[i+1]`:
- If we find that `nums[i] > nums[i+1]`, we know the array cannot be non-decreasing, so we set the `increasing` flag to `false`.
- If we find that `nums[i] < nums[i+1]`, we know the array cannot be non-increasing, so we set the `decreasing` flag to `false`.
If at any point both flags become `false`, we could even break out of the loop early, but it's not necessary for correctness. After the loop completes, the array is monotonic if either the `increasing` flag or the `decreasing` flag is still `true`.
```java
class Solution {
    public boolean isMonotonic(int[] nums) {
        if (nums.length <= 1) {
            return true;
        }
        
        boolean increasing = true;
        boolean decreasing = true;
        
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i+1]) {
                increasing = false;
            }
            if (nums[i] < nums[i+1]) {
                decreasing = false;
            }
        }
        
        return increasing || decreasing;
    }
}
```
### Algorithm
- Initialize two boolean flags, `increasing = true` and `decreasing = true`.
- Iterate through the array from `i = 0` to `n-2`.
- In each iteration, compare `nums[i]` with `nums[i+1]`.
- If `nums[i] > nums[i+1]`, set `increasing = false`.
- If `nums[i] < nums[i+1]`, set `decreasing = false`.
- After the loop, return `increasing || decreasing`.

# Solutions
### Java

```java
class Solution { public boolean isMonotonic ( int [] nums ) { boolean asc = false , desc = false ; for ( int i = 1 ; i < nums . length ; ++ i ) { if ( nums [ i - 1 ] < nums [ i ]) { asc = true ; } else if ( nums [ i - 1 ] > nums [ i ]) { desc = true ; } if ( asc && desc ) { return false ; } } return true ; } }
```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {boolean} */ var isMonotonic = function (
  nums,
) {
  let [asc, desc] = [false, false];
  for (let i = 1; i < nums.length; ++i) {
    if (nums[i - 1] < nums[i]) {
      asc = true;
    } else if (nums[i - 1] > nums[i]) {
      desc = true;
    }
    if (asc && desc) {
      return false;
    }
  }
  return true;
};

```

### CPP

```cpp
class Solution { public: bool isMonotonic ( vector < int >& nums ) { bool asc = false , desc = false ; for ( int i = 1 ; i < nums . size (); ++ i ) { if ( nums [ i - 1 ] < nums [ i ]) { asc = true ; } else if ( nums [ i - 1 ] > nums [ i ]) { desc = true ; } if ( asc && desc ) { return false ; } } return true ; } };
```

### Python

```python
class Solution : def isMonotonic ( self , nums : List [ int ]) -> bool : asc = all ( a <= b for a , b in pairwise ( nums )) desc = all ( a >= b for a , b in pairwise ( nums )) return asc or desc
```