Monotonic Array

EASY

Description

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

Checkout 2 different approaches to solve Monotonic Array. Click on different approaches to view the approach and algorithm in detail.

Two-Pass Iteration

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.

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 Analysis

Time Complexity: 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 Complexity: O(1), as no extra space proportional to the input size is used. The space for helper function call stacks is constant.

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Monotonic Array. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Monotonic Array

Data Structures:

Array

Companies:

Ozon |