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] <= 105Problem Overview: You are given an integer array and must determine whether the sequence is monotonic. A monotonic array is either entirely non‑decreasing or entirely non‑increasing. Equal adjacent values are allowed, but the direction must never switch.
Approach 1: Two Separate Passes for Increasing and Decreasing (O(n) time, O(1) space)
The straightforward strategy checks both possible monotonic directions independently. First iterate through the array and verify the non‑decreasing condition: nums[i] >= nums[i-1] for every element. If any pair violates this rule, the array is not non‑decreasing. Then perform a second pass checking the non‑increasing condition nums[i] <= nums[i-1]. If either pass succeeds, the array is monotonic.
This approach keeps the logic extremely simple. Each pass performs a linear scan, comparing adjacent elements. No additional data structures are required, so space complexity stays constant. The trade‑off is that you potentially traverse the array twice, although the asymptotic complexity remains O(n). When clarity matters more than micro‑optimizations, this version is often preferred.
Approach 2: Single Pass Check for Monotonic Nature (O(n) time, O(1) space)
A more efficient implementation determines the direction during a single traversal. Track two boolean flags: one representing whether the sequence can still be non‑decreasing and another for non‑increasing. While iterating through adjacent elements, update these flags whenever a violation occurs. For example, if nums[i] < nums[i-1], the array cannot be non‑decreasing; if nums[i] > nums[i-1], it cannot be non‑increasing.
Once both flags become false, you can immediately stop because the array has already switched direction. If at least one flag survives the scan, the sequence is monotonic. This method still performs simple adjacent comparisons but reduces the logic to a single pass over the data. Time complexity remains O(n) with constant O(1) auxiliary space.
This pattern appears frequently in array traversal problems where the property of interest depends only on neighboring elements. It resembles techniques used in two pointers and simple greedy validations where you maintain state while scanning.
Recommended for interviews: The single‑pass flag approach is typically what interviewers expect. It demonstrates that you can detect monotonic direction dynamically while scanning the array once. The two‑pass method still shows solid understanding and may be easier to reason about, but the single‑pass check communicates stronger algorithmic intuition and attention to efficiency.
This 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.
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.
Time Complexity: O(n), two passes over the array which are separate checks.
Space Complexity: O(1), with no additional space used beyond flags.
We traverse the array, and if an increasing or decreasing situation occurs, we record it. We then check whether both increasing and decreasing situations have occurred. If both have occurred, it means that the array is not monotonic, and we return false.
Otherwise, if we reach the end of the traversal, it means that the array is monotonic, and we return true.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| 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. |
| Single Traversal | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Separate Passes for Increasing and Decreasing | O(n) | O(1) | Best for readability and simple reasoning when performance differences are negligible |
| Single Pass Monotonic Check | O(n) | O(1) | Preferred interview solution since it validates monotonic direction in one traversal |
LeetCode 896. Monotonic Array (Algorithm Explained) • Nick White • 11,473 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