Code Implementation

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

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

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

var isMonotonic = function(nums) {
    let increasing = true, decreasing = true;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i-1]) decreasing = false;
        if (nums[i] < nums[i-1]) increasing = false;
    }
    return increasing || decreasing;
};
      

Problem Description

Given an array of integers nums, determine if the array is monotonic. An array is monotonic if it is either entirely non-increasing or non-decreasing. In other words, for every index i (1 ≤ i < nums.length):

• nums[i] >= nums[i-1] for all i (non-decreasing), or
• nums[i] <= nums[i-1] for all i (non-increasing).

Return true if the array is monotonic, and false otherwise.

Constraints:

• 1 ≤ nums.length ≤ 10⁵
• -10⁵ ≤ nums[i] ≤ 10⁵

Thought Process

At first glance, the problem asks us to check if the numbers in the array never increase or never decrease as we move from left to right. A brute-force approach might involve checking every possible pair of elements, but that is unnecessary and inefficient.

Instead, we can observe that we only need to check the relationship between each consecutive pair of elements. If we ever see a pair where the order violates monotonicity in both directions, the array is not monotonic.

To optimize, we can keep track of two flags: one for non-decreasing and one for non-increasing. As we iterate, we update these flags, and if either remains true by the end, the array is monotonic.

Solution Approach

• Step 1: Initialize two boolean variables: increasing and decreasing, both set to true.
• Step 2: Loop through the array from the second element to the end.
  • For each pair (nums[i-1], nums[i]), check if nums[i] is greater than nums[i-1]. If it is, set decreasing to false (since the sequence is not strictly non-increasing).
  • Similarly, if nums[i] is less than nums[i-1], set increasing to false.
• Step 3: After the loop, if either increasing or decreasing is true, the array is monotonic.
• Why this works: We only need to check adjacent elements. If at any point both increasing and decreasing are false, we can stop early (though the code above checks all elements for clarity).

This method is efficient, straightforward, and easy to implement.

Example Walkthrough

Example Input: nums = [1, 2, 2, 3]

• Start with increasing = true, decreasing = true.
• Compare 1 and 2: 2 > 1, so set decreasing = false. increasing remains true.
• Compare 2 and 2: 2 == 2, no change.
• Compare 2 and 3: 3 > 2, decreasing remains false, increasing remains true.
• At the end, increasing = true, so return true.

Second Example: nums = [6, 5, 4, 4]

• Compare 6 and 5: 5 < 6, set increasing = false.
• Compare 5 and 4: 4 < 5, increasing remains false.
• Compare 4 and 4: 4 == 4, no change.
• At the end, decreasing = true, so return true.

Non-monotonic Example: nums = [1, 3, 2]

• Compare 1 and 3: 3 > 1, set decreasing = false.
• Compare 3 and 2: 2 < 3, set increasing = false.
• Both flags are false, so return false.

Time and Space Complexity

• Brute-force approach: If we compared every possible pair, it would take O(n²) time, which is not practical for large arrays.
• Optimized approach (above):
  • Time Complexity: O(n) — We only loop through the array once, making a constant-time check at each step.
  • Space Complexity: O(1) — We only use two boolean variables, regardless of the input size.

This efficiency is critical for handling arrays of up to 10⁵ elements.

Summary

To determine if an array is monotonic, we check for both non-decreasing and non-increasing patterns by iterating through consecutive pairs. By updating two flags, we can efficiently decide if the array meets the monotonicity condition in a single pass, using only constant extra space. This approach is elegant, easy to implement, and optimal for large datasets.