Monotonic Array

Tags

Monotonic Array

Category

Arrays

Difficulty

Medium

Problem Statement

Given an array of integers, determine whether the array is monotonic. An array is monotonic if its elements are entirely non-increasing or entirely non-decreasing.

Intuition

A monotonic array never changes direction. We can track two boolean flags — one for non-decreasing and one for non-increasing. As we scan adjacent pairs, any increase invalidates non-increasing, and any decrease invalidates non-decreasing. If at least one flag remains true by the end, the array is monotonic.

Approach

  1. Initialize two booleans: isNonDecreasing = true and isNonIncreasing = true.
  2. Iterate through the array from index 1 to the end:
    • If array[i] < array[i - 1], set isNonDecreasing = false.
    • If array[i] > array[i - 1], set isNonIncreasing = false.
  3. Return isNonDecreasing OR isNonIncreasing.

Pseudocode

function isMonotonic(array):
    isNonDecreasing = true
    isNonIncreasing = true

    for i from 1 to length(array) - 1:
        if array[i] < array[i - 1]:
            isNonDecreasing = false
        if array[i] > array[i - 1]:
            isNonIncreasing = false

    return isNonDecreasing or isNonIncreasing

Time & Space Complexity

  • Time: O(n) — single pass through the array.
  • Space: O(1) — only two boolean variables used.

Key Insights

  • An array of length 0 or 1 is trivially monotonic.
  • Equal adjacent elements are compatible with both non-decreasing and non-increasing, so they do not invalidate either flag.
  • You can short-circuit early if both flags become false, though the asymptotic complexity remains the same.

Edge Cases

  • Empty array or single-element array: monotonic by definition.
  • All elements are equal: both non-decreasing and non-increasing, so monotonic.
  • Array with exactly two elements: always monotonic.
  • Strictly increasing then a single decrease at the end: not monotonic.

Linked mentions