LeetCode 896 - Monotonic Array

LeetCode Problem 896

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

This problem asks us to determine whether a given array of integers is monotonic. An array is considered monotonic if it is entirely non-decreasing (monotone increasing) or entirely non-increasing (monotone decreasing). In simpler terms, as we traverse the array from left to right, the elements should either never decrease or never increase. The input is a single list of integers, and the output is a boolean value: true if the array is monotonic, false otherwise.

The constraints tell us the array length can be as large as 100,000 elements, and the integer values range between -100,000 and 100,000. This means any solution with quadratic time complexity, O(n²), would likely be too slow, while linear time, O(n), solutions are acceptable. The problem guarantees that the array has at least one element, so we do not need to handle an empty array case.

Important edge cases include arrays with only one element, arrays where all elements are equal, and arrays where the monotonicity switches once or multiple times.

Approaches

The brute-force approach would involve checking every pair of elements to determine if the array is increasing or decreasing. We could first assume it is increasing and check for violations, then assume it is decreasing and check again. This approach would work correctly but is inefficient because it potentially checks all element pairs multiple times.

The key insight for an optimal solution is that we only need a single pass through the array to track whether it is increasing or decreasing. We can maintain two boolean flags, one for increasing and one for decreasing. As we iterate, if we find any violation of increasing order, we set the increasing flag to false, and similarly for decreasing order. At the end, if either flag remains true, the array is monotonic.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks all pairs for monotonicity; correct but slow
Optimal	O(n)	O(1)	Single-pass check using two boolean flags for increasing/decreasing

Algorithm Walkthrough

1. Initialize two boolean variables, increasing and decreasing, and set both to True. These flags represent whether the array could still be monotone increasing or decreasing as we iterate.
2. Iterate through the array starting from the second element. For each element, compare it with the previous element.
3. If the current element is greater than the previous element, set decreasing to False because the array cannot be monotone decreasing.
4. If the current element is less than the previous element, set increasing to False because the array cannot be monotone increasing.
5. After finishing the iteration, if either increasing or decreasing is True, return True because the array is monotonic. Otherwise, return False.

Why it works: The algorithm maintains an invariant that the flags increasing and decreasing reflect whether a monotonic relationship has been violated at any point. If any violation occurs, the corresponding flag is turned off, and the array can only remain monotone if at least one flag stays true.

Python Solution

from typing import List

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

In this Python implementation, we start by assuming the array could be either increasing or decreasing. As we iterate through the array, we update the flags whenever we detect a violation of either type of monotonicity. At the end, returning increasing or decreasing correctly determines whether the array is monotonic.

Go Solution

func isMonotonic(nums []int) bool {
    increasing := true
    decreasing := true

    for i := 1; i < len(nums); i++ {
        if nums[i] > nums[i-1] {
            decreasing = false
        } else if nums[i] < nums[i-1] {
            increasing = false
        }
    }

    return increasing || decreasing
}

In Go, we handle slices similarly to Python lists. The for loop iterates over the indices, and we use the same boolean flag approach. Edge cases such as arrays of length 1 are automatically handled because the loop does not execute, leaving both flags true, which correctly returns true.

Worked Examples

Example 1: [1,2,2,3]

Step through each element comparison:

i	nums[i-1]	nums[i]	increasing	decreasing
1	1	2	True	False
2	2	2	True	False
3	2	3	True	False

Return True.

Example 2: [6,5,4,4]

i	nums[i-1]	nums[i]	increasing	decreasing
1	6	5	False	True
2	5	4	False	True
3	4	4	False	True

Return True.

Example 3: [1,3,2]

i	nums[i-1]	nums[i]	increasing	decreasing
1	1	3	True	False
2	3	2	False	False

Return False.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We traverse the array once, performing constant-time comparisons for each element.
Space	O(1)	Only two boolean variables are maintained regardless of array size.

The algorithm is efficient because it only requires a single pass and constant extra space, making it suitable even for the largest allowed arrays.

Test Cases

# Provided examples
assert Solution().isMonotonic([1,2,2,3]) == True  # increasing
assert Solution().isMonotonic([6,5,4,4]) == True  # decreasing
assert Solution().isMonotonic([1,3,2]) == False   # not monotonic

# Edge and boundary cases
assert Solution().isMonotonic([1]) == True        # single element
assert Solution().isMonotonic([2,2,2,2]) == True  # all equal
assert Solution().isMonotonic([-100000, 0, 100000]) == True  # increasing with extremes
assert Solution().isMonotonic([100000, 0, -100000]) == True  # decreasing with extremes
assert Solution().isMonotonic([1,2,3,2,4]) == False  # increasing then decreasing

Test	Why
[1,2,2,3]	Validates monotone increasing array
[6,5,4,4]	Validates monotone decreasing array
[1,3,2]	Checks non-monotonic array
[1]	Single element edge case
[2,2,2,2]	All elements equal
[-100000,0,100000]	Increasing with extreme values
[100000,0,-100000]	Decreasing with extreme values
[1,2,3,2,4]	Array that switches direction mid-sequence

Edge Cases

One important edge case is an array with only one element. Such arrays are trivially monotonic because there are no pairs to violate either increasing or decreasing order. Our implementation handles this because the loop does not run, leaving both flags true.

A second edge case is when all elements are equal. In this situation, neither increasing nor decreasing strictly changes, so both flags remain true, and the algorithm correctly returns True.

A third edge case involves arrays that appear to be monotone but switch direction once. For example, [1,2,3,2] initially appears increasing but then decreases. The algorithm detects the violation, sets the increasing flag to false, and since the decreasing flag is also false at the start, it returns False, correctly identifying the array as non-monotonic. This highlights that the approach reliably detects violations without relying on separate scans.