LeetCode 896: Monotonic Array

A clear explanation of checking whether an array is monotonic using one pass and direction flags.

leetcodearray

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:

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:

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:

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:

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:

False

Use:

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:

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)
Metric Value Why
Time O(n) We scan adjacent pairs once
Space O(1) We store only two boolean flags

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:

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