Monotonic Array LeetCode 896 Guide

LeetCode 896 Monotonic Array asks you to determine whether a given integer array is monotonic. An array is monotonic if it is entirely non-increasing or entirely non-decreasing.

The two cases are: monotone increasing means every a[i] <= a[i+1] for all valid i, and monotone decreasing means every a[i] >= a[i+1] for all valid i. Equal adjacent elements are fine in both directions — the constraint is non-strict.

Return true if the array is monotone in either direction. Return false if the array changes direction at any point — increasing for some pairs and decreasing for others.

The cleanest single-pass solution uses two boolean flags: isIncreasing and isDecreasing. Both start as true — every array is assumed to be both until proven otherwise. As you scan adjacent pairs, evidence against each direction kills its flag.

For each adjacent pair (a[i], a[i+1]): if a[i] > a[i+1], the array cannot be increasing, so set isIncreasing = false. If a[i] < a[i+1], the array cannot be decreasing, so set isDecreasing = false. After the loop, return isIncreasing OR isDecreasing.

This is elegant because both possibilities are tracked simultaneously. If the array is strictly increasing, isDecreasing gets killed early. If the array is strictly decreasing, isIncreasing gets killed. A flat array never kills either flag and returns true for both.

The algorithm is a single loop from index 0 to n-2, comparing each element to the next. The two flag updates are independent — both checks happen for every pair, not in an if-else chain. This ensures both flags accurately reflect the full array.

Early termination is possible as an optimization: if both flags are already false, no pair can revive either one. You can break out of the loop as soon as both flags die. In practice the simpler no-break version reads more clearly.

The return statement is simply isIncreasing or isDecreasing. If either direction is still valid after seeing all pairs, the array is monotonic. If both were killed, the array changes direction — return false.

An alternative approach uses two separate passes. Pass 1 checks whether all adjacent pairs are non-decreasing (a[i] <= a[i+1]). Pass 2 checks whether all adjacent pairs are non-increasing (a[i] >= a[i+1]). Return true if either pass succeeds.

This two-pass version is arguably more readable because each pass has a single, clear purpose. It avoids the cognitive overhead of tracking two flags at once. The tradeoff is that it literally traverses the array twice, doing up to 2(n-1) comparisons instead of n-1.

For most inputs the two-pass version terminates early on the first mismatch of each pass, so the practical difference is small. Both approaches are O(n) time and O(1) space. The choice between them is purely stylistic.

Example 1 — [1, 2, 2, 3]: Pairs are (1,2), (2,2), (2,3). No pair has a[i] > a[i+1], so isIncreasing stays true. Pair (1,2) has a[i] < a[i+1], so isDecreasing becomes false. Final: isIncreasing=true, isDecreasing=false. Return true — array is monotone increasing.

Example 2 — [6, 5, 4, 4]: Pairs are (6,5), (5,4), (4,4). Pair (6,5) has a[i] > a[i+1], so isIncreasing becomes false. No pair has a[i] < a[i+1], so isDecreasing stays true. Final: isIncreasing=false, isDecreasing=true. Return true — array is monotone decreasing.

Example 3 — [1, 3, 2]: Pairs are (1,3) and (3,2). Pair (1,3) kills isDecreasing. Pair (3,2) kills isIncreasing. Final: both false. Return false — array is not monotonic.

Python two-flag implementation: initialize inc = dec = True, loop with for i in range(len(nums)-1), set inc = False if nums[i] > nums[i+1], set dec = False if nums[i] < nums[i+1], return inc or dec. Six lines total. Python one-liner: return all(a<=b for a,b in zip(nums,nums[1:])) or all(a>=b for a,b in zip(nums,nums[1:])).

Java implementation: boolean isInc = true, isDec = true; for loop from i=0 to nums.length-2; if nums[i] > nums[i+1] set isInc = false; if nums[i] < nums[i+1] set isDec = false; return isInc || isDec. O(n) time, O(1) space. No extra arrays, no sorting.

Both use the same structure: two flags, one loop, one return. The flags are updated independently on each iteration — not in an if-else chain — so both directions are always tracked accurately regardless of element order.

Monotonic Array belongs to the family of single-pass array property check problems. Increasing Triplet Subsequence (LeetCode 334) asks whether any three indices exist with strictly increasing values — it uses a similar two-variable tracking approach to avoid O(n^3) brute force.

Is Subsequence (LeetCode 392) checks a structural property of two arrays in one scan using two pointers. Sort Colors (LeetCode 75) verifies or rearranges an array based on its element distribution in one or two passes. All these problems reward recognizing what information you truly need to track across a single traversal.

For interview preparation, the monotonic array problem is a warm-up that reinforces the habit of asking: what is the minimal state I need to carry through the loop? Two booleans — isIncreasing and isDecreasing — are all that is needed here. No counts, no indices, no stack.