Problem Description

You need to determine if an array is monotonic. An array is considered monotonic if it follows one of these two patterns:

1. Monotone Increasing: Every element is less than or equal to the next element. In other words, for any two indices i and j where i <= j, we have nums[i] <= nums[j].

2. Monotone Decreasing: Every element is greater than or equal to the next element. In other words, for any two indices i and j where i <= j, we have nums[i] >= nums[j].

Given an integer array nums, you should return true if the array is either monotone increasing or monotone decreasing. Return false if the array doesn't follow either pattern.

For example:

• [1, 2, 2, 3] is monotonic (monotone increasing)
• [6, 5, 4, 4] is monotonic (monotone decreasing)
• [1, 3, 2] is not monotonic (neither consistently increasing nor decreasing)

The solution checks both conditions by examining consecutive pairs of elements. It uses pairwise(nums) to get all adjacent pairs (a, b) and verifies if all pairs satisfy the increasing condition (a <= b) or all pairs satisfy the decreasing condition (a >= b). If either condition is fully satisfied, the array is monotonic.

Intuition

The key insight is that a monotonic array must be entirely non-decreasing or entirely non-increasing. We can't have some parts going up and other parts going down.

Think about what makes an array monotonic - it needs to maintain a consistent direction throughout. If we examine each consecutive pair of elements, they should all follow the same pattern:

• For increasing: every pair (a, b) should satisfy a <= b
• For decreasing: every pair (a, b) should satisfy a >= b

Instead of trying to detect which type of monotonic pattern we have first and then checking it, we can simply check both patterns simultaneously. Why? Because if an array is monotonic, it will completely satisfy at least one of these conditions.

The elegant approach is to:

1. Check if all consecutive pairs are non-decreasing (a <= b for every pair)
2. Check if all consecutive pairs are non-increasing (a >= b for every pair)
3. If either check passes completely, the array is monotonic

This works because:

• If the array is monotone increasing, the first check will return True
• If the array is monotone decreasing, the second check will return True
• If the array is neither (has mixed increases and decreases), both checks will return False

Using pairwise(nums) gives us a clean way to iterate through consecutive pairs (nums[i], nums[i+1]), and the all() function ensures that every single pair meets the condition. The final or operation captures the fact that we only need one of the two patterns to be satisfied.

Solution Approach

The implementation uses a single traversal approach to determine if the array is monotonic. Here's how the solution works:

1. Check for Monotone Increasing Pattern:

   • Use pairwise(nums) to generate consecutive pairs from the array
   • For each pair (a, b), check if a <= b
   • The all() function returns True only if every single pair satisfies this condition
   • Store this result in the variable asc

2. Check for Monotone Decreasing Pattern:

   • Similarly, use pairwise(nums) to generate consecutive pairs
   • For each pair (a, b), check if a >= b
   • The all() function returns True only if every single pair satisfies this condition
   • Store this result in the variable desc

3. Determine Final Result:

   • Return asc or desc
   • This returns True if the array is either monotone increasing OR monotone decreasing
   • Returns False if neither condition is satisfied (meaning the array has both increasing and decreasing segments)

Key Implementation Details:

• pairwise(nums) creates an iterator of consecutive pairs: if nums = [1, 2, 3], it yields (1, 2) and (2, 3)
• The generator expressions (a <= b for a, b in pairwise(nums)) and (a >= b for a, b in pairwise(nums)) are memory-efficient as they don't create intermediate lists
• The all() function short-circuits - it stops checking as soon as it encounters a False value, making it efficient

Time Complexity: O(n) where n is the length of the array, as we traverse the array at most twice (once for each check)

Space Complexity: O(1) as we only use constant extra space for the boolean variables

Example Walkthrough

Let's walk through the solution with the array [3, 5, 5, 2]:

Step 1: Check for Monotone Increasing

• Generate consecutive pairs using pairwise([3, 5, 5, 2]):
  • Pair 1: (3, 5) → Check 3 <= 5 → True
  • Pair 2: (5, 5) → Check 5 <= 5 → True
  • Pair 3: (5, 2) → Check 5 <= 2 → False
• Since not all pairs satisfy a <= b, asc = False

Step 2: Check for Monotone Decreasing

• Generate consecutive pairs using pairwise([3, 5, 5, 2]):
  • Pair 1: (3, 5) → Check 3 >= 5 → False
  • The all() function short-circuits here and returns False
• Since the first pair already fails, desc = False

Step 3: Determine Final Result

• Return asc or desc → False or False → False
• The array is not monotonic because it goes up from 3 to 5, then down from 5 to 2

Now let's trace through a monotonic example with [4, 3, 3, 1]:

Step 1: Check for Monotone Increasing

• Generate consecutive pairs:
  • Pair 1: (4, 3) → Check 4 <= 3 → False
  • The all() function short-circuits and returns False
• Result: asc = False

Step 2: Check for Monotone Decreasing

• Generate consecutive pairs:
  • Pair 1: (4, 3) → Check 4 >= 3 → True
  • Pair 2: (3, 3) → Check 3 >= 3 → True
  • Pair 3: (3, 1) → Check 3 >= 1 → True
• All pairs satisfy a >= b, so desc = True

Step 3: Determine Final Result

• Return asc or desc → False or True → True
• The array is monotonic (specifically, monotone decreasing)

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because:

• The pairwise(nums) function creates pairs of consecutive elements, yielding n-1 pairs
• The all() function with generator expression iterates through these pairs
• In the worst case, both asc and desc checks need to examine all n-1 pairs
• Even though we have two all() calls, they execute sequentially, giving us O(n) + O(n) = O(n)

The space complexity is O(1). This is because:

• The pairwise() function returns an iterator, not a list, so it doesn't create additional storage proportional to the input
• The generator expressions (a <= b for a, b in pairwise(nums)) and (a >= b for a, b in pairwise(nums)) are evaluated lazily and don't store all comparisons in memory
• Only constant extra space is used for the boolean variables asc and desc

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Python Version Compatibility Issue

The pairwise function is only available in Python 3.10+. If you're using an older version of Python or submitting to a platform that doesn't support Python 3.10+, the code will fail with an ImportError.

Solution: Implement your own pairwise logic or use alternative approaches:

class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        # Manual pairwise implementation for compatibility
        is_ascending = all(nums[i] <= nums[i+1] for i in range(len(nums)-1))
        is_descending = all(nums[i] >= nums[i+1] for i in range(len(nums)-1))
        return is_ascending or is_descending

2. Inefficient Double Traversal

The current solution potentially traverses the array twice - once to check for ascending and once for descending. In the worst case where the array is monotonic, both checks run completely.

Optimized Solution: Use a single pass to determine monotonicity by tracking both conditions simultaneously:

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

3. Edge Case: Single Element or Empty Arrays

While the current solution handles these correctly (returns True for arrays with 0 or 1 element), it's not immediately obvious why this works.

Clarification:

• pairwise([]) produces no pairs, so all() returns True (vacuous truth)
• pairwise([5]) produces no pairs, so all() returns True
• Both checks return True, making the array monotonic

Consider adding an explicit check for clarity:

class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        if len(nums) <= 1:
            return True
      
        from itertools import pairwise
        is_ascending = all(a <= b for a, b in pairwise(nums))
        is_descending = all(a >= b for a, b in pairwise(nums))
        return is_ascending or is_descending

4. Misunderstanding Monotonic Definition

A common misconception is thinking that equal consecutive elements break monotonicity. Remember that:

• [1, 2, 2, 3] is monotonic (non-decreasing)
• [3, 2, 2, 1] is monotonic (non-increasing)
• The conditions use <= and >=, not < and >

5. Early Termination Opportunity Missed

When checking both conditions separately, we might miss the opportunity to terminate early when we detect the array is neither increasing nor decreasing.

Early Termination Solution:

class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        if len(nums) <= 2:
            return True
      
        # Determine initial direction from first different pair
        direction = 0  # 0: unknown, 1: increasing, -1: decreasing
      
        for i in range(len(nums) - 1):
            if nums[i] < nums[i + 1]:
                if direction == -1:  # Was decreasing, now increasing
                    return False
                direction = 1
            elif nums[i] > nums[i + 1]:
                if direction == 1:  # Was increasing, now decreasing
                    return False
                direction = -1
      
        return True