# LeetCode 896: Monotonic Array

## Problem Restatement

We are given an integer array `nums`.

An array is monotonic if it is either:

| Type | Condition |
|---|---|
| Monotone increasing | For all `i <= j`, `nums[i] <= nums[j]` |
| Monotone decreasing | For all `i <= j`, `nums[i] >= nums[j]` |

Return `true` if `nums` is monotonic. Otherwise, return `false`.

The array may contain equal adjacent values. Equal values do not break monotonicity. LeetCode gives examples such as `[1,2,2,3]` and `[6,5,4,4]` returning `true`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `nums`, an integer array |
| Output | `true` if the array is monotonic |
| Increasing rule | Values never decrease |
| Decreasing rule | Values never increase |
| Equal adjacent values | Allowed |

Function shape:

```python
def isMonotonic(self, nums: list[int]) -> bool:
    ...
```

## Examples

Example 1:

```text
Input: nums = [1,2,2,3]
Output: true
```

The array never decreases:

```text
1 <= 2 <= 2 <= 3
```

So it is monotone increasing.

Example 2:

```text
Input: nums = [6,5,4,4]
Output: true
```

The array never increases:

```text
6 >= 5 >= 4 >= 4
```

So it is monotone decreasing.

Example 3:

```text
Input: nums = [1,3,2]
Output: false
```

The array first increases:

```text
1 < 3
```

Then decreases:

```text
3 > 2
```

So it is neither monotone increasing nor monotone decreasing.

## First Thought: Check All Pairs

The definition says:

```text
for all i <= j
```

So a direct idea is to compare every pair of indices.

For monotone increasing, check:

```python
nums[i] <= nums[j]
```

for every `i <= j`.

For monotone decreasing, check:

```python
nums[i] >= nums[j]
```

for every `i <= j`.

This works, but it does unnecessary work.

If every adjacent pair is ordered correctly, then the whole array is ordered correctly by transitivity.

So we only need to compare neighboring elements.

## Key Insight

A monotonic array has at most one direction.

While scanning adjacent pairs:

| Pair relation | Meaning |
|---|---|
| `nums[i - 1] < nums[i]` | We have seen an increasing step |
| `nums[i - 1] > nums[i]` | We have seen a decreasing step |
| `nums[i - 1] == nums[i]` | No direction change |

If we ever see both an increasing step and a decreasing step, the array is not monotonic.

Equal values do not matter because they satisfy both monotone increasing and monotone decreasing conditions.

## Algorithm

Initialize two flags:

```python
seen_increase = False
seen_decrease = False
```

Scan the array from index `1` to the end.

For each adjacent pair:

1. If the previous value is smaller, set `seen_increase = True`.
2. If the previous value is larger, set `seen_decrease = True`.
3. If both flags are true, return `False`.

If the scan finishes, return `True`.

## Walkthrough

Use:

```text
nums = [1, 3, 2]
```

Start:

| Flag | Value |
|---|---|
| `seen_increase` | `False` |
| `seen_decrease` | `False` |

Compare adjacent pairs:

| Pair | Relation | Flags |
|---|---|---|
| `1, 3` | Increase | `seen_increase = True` |
| `3, 2` | Decrease | `seen_decrease = True` |

Now both flags are true.

So the array is not monotonic.

Return:

```python
False
```

Use:

```text
nums = [6, 5, 4, 4]
```

Compare adjacent pairs:

| Pair | Relation | Flags |
|---|---|---|
| `6, 5` | Decrease | `seen_decrease = True` |
| `5, 4` | Decrease | `seen_decrease = True` |
| `4, 4` | Equal | no change |

We saw only decreasing steps, so the array is monotonic.

Return:

```python
True
```

## Correctness

The algorithm returns `False` only when it has seen at least one increasing adjacent pair and at least one decreasing adjacent pair.

If both types of adjacent steps exist, the array cannot be monotone increasing because a decreasing adjacent pair violates `nums[i - 1] <= nums[i]`. It also cannot be monotone decreasing because an increasing adjacent pair violates `nums[i - 1] >= nums[i]`. Therefore, returning `False` is correct.

If the algorithm finishes without seeing both types of steps, then one of the following is true:

1. It saw only increasing steps and equal steps.
2. It saw only decreasing steps and equal steps.
3. It saw only equal steps.

In the first case, every adjacent pair satisfies `nums[i - 1] <= nums[i]`, so the array is monotone increasing.

In the second case, every adjacent pair satisfies `nums[i - 1] >= nums[i]`, so the array is monotone decreasing.

In the third case, all values are equal, so the array is both monotone increasing and monotone decreasing.

Thus, returning `True` is correct.

## Complexity

Let:

```text
n = len(nums)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan adjacent pairs once |
| Space | `O(1)` | We store only two boolean flags |

## Implementation

```python
class Solution:
    def isMonotonic(self, nums: list[int]) -> bool:
        seen_increase = False
        seen_decrease = False

        for i in range(1, len(nums)):
            if nums[i - 1] < nums[i]:
                seen_increase = True
            elif nums[i - 1] > nums[i]:
                seen_decrease = True

            if seen_increase and seen_decrease:
                return False

        return True
```

## Code Explanation

We track whether the array has gone up or down:

```python
seen_increase = False
seen_decrease = False
```

Then we scan adjacent pairs:

```python
for i in range(1, len(nums)):
```

If the current value is larger than the previous value, we have seen an increasing step:

```python
if nums[i - 1] < nums[i]:
    seen_increase = True
```

If the current value is smaller than the previous value, we have seen a decreasing step:

```python
elif nums[i - 1] > nums[i]:
    seen_decrease = True
```

If both directions appear, the array cannot be monotonic:

```python
if seen_increase and seen_decrease:
    return False
```

If the loop finishes without conflict, the array is monotonic:

```python
return True
```

## Alternative Implementation

We can also check both monotonic directions directly:

```python
class Solution:
    def isMonotonic(self, nums: list[int]) -> bool:
        increasing = True
        decreasing = True

        for i in range(1, len(nums)):
            if nums[i - 1] > nums[i]:
                increasing = False

            if nums[i - 1] < nums[i]:
                decreasing = False

        return increasing or decreasing
```

This version is also `O(n)` time and `O(1)` space.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.isMonotonic([1, 2, 2, 3]) is True
    assert s.isMonotonic([6, 5, 4, 4]) is True
    assert s.isMonotonic([1, 3, 2]) is False
    assert s.isMonotonic([1]) is True
    assert s.isMonotonic([1, 1, 1]) is True
    assert s.isMonotonic([1, 2, 3, 2]) is False
    assert s.isMonotonic([3, 2, 2, 1]) is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1,2,2,3]` | Non-decreasing with equal values |
| `[6,5,4,4]` | Non-increasing with equal values |
| `[1,3,2]` | Increase then decrease |
| `[1]` | Single element is monotonic |
| `[1,1,1]` | All equal values |
| `[1,2,3,2]` | Late direction change |
| `[3,2,2,1]` | Decreasing with equal middle values |