We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Monotonic Array

Number: 932

Difficulty: Easy

Paid? No

Companies: Meta, Google, Yandex, Amazon, Adobe, TikTok

Problem Description

Determine if a given array of integers is monotonic, meaning it is either entirely non-decreasing or non-increasing. Return true if the array meets the monotonic criteria, and false otherwise.

Key Insights

  • An array is monotonic if it is either monotone increasing (each element is greater than or equal to the previous) or monotone decreasing (each element is less than or equal to the previous).
  • Use two flags to keep track of whether the array can be increasing and/or decreasing.
  • A single pass through the array is sufficient to update these flags based on adjacent element comparisons.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as only constant additional space is used.

Solution

The solution initializes two boolean flags, one for checking non-decreasing order (increasing) and another for non-increasing order (decreasing). As you loop through the array comparing each element to its predecessor, you update these flags accordingly. If an element violates the condition for increasing order, the increasing flag is set to false; similarly, if it violates the decreasing condition, the decreasing flag is set to false. At the end of the loop, if either flag remains true, the array is monotonic. This simple linear scan with constant extra space efficiently validates the monotonic nature of the array.

Code Solutions

def isMonotonic(nums):
    # Initialize flags for increasing and decreasing orders.
    increasing = True
    decreasing = True

    # Loop through the list starting from the second element.
    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            # If current element is greater than the previous, the array cannot be decreasing.
            decreasing = False
        if nums[i] < nums[i - 1]:
            # If current element is less than the previous, the array cannot be increasing.
            increasing = False

    # The array is monotonic if it is either increasing or decreasing.
    return increasing or decreasing

# Example usage:
print(isMonotonic([1, 2, 2, 3]))  # Expected output: True
← Back to All Questions