896. Monotonic Array - Explanation

Problem Link

1. Two Pass

Intuition

An array is monotonic if it is entirely non-decreasing or entirely non-increasing. We can check each condition separately. First, scan to see if every element is greater than or equal to the previous one. If this holds, the array is monotonically increasing. If not, scan again to check if every element is less than or equal to the previous one. If either condition is satisfied, the array is monotonic.

Algorithm

1. Assume the array is increasing. Iterate through and check if nums[i] < nums[i - 1] for any i. If found, the array is not increasing.
2. If the array passed the increasing check, return true.
3. Otherwise, assume the array is decreasing. Iterate through and check if nums[i] > nums[i - 1] for any i. If found, the array is not decreasing.
4. Return whether the array passed the decreasing check.

class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        n = len(nums)
        increase = True
        for i in range(1, n):
            if nums[i] < nums[i - 1]:
                increase = False
                break

        if increase:
            return True

        decrease = True
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                decrease = False
                break
        return decrease

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$

---

2. One Pass - I

Intuition

We can determine the expected direction by comparing the first and last elements. If the first element is less than or equal to the last, the array should be non-decreasing. Otherwise, it should be non-increasing. With the direction determined upfront, a single pass can verify whether all consecutive pairs follow the expected pattern.

Algorithm

1. Compare nums[0] and nums[n - 1] to determine the expected direction.
2. If nums[0] <= nums[n - 1], the array should be non-decreasing:
   • Iterate through and return false if any nums[i] < nums[i - 1].
3. Otherwise, the array should be non-increasing:
   • Iterate through and return false if any nums[i] > nums[i - 1].
4. If no violations are found, return true.

class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        n = len(nums)
        if nums[0] <= nums[-1]:
            for i in range(1, n):
                if nums[i] < nums[i - 1]:
                    return False
            return True
        else:
            for i in range(1, n):
                if nums[i] > nums[i - 1]:
                    return False
            return True

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$

---

3. One Pass - II

Intuition

Rather than deciding the direction upfront, we can track both possibilities simultaneously. We maintain two flags: one for whether the array could still be non-decreasing, and one for whether it could still be non-increasing. As we scan, any violation disqualifies that direction. At the end, if at least one flag remains true, the array is monotonic.

Algorithm

1. Initialize two boolean flags: increase = true and decrease = true.
2. Iterate through consecutive pairs (nums[i], nums[i + 1]):
   • If nums[i] > nums[i + 1], set increase = false.
   • If nums[i] < nums[i + 1], set decrease = false.
3. Return increase || decrease.

class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        increase, decrease = True, True

        for i in range(len(nums) - 1):
            if not (nums[i] <= nums[i + 1]):
                increase = False
            if not (nums[i] >= nums[i + 1]):
                decrease = False
        return increase or decrease

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$

Common Pitfalls

Using Strict Inequality Instead of Non-Strict

A monotonic array allows equal consecutive elements (non-decreasing or non-increasing). Using strict comparisons like nums[i] > nums[i-1] instead of nums[i] >= nums[i-1] incorrectly rejects arrays like [1, 2, 2, 3] as non-monotonic. The condition should check for <= (non-decreasing) or >= (non-increasing) to properly handle equal adjacent values.

Checking Only One Direction

Arrays that are constant (all elements equal) are both non-decreasing and non-increasing. Returning false early when detecting a violation in one direction without checking the other leads to incorrect results. The array [5, 5, 5] should return true, but checking only for strictly increasing or strictly decreasing patterns would fail this case.