Skip to main content

TIL: Checking Monotonic Lists (Ascending/Descending)

A common interview question: determine if a list is monotonic (entirely non-increasing or non-decreasing). This tests understanding of array traversal and boolean logic.

The Problem / Context​

When you need this:

  • Interview questions (LeetCode 896)
  • Validating sorted data
  • Checking trend direction in time series
  • Pre-condition checks before binary search

Definition: A list is monotonic if it's either:

  • Non-decreasing: each element ≥ previous ([1, 2, 2, 3])
  • Non-increasing: each element ≤ previous ([3, 2, 2, 1])

Solution / How It Works​

One-Pass Solution (Interview Favorite)​

def is_monotonic(nums: list[int]) -> bool:
    """
    Check if list is monotonically increasing OR decreasing.

    Time: O(n) - single pass through array
    Space: O(1) - only two boolean flags
    """
    increasing = decreasing = True

    for i in range(len(nums) - 1):
        # If we find a decrease, it's not increasing
        if nums[i] > nums[i + 1]:
            increasing = False
        # If we find an increase, it's not decreasing
        if nums[i] < nums[i + 1]:
            decreasing = False

    # Monotonic if EITHER direction holds
    return increasing or decreasing

Why this works: We track both possibilities simultaneously. A list can be monotonic in either direction, so we check both and return True if either holds.

Simple Approach (More Readable)​

def is_monotonic(nums: list[int]) -> bool:
    """Using all() for clarity - two passes but very readable."""
    increasing = all(nums[i] <= nums[i+1] for i in range(len(nums)-1))
    decreasing = all(nums[i] >= nums[i+1] for i in range(len(nums)-1))
    return increasing or decreasing

Common Patterns​

Pythonic with zip​

def is_monotonic(nums: list[int]) -> bool:
    """Using zip to pair adjacent elements."""
    return (all(a <= b for a, b in zip(nums, nums[1:])) or
            all(a >= b for a, b in zip(nums, nums[1:])))

Separate Helper Functions​

def is_ascending(nums: list[int]) -> bool:
    """Strictly ascending: each element > previous."""
    return all(nums[i] < nums[i+1] for i in range(len(nums)-1))

def is_descending(nums: list[int]) -> bool:
    """Strictly descending: each element < previous."""
    return all(nums[i] > nums[i+1] for i in range(len(nums)-1))

def is_non_decreasing(nums: list[int]) -> bool:
    """Non-decreasing: allows equal adjacent elements."""
    return all(nums[i] <= nums[i+1] for i in range(len(nums)-1))

def is_non_increasing(nums: list[int]) -> bool:
    """Non-increasing: allows equal adjacent elements."""
    return all(nums[i] >= nums[i+1] for i in range(len(nums)-1))

Early Exit Optimization​

def is_monotonic(nums: list[int]) -> bool:
    """Exit early once we know neither direction works."""
    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
        # Early exit: if neither holds, no point continuing
        if not increasing and not decreasing:
            return False

    return True

Edge Cases / Gotchas​

# Empty list and single element are monotonic
assert is_monotonic([]) == True
assert is_monotonic([1]) == True

# All same elements - BOTH increasing AND decreasing
assert is_monotonic([5, 5, 5]) == True

# Standard cases
assert is_monotonic([1, 2, 3, 4]) == True   # Increasing
assert is_monotonic([4, 3, 2, 1]) == True   # Decreasing
assert is_monotonic([1, 3, 2, 4]) == False  # Neither

Interview clarification questions:

  1. Strict or non-strict? (< vs <=)
  2. How to handle empty list?
  3. How to handle single element?

Key Takeaway​

  • Strictly monotonic: no equal adjacent elements (< or >)
  • Non-strictly monotonic: equals allowed (<= or >=)
  • One-pass with two boolean flags is optimal: O(n) time, O(1) space
  • Always clarify strict vs non-strict with interviewer

References​