algoadvance

Given an array nums, an array is monotonic if it is either monotone increasing or monotone decreasing.

An array nums is monotone increasing if for all i <= j, nums[i] <= nums[j]. Similarly, an array nums is monotone decreasing if for all i <= j, nums[i] >= nums[j].

Return True if and only if the given array nums is monotonic.

Example 1:

Input: nums = [1,2,2,3]
Output: True

Example 2:

Input: nums = [6,5,4,4]
Output: True

Example 3:

Input: nums = [1,3,2]
Output: False

Constraints:

Clarifying Questions

  1. Should we consider an array with a single element or an empty array as monotonic?
    • Yes, both an array with a single element and an empty array should be considered monotonic.
  2. Can the array contain duplicate numbers?
    • Yes, the array can contain duplicate numbers.

Strategy

To determine if an array is monotonic, we need to verify if it is either monotone increasing or monotone decreasing. We can do this by iterating through the array and checking the direction of the differences between each pair of elements:

  1. Initialize two flags, increasing and decreasing, both set to True.
  2. Iterate through the array from the second element to the last:
    • If any element is greater than the previous one, set the decreasing flag to False.
    • If any element is less than the previous one, set the increasing flag to False.
  3. At the end of the iteration, if either flag remains True, the array is monotonic.

This approach ensures that we only need to make a single pass through the array, making it efficient.

Code

def isMonotonic(nums):
    increasing = True
    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

# Example test cases
print(isMonotonic([1, 2, 2, 3])) # True
print(isMonotonic([6, 5, 4, 4])) # True
print(isMonotonic([1, 3, 2])) # False
print(isMonotonic([1, 1, 1])) # True

Time Complexity

The time complexity of this solution is O(n), where n is the length of the array, because we only iterate through the array once.

The space complexity is O(1) since we only use a fixed amount of additional space regardless of the size of the input array.

Try our interview co-pilot at AlgoAdvance.com