Monotonic Array

Difficulty: Easy | Acceptance: 62.30% | Paid: No Topics: 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
• Constraints
• Two Pass Check
• One Pass State Tracking

Examples

Example 1:

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

Example 2:

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

Example 3:

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

Constraints

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Two Pass Check

Intuition We can simply check if the array is sorted in non-decreasing order. If it is, we return true. If not, we check if it is sorted in non-increasing order. If either check passes, the array is monotonic.

Steps

• Iterate through the array to check if it is monotone increasing.
• If the check fails, iterate through the array to check if it is monotone decreasing.
• Return true if either check passes, otherwise return false.

class Solution:
    def isMonotonic(self, nums: list[int]) -> bool:
        def is_increasing():
            for i in range(len(nums) - 1):
                if nums[i] > nums[i + 1]:
                    return False
            return True

        def is_decreasing():
            for i in range(len(nums) - 1):
                if nums[i] < nums[i + 1]:
                    return False
            return True

        return is_increasing() or is_decreasing()

Complexity

• Time: O(N) - We may traverse the array twice in the worst case.
• Space: O(1) - We only use a constant amount of extra space.
• Notes: Simple to implement, but performs redundant checks if the array is monotonic (it always checks the first condition).

One Pass State Tracking

Intuition We can determine the monotonicity in a single pass. We maintain two boolean flags, increasing and decreasing. Initially, both are true. As we iterate, if we find a pair that violates the increasing property, we set increasing to false. Similarly, if we find a pair that violates the decreasing property, we set decreasing to false. If both flags become false at any point, the array cannot be monotonic.

Steps

• Initialize increasing = true and decreasing = true.
• Iterate through the array from index 1 to the end.
• If nums[i] > nums[i-1], the array cannot be decreasing, so set decreasing = false.
• If nums[i] < nums[i-1], the array cannot be increasing, so set increasing = false.
• If both increasing and decreasing are false, return false immediately.
• If the loop finishes, return true (at least one flag is still true).

class Solution:
    def isMonotonic(self, nums: list[int]) -> bool:
        inc = True
        dec = True
        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                dec = False
            if nums[i] < nums[i - 1]:
                inc = False
            if not inc and not dec:
                return False
        return True

Complexity

• Time: O(N) - We traverse the array at most once.
• Space: O(1) - We only use two boolean variables.
• Notes: This is the optimal solution as it minimizes the number of comparisons and allows for early exit.