Solution Explanation: Checking for Monotonic Array

The problem asks to determine if an array is monotonic, meaning it's either entirely non-decreasing (monotone increasing) or entirely non-increasing (monotone decreasing).

Approach:

The most efficient approach involves a single pass through the array. We maintain two boolean flags: asc and desc. asc becomes true if we encounter an increasing pair of elements, and desc becomes true if we encounter a decreasing pair. If both asc and desc are true at any point, it means the array is neither strictly increasing nor strictly decreasing, thus it's not monotonic.

Algorithm:

1. Initialize asc and desc to false.
2. Iterate through the array, comparing each element with its predecessor.
3. If nums[i] > nums[i-1], set asc to true.
4. If nums[i] < nums[i-1], set desc to true.
5. If both asc and desc are true, the array is not monotonic; return false.
6. If the loop completes without finding both asc and desc to be true, the array is monotonic; return true.

Time and Space Complexity:

• Time Complexity: O(n), where n is the length of the array. We perform a single pass through the array.
• Space Complexity: O(1). We use only a constant amount of extra space to store the asc and desc flags.

Code Examples:

The following code examples demonstrate the solution in various programming languages. The core logic remains consistent across all implementations.

Python:

def isMonotonic(nums):
    asc = False
    desc = False
    for i in range(1, len(nums)):
        if nums[i] > nums[i-1]:
            asc = True
        elif nums[i] < nums[i-1]:
            desc = True
        if asc and desc:
            return False
    return True
 

Java:

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

C++:

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

JavaScript:

var isMonotonic = function(nums) {
    let asc = false;
    let desc = false;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) {
            asc = true;
        } else if (nums[i] < nums[i - 1]) {
            desc = true;
        }
        if (asc && desc) return false;
    }
    return true;
};

These examples all implement the same efficient single-pass algorithm with O(n) time and O(1) space complexity. The choice of language primarily impacts the syntax, but the underlying logic remains consistent.