Monotonic Array
EasyPrompt
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: trueExample 2:
Input: nums = [6,5,4,4]
Output: trueExample 3:
Input: nums = [1,3,2]
Output: false
Constraints:
1 <= nums.length <= 105-105 <= nums[i] <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This straightforward approach checks for the two conditions of monotonicity (non-decreasing and non-increasing) in two separate iterations. It first scans the entire array to see if it's non-decreasing. If not, it performs a second scan to check if it's non-increasing. The array is monotonic if it satisfies at least one of these conditions.
Algorithm
- Check if the array is non-decreasing by iterating from
i = 0ton-2. - In the loop, if
nums[i] > nums[i+1], the condition is violated, so it's not non-decreasing. - If the first check passes, the array is monotonic (non-decreasing), so return
true. - If the first check fails, check if the array is non-increasing by iterating from
i = 0ton-2. - In this second loop, if
nums[i] < nums[i+1], the condition is violated. - The final result is
trueif the array is non-decreasing OR non-increasing, andfalseotherwise.
Walkthrough
The core idea is to break the problem down into two subproblems: checking for a non-decreasing sequence and checking for a non-increasing sequence.
We can implement two helper functions, isNonDecreasing and isNonIncreasing.
The isNonDecreasing function iterates through the array from the first element to the second-to-last. If it ever finds nums[i] > nums[i+1], it immediately knows the array is not non-decreasing and returns false. If the loop completes without finding such a pair, the array is non-decreasing, and it returns true.
The isNonIncreasing function works similarly, but it checks for the condition nums[i] < nums[i+1].
The main function isMonotonic then simply calls both helper functions and returns true if either of them returns true.
class Solution { public boolean isMonotonic(int[] nums) { return isNonDecreasing(nums) || isNonIncreasing(nums); } private boolean isNonDecreasing(int[] nums) { for (int i = 0; i < nums.length - 1; i++) { if (nums[i] > nums[i+1]) { return false; } } return true; } private boolean isNonIncreasing(int[] nums) { for (int i = 0; i < nums.length - 1; i++) { if (nums[i] < nums[i+1]) { return false; } } return true; }}Complexity
Time
O(N), where N is the number of elements in the array. In the worst-case scenario (e.g., for an array like `[1, 5, 2]`), we might traverse the array almost twice. For a monotonic array, we will traverse it fully once and then partially or fully a second time.
Space
O(1), as no extra space proportional to the input size is used. The space for helper function call stacks is constant.
Trade-offs
Pros
The logic is very clear and easy to follow, as it separates the two conditions for monotonicity.
Easy to implement and debug.
Cons
It is less efficient than a single-pass solution because it might iterate over the array twice.
Solutions
Solution
class Solution { public boolean isMonotonic ( int [] nums ) { boolean asc = false , desc = false ; for ( int i = 1 ; i < nums . length ; ++ i ) { if ( nums [ i - 1 ] < nums [ i ]) { asc = true ; } else if ( nums [ i - 1 ] > nums [ i ]) { desc = true ; } if ( asc && desc ) { return false ; } } return true ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.