896. Monotonic Array - Explanation

Prerequisites

Before attempting this problem, you should be comfortable with:

Arrays - Understanding how to iterate through arrays and access elements by index
Comparison Operators - Using comparison operators to check relationships between adjacent elements

1. Two Pass

Intuition

An array is monotonic if it is entirely non-decreasing or entirely non-increasing. We can check each condition separately. First, scan to see if every element is greater than or equal to the previous one. If this holds, the array is monotonically increasing. If not, scan again to check if every element is less than or equal to the previous one. If either condition is satisfied, the array is monotonic.

Algorithm

Assume the array is increasing. Iterate through and check if nums[i] < nums[i - 1] for any i. If found, the array is not increasing.
If the array passed the increasing check, return true.
Otherwise, assume the array is decreasing. Iterate through and check if nums[i] > nums[i - 1] for any i. If found, the array is not decreasing.
Return whether the array passed the decreasing check.

class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        n = len(nums)
        increase = True
        for i in range(1, n):
            if nums[i] < nums[i - 1]:
                increase = False
                break

        if increase:
            return True

        decrease = True
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                decrease = False
                break
        return decrease

public class Solution {
    public boolean isMonotonic(int[] nums) {
        int n = nums.length;
        boolean increase = true;
        for (int i = 1; i < n; i++) {
            if (nums[i] < nums[i - 1]) {
                increase = false;
                break;
            }
        }
        if (increase) {
            return true;
        }

        boolean decrease = true;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                decrease = false;
                break;
            }
        }
        return decrease;
    }
}

class Solution {
public:
    bool isMonotonic(vector<int>& nums) {
        int n = nums.size();
        bool increase = true;
        for (int i = 1; i < n; ++i) {
            if (nums[i] < nums[i - 1]) {
                increase = false;
                break;
            }
        }
        if (increase) {
            return true;
        }

        bool decrease = true;
        for (int i = 1; i < n; ++i) {
            if (nums[i] > nums[i - 1]) {
                decrease = false;
                break;
            }
        }
        return decrease;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {boolean}
     */
    isMonotonic(nums) {
        const n = nums.length;
        let increase = true;
        for (let i = 1; i < n; i++) {
            if (nums[i] < nums[i - 1]) {
                increase = false;
                break;
            }
        }
        if (increase) {
            return true;
        }

        let decrease = true;
        for (let i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                decrease = false;
                break;
            }
        }
        return decrease;
    }
}

public class Solution {
    public bool IsMonotonic(int[] nums) {
        int n = nums.Length;
        bool increase = true;
        for (int i = 1; i < n; i++) {
            if (nums[i] < nums[i - 1]) {
                increase = false;
                break;
            }
        }
        if (increase) {
            return true;
        }

        bool decrease = true;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                decrease = false;
                break;
            }
        }
        return decrease;
    }
}

func isMonotonic(nums []int) bool {
    n := len(nums)
    increase := true
    for i := 1; i < n; i++ {
        if nums[i] < nums[i-1] {
            increase = false
            break
        }
    }
    if increase {
        return true
    }

    decrease := true
    for i := 1; i < n; i++ {
        if nums[i] > nums[i-1] {
            decrease = false
            break
        }
    }
    return decrease
}

class Solution {
    fun isMonotonic(nums: IntArray): Boolean {
        val n = nums.size
        var increase = true
        for (i in 1 until n) {
            if (nums[i] < nums[i - 1]) {
                increase = false
                break
            }
        }
        if (increase) {
            return true
        }

        var decrease = true
        for (i in 1 until n) {
            if (nums[i] > nums[i - 1]) {
                decrease = false
                break
            }
        }
        return decrease
    }
}

class Solution {
    func isMonotonic(_ nums: [Int]) -> Bool {
        let n = nums.count
        var increase = true
        for i in 1..<n {
            if nums[i] < nums[i - 1] {
                increase = false
                break
            }
        }
        if increase {
            return true
        }

        var decrease = true
        for i in 1..<n {
            if nums[i] > nums[i - 1] {
                decrease = false
                break
            }
        }
        return decrease
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

2. One Pass - I

Intuition

We can determine the expected direction by comparing the first and last elements. If the first element is less than or equal to the last, the array should be non-decreasing. Otherwise, it should be non-increasing. With the direction determined upfront, a single pass can verify whether all consecutive pairs follow the expected pattern.

Algorithm

Compare nums[0] and nums[n - 1] to determine the expected direction.
If nums[0] <= nums[n - 1], the array should be non-decreasing:
- Iterate through and return false if any nums[i] < nums[i - 1].
Otherwise, the array should be non-increasing:
- Iterate through and return false if any nums[i] > nums[i - 1].
If no violations are found, return true.

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

public class Solution {
    public boolean isMonotonic(int[] nums) {
        int n = nums.length;
        if (nums[0] <= nums[n - 1]) {
            for (int i = 1; i < n; i++) {
                if (nums[i] < nums[i - 1]) {
                    return false;
                }
            }
            return true;
        } else {
            for (int i = 1; i < n; i++) {
                if (nums[i] > nums[i - 1]) {
                    return false;
                }
            }
            return true;
        }
    }
}

class Solution {
public:
    bool isMonotonic(vector<int>& nums) {
        int n = nums.size();
        if (nums[0] <= nums[n - 1]) {
            for (int i = 1; i < n; ++i) {
                if (nums[i] < nums[i - 1]) {
                    return false;
                }
            }
            return true;
        } else {
            for (int i = 1; i < n; ++i) {
                if (nums[i] > nums[i - 1]) {
                    return false;
                }
            }
            return true;
        }
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {boolean}
     */
    isMonotonic(nums) {
        const n = nums.length;
        if (nums[0] <= nums[n - 1]) {
            for (let i = 1; i < n; i++) {
                if (nums[i] < nums[i - 1]) {
                    return false;
                }
            }
            return true;
        } else {
            for (let i = 1; i < n; i++) {
                if (nums[i] > nums[i - 1]) {
                    return false;
                }
            }
            return true;
        }
    }
}

public class Solution {
    public bool IsMonotonic(int[] nums) {
        int n = nums.Length;
        if (nums[0] <= nums[n - 1]) {
            for (int i = 1; i < n; i++) {
                if (nums[i] < nums[i - 1]) {
                    return false;
                }
            }
            return true;
        } else {
            for (int i = 1; i < n; i++) {
                if (nums[i] > nums[i - 1]) {
                    return false;
                }
            }
            return true;
        }
    }
}

func isMonotonic(nums []int) bool {
    n := len(nums)
    if nums[0] <= nums[n-1] {
        for i := 1; i < n; i++ {
            if nums[i] < nums[i-1] {
                return false
            }
        }
        return true
    } else {
        for i := 1; i < n; i++ {
            if nums[i] > nums[i-1] {
                return false
            }
        }
        return true
    }
}

class Solution {
    fun isMonotonic(nums: IntArray): Boolean {
        val n = nums.size
        if (nums[0] <= nums[n - 1]) {
            for (i in 1 until n) {
                if (nums[i] < nums[i - 1]) {
                    return false
                }
            }
            return true
        } else {
            for (i in 1 until n) {
                if (nums[i] > nums[i - 1]) {
                    return false
                }
            }
            return true
        }
    }
}

class Solution {
    func isMonotonic(_ nums: [Int]) -> Bool {
        let n = nums.count
        if nums[0] <= nums[n - 1] {
            for i in 1..<n {
                if nums[i] < nums[i - 1] {
                    return false
                }
            }
            return true
        } else {
            for i in 1..<n {
                if nums[i] > nums[i - 1] {
                    return false
                }
            }
            return true
        }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

3. One Pass - II

Intuition

Rather than deciding the direction upfront, we can track both possibilities simultaneously. We maintain two flags: one for whether the array could still be non-decreasing, and one for whether it could still be non-increasing. As we scan, any violation disqualifies that direction. At the end, if at least one flag remains true, the array is monotonic.

Algorithm

Initialize two boolean flags: increase = true and decrease = true.
Iterate through consecutive pairs (nums[i], nums[i + 1]):
- If nums[i] > nums[i + 1], set increase = false.
- If nums[i] < nums[i + 1], set decrease = false.
Return increase || decrease.

class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        increase, decrease = True, True

        for i in range(len(nums) - 1):
            if not (nums[i] <= nums[i + 1]):
                increase = False
            if not (nums[i] >= nums[i + 1]):
                decrease = False
        return increase or decrease

public class Solution {
    public boolean isMonotonic(int[] nums) {
        boolean increase = true, decrease = true;

        for (int i = 0; i < nums.length - 1; i++) {
            if (!(nums[i] <= nums[i + 1])) {
                increase = false;
            }
            if (!(nums[i] >= nums[i + 1])) {
                decrease = false;
            }
        }
        return increase || decrease;
    }
}

class Solution {
public:
    bool isMonotonic(vector<int>& nums) {
        bool increase = true, decrease = true;

        for (int i = 0; i < nums.size() - 1; ++i) {
            if (!(nums[i] <= nums[i + 1])) {
                increase = false;
            }
            if (!(nums[i] >= nums[i + 1])) {
                decrease = false;
            }
        }
        return increase || decrease;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {boolean}
     */
    isMonotonic(nums) {
        let increase = true,
            decrease = true;

        for (let i = 0; i < nums.length - 1; i++) {
            if (!(nums[i] <= nums[i + 1])) {
                increase = false;
            }
            if (!(nums[i] >= nums[i + 1])) {
                decrease = false;
            }
        }
        return increase || decrease;
    }
}

public class Solution {
    public bool IsMonotonic(int[] nums) {
        bool increase = true, decrease = true;

        for (int i = 0; i < nums.Length - 1; i++) {
            if (!(nums[i] <= nums[i + 1])) {
                increase = false;
            }
            if (!(nums[i] >= nums[i + 1])) {
                decrease = false;
            }
        }
        return increase || decrease;
    }
}

func isMonotonic(nums []int) bool {
    increase, decrease := true, true

    for i := 0; i < len(nums)-1; i++ {
        if !(nums[i] <= nums[i+1]) {
            increase = false
        }
        if !(nums[i] >= nums[i+1]) {
            decrease = false
        }
    }
    return increase || decrease
}

class Solution {
    fun isMonotonic(nums: IntArray): Boolean {
        var increase = true
        var decrease = true

        for (i in 0 until nums.size - 1) {
            if (!(nums[i] <= nums[i + 1])) {
                increase = false
            }
            if (!(nums[i] >= nums[i + 1])) {
                decrease = false
            }
        }
        return increase || decrease
    }
}

class Solution {
    func isMonotonic(_ nums: [Int]) -> Bool {
        var increase = true
        var decrease = true

        for i in 0..<(nums.count - 1) {
            if !(nums[i] <= nums[i + 1]) {
                increase = false
            }
            if !(nums[i] >= nums[i + 1]) {
                decrease = false
            }
        }
        return increase || decrease
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Using Strict Inequality Instead of Non-Strict

A monotonic array allows equal consecutive elements (non-decreasing or non-increasing). Using strict comparisons like nums[i] > nums[i-1] instead of nums[i] >= nums[i-1] incorrectly rejects arrays like [1, 2, 2, 3] as non-monotonic. The condition should check for <= (non-decreasing) or >= (non-increasing) to properly handle equal adjacent values.

Checking Only One Direction

Arrays that are constant (all elements equal) are both non-decreasing and non-increasing. Returning false early when detecting a violation in one direction without checking the other leads to incorrect results. The array [5, 5, 5] should return true, but checking only for strictly increasing or strictly decreasing patterns would fail this case.