Monotonic Array

Easy

#0850Time: 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.1 company

Data structures

Array

Companies

Ozon

Prompt

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 <= 10⁵
-10⁵ <= nums[i] <= 10⁵

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 = 0 to n-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 = 0 to n-2.
In this second loop, if nums[i] < nums[i+1], the condition is violated.
The final result is true if the array is non-decreasing OR non-increasing, and false otherwise.

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.

1class Solution {2    public boolean isMonotonic(int[] nums) {3        return isNonDecreasing(nums) || isNonIncreasing(nums);4    }5 6    private boolean isNonDecreasing(int[] nums) {7        for (int i = 0; i < nums.length - 1; i++) {8            if (nums[i] > nums[i+1]) {9                return false;10            }11        }12        return true;13    }14 15    private boolean isNonIncreasing(int[] nums) {16        for (int i = 0; i < nums.length - 1; i++) {17            if (nums[i] < nums[i+1]) {18                return false;19            }20        }21        return true;22    }23}

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.

This optimized approach determines if an array is monotonic in a single pass. It maintains two boolean flags, one to track if the array could be non-decreasing and another to track if it could be non-increasing. By updating these flags while iterating through the array just once, we can efficiently arrive at the solution.

Algorithm

Initialize two boolean flags, increasing = true and decreasing = true.
Iterate through the array from i = 0 to n-2.
In each iteration, compare nums[i] with nums[i+1].
If nums[i] > nums[i+1], set increasing = false.
If nums[i] < nums[i+1], set decreasing = false.
After the loop, return increasing || decreasing.

Walkthrough

We can improve upon the two-pass approach by combining the checks into a single loop. We initialize two boolean variables, increasing and decreasing, to true. We then iterate through the array from the first element to the second-to-last. In each step, we compare nums[i] with nums[i+1]:

If we find that nums[i] > nums[i+1], we know the array cannot be non-decreasing, so we set the increasing flag to false.
If we find that nums[i] < nums[i+1], we know the array cannot be non-increasing, so we set the decreasing flag to false. If at any point both flags become false, we could even break out of the loop early, but it's not necessary for correctness. After the loop completes, the array is monotonic if either the increasing flag or the decreasing flag is still true.

1class Solution {2    public boolean isMonotonic(int[] nums) {3        if (nums.length <= 1) {4            return true;5        }6        7        boolean increasing = true;8        boolean decreasing = true;9        10        for (int i = 0; i < nums.length - 1; i++) {11            if (nums[i] > nums[i+1]) {12                increasing = false;13            }14            if (nums[i] < nums[i+1]) {15                decreasing = false;16            }17        }18        19        return increasing || decreasing;20    }21}

Complexity

Time

O(N), where N is the number of elements in the array. We only need to iterate through the array once.

Space

O(1). We only use a constant amount of extra space for the two boolean flags.

Trade-offs

Pros

This is the most efficient approach in terms of time complexity, as it guarantees a single pass.
It's optimal as we must examine each element at least once in the worst case.

Cons

Slightly more complex than the two-pass approach as it combines two logical checks in one loop.

Solutions

Solution

1class 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 ; } }

1/** * @param {number[]} nums * @return {boolean} */ var isMonotonic = function (2  nums,3) {4  let [asc, desc] = [false, false];5  for (let i = 1; i < nums.length; ++i) {6    if (nums[i - 1] < nums[i]) {7      asc = true;8    } else if (nums[i - 1] > nums[i]) {9      desc = true;10    }11    if (asc && desc) {12      return false;13    }14  }15  return true;16};

1class Solution { public: bool isMonotonic ( vector < int >& nums ) { bool asc = false , desc = false ; for ( int i = 1 ; i < nums . size (); ++ 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 ; } };

1class Solution : def isMonotonic ( self , nums : List [ int ]) -> bool : asc = all ( a <= b for a , b in pairwise ( nums )) desc = all ( a >= b for a , b in pairwise ( nums )) return asc or desc

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.

← Previous

Previous problem

Next problem