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]. An array nums is monotone decreasing if for all i <= j, nums[i] >= nums[j].
Given an integer array nums, return true if the given array is monotonic, or false otherwise.
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:
1 <= nums.length <= 105-105 <= nums[i] <= 105This approach involves traversing the array and maintaining two flags: one for checking if the array elements are in increasing order and another for checking if they are in decreasing order. As we iterate through the array, we update these flags accordingly. If the array violates both conditions at any point, it is not monotonic.
We loop through the array, starting from the second element. We check if the current element is greater than or less than the previous element and update the respective flags (decreasing and increasing). If both conditions are violated for any element pair, the function returns false. At the end of the loop, if either flag remains true, it implies the array is monotonic.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the array, since we perform a single traversal of the array.
Space Complexity: O(1), as no extra space is utilized apart from the flags.
In this approach, we perform two separate passes to test for monotonic increase and monotonic decrease independently. The first pass checks for strictly increasing nature, and the second checks for strictly decreasing nature.
The C solution uses two helper functions, isIncreasing and isDecreasing, which independently check if the array is monotone increasing or decreasing. The main function returns true if either condition holds true.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), two passes over the array which are separate checks.
Space Complexity: O(1), with no additional space used beyond flags.
| Approach | Complexity |
|---|---|
| Single Pass Check for Monotonic Nature | Time Complexity: O(n), where n is the length of the array, since we perform a single traversal of the array. |
| Two Separate Passes for Increasing and Decreasing | Time Complexity: O(n), two passes over the array which are separate checks. |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,144 views views
Watch 9 more video solutions →Practice Monotonic Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor