Monotonic Array

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.

Examples:

1. nums = [1,2,2,3] Output: true
2. nums = [6,5,4,4] Output: true
3. nums = [1,3,2] Output: false

Can you write code to efficiently determine if a given array is monotonic, considering various edge cases and optimizing for time and space complexity? Please provide a detailed explanation of your approach, including the time and space complexity analysis.

## Monotonic Array

### Problem Description

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`, determine whether the array is monotonic.

### Naive Solution

The naive solution involves checking both increasing and decreasing conditions separately. We iterate through the array twice, once to check if it's monotone increasing and another time to check if it's monotone decreasing. If either condition is met, we return `true`; otherwise, we return `false`.

```python
def isMonotonicNaive(nums):
    increasing = True
    decreasing = True
    
    for i in range(1, len(nums)):
        if nums[i] < nums[i-1]:
            increasing = False
        if nums[i] > nums[i-1]:
            decreasing = False
            
    return increasing or decreasing

Optimal Solution

The optimal solution involves a single pass through the array. We maintain two boolean flags, one for increasing and one for decreasing. During the iteration, we update these flags based on the relationship between adjacent elements. If at any point, the array violates both increasing and decreasing conditions, we return false. Otherwise, if we reach the end of the array, it means the array is either monotone increasing or monotone decreasing, so we return true.

def isMonotonic(nums):
    increasing = True
    decreasing = True
    
    for i in range(1, len(nums)):
        if nums[i] < nums[i-1]:
            increasing = False
        if nums[i] > nums[i-1]:
            decreasing = False
            
    return increasing or decreasing

Big(O) Run-time Analysis

The time complexity of the optimal solution is O(n), where n is the length of the input array nums. This is because we iterate through the array only once.

Big(O) Space Usage Analysis

The space complexity is O(1) because we use only a constant amount of extra space to store the boolean flags increasing and decreasing, regardless of the size of the input array.

Edge Cases

1. Empty Array: If the input array is empty, it can be considered both monotone increasing and monotone decreasing. The given solution works for this case because the loop will not execute, and both increasing and decreasing will remain True, thus returning True.
2. Single Element Array: If the array contains only one element, it is also considered monotonic. The solution handles this correctly for the same reason as the empty array case.
3. Array with Equal Elements: If the array contains all equal elements (e.g., [2, 2, 2, 2]), it is also considered monotonic. The solution handles this correctly because neither increasing nor decreasing will be set to False.
4. Large Input: For very large arrays, the solution remains efficient because it has a linear time complexity O(n) and constant space complexity O(1).