LeetCode 896: Monotonic Array

Problem Restatement

We are given an integer array nums.

An array is monotonic if it is either:

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

Function shape:

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

Examples

Example 1:

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

The array never decreases:

1 <= 2 <= 2 <= 3

So it is monotone increasing.

Example 2:

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

The array never increases:

6 >= 5 >= 4 >= 4

So it is monotone decreasing.

Example 3:

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

The array first increases:

1 < 3

Then decreases:

3 > 2

So it is neither monotone increasing nor monotone decreasing.

First Thought: Check All Pairs

The definition says:

for all i <= j

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

For monotone increasing, check:

nums[i] <= nums[j]

for every i <= j.

For monotone decreasing, check:

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:

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:

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:

nums = [1, 3, 2]

Start:

Compare adjacent pairs:

Now both flags are true.

So the array is not monotonic.

Return:

False

Use:

nums = [6, 5, 4, 4]

Compare adjacent pairs:

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

Return:

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:

n = len(nums)

Implementation

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:

seen_increase = False
seen_decrease = False

Then we scan adjacent pairs:

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

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

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:

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

If both directions appear, the array cannot be monotonic:

if seen_increase and seen_decrease:
    return False

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

return True

Alternative Implementation

We can also check both monotonic directions directly:

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

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: