Monotonic Array - Solution & Explanation

Problem Overview: You are given an integer array and must determine whether the sequence is monotonic. A monotonic array is either entirely non‑decreasing or entirely non‑increasing. Equal adjacent values are allowed, but the direction must never switch.

Approach 1: Two Separate Passes for Increasing and Decreasing (O(n) time, O(1) space)

The straightforward strategy checks both possible monotonic directions independently. First iterate through the array and verify the non‑decreasing condition: nums[i] >= nums[i-1] for every element. If any pair violates this rule, the array is not non‑decreasing. Then perform a second pass checking the non‑increasing condition nums[i] <= nums[i-1]. If either pass succeeds, the array is monotonic.

This approach keeps the logic extremely simple. Each pass performs a linear scan, comparing adjacent elements. No additional data structures are required, so space complexity stays constant. The trade‑off is that you potentially traverse the array twice, although the asymptotic complexity remains O(n). When clarity matters more than micro‑optimizations, this version is often preferred.

Approach 2: Single Pass Check for Monotonic Nature (O(n) time, O(1) space)

A more efficient implementation determines the direction during a single traversal. Track two boolean flags: one representing whether the sequence can still be non‑decreasing and another for non‑increasing. While iterating through adjacent elements, update these flags whenever a violation occurs. For example, if nums[i] < nums[i-1], the array cannot be non‑decreasing; if nums[i] > nums[i-1], it cannot be non‑increasing.

Once both flags become false, you can immediately stop because the array has already switched direction. If at least one flag survives the scan, the sequence is monotonic. This method still performs simple adjacent comparisons but reduces the logic to a single pass over the data. Time complexity remains O(n) with constant O(1) auxiliary space.

This pattern appears frequently in array traversal problems where the property of interest depends only on neighboring elements. It resembles techniques used in two pointers and simple greedy validations where you maintain state while scanning.

Recommended for interviews: The single‑pass flag approach is typically what interviewers expect. It demonstrates that you can detect monotonic direction dynamically while scanning the array once. The two‑pass method still shows solid understanding and may be easier to reason about, but the single‑pass check communicates stronger algorithmic intuition and attention to efficiency.