896. Monotonic Array

EasyArray
Leetcode Link

Problem Description

In this problem, we are given an integer array nums and our task is to determine whether the array is monotonic or not. An array is considered monotonic if it is either monotonically increasing or monotonically decreasing. This means that for each pair of indices i and j where i <= j, the condition nums[i] <= nums[j] must hold true for the entire array if it's increasing, or nums[i] >= nums[j] if it's decreasing. The goal is to return true if the array meets either of these conditions for all its elements, and false otherwise.

Intuition

To understand if an array is monotonic, we need to check two conditions:

  1. Monotone Increasing: To verify this, we need to check if every element at index i is less than or equal to the element at index i+1. This should be true for all consecutive pairs in the array.
  2. Monotone Decreasing: Similarly, we need to check if every element at index i is greater than or equal to the element at index i+1 for all consecutive pairs.

The given Python solution approaches the problem by checking both conditions separately. It uses the pairwise utility which, in this context, would generate pairs of consecutive elements from the nums array. It is important to note that pairwise is available in the itertools module from Python 3.10 onwards. For versions prior to that, we can manually create pairs using a simple loop or list comprehension.

For the increasing condition, the expression all(a <= b for a, b in pairwise(nums)) returns True if every element a is less than or equal to the next element b, for all pairs (a, b) in the array. Similarly, the decreasing condition is checked with the expression all(a >= b for a, b in pairwise(nums)).

Finally, the function returns True if either of these conditions is True, meaning the array is either strictly non-decreasing or strictly non-increasing. Otherwise, it returns False, indicating the array is not monotonic.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What data structure does Breadth-first search typically uses to store intermediate states?

Solution Approach

The solution provided in the Python code relies on a straightforward approach and the efficient use of Python's built-in functions to check if the array is monotonic. Let's break down the steps of how the algorithm is implemented:

  1. The solution first attempts to determine if the array is monotonically increasing. It does this with the help of a generator expression all(a <= b for a, b in pairwise(nums)). This expression generates a sequence of boolean values for each pairwise comparison between items a and b in the array such that a and b are consecutive elements. If a is always less than or equal to b, meaning no violation of the increasing condition is found, the all function will return True.

  2. Similarly, the solution tries to find out if the array is monotonically decreasing by using the expression all(a >= b for a, b in pairwise(nums)). This also generates a sequence of boolean values where each pair is compared to ensure that a is greater than or equal to b. If this is true for the whole array, the all function returns True.

  3. As for the pairwise function, it is not explicitly defined within the solution, which implies it must be imported from Python's itertools module before using the solution. pairwise creates an iterator that returns consecutive pairs of elements from the input iterable. For example, pairwise([1, 2, 3, 4]) would yield (1, 2), (2, 3), and (3, 4). If the pairwise function is unavailable, the same effect can be achieved with zip(nums, nums[1:]).

  4. The crucial part of the solution is the return incr or decr line of code. What it does is return True if either variable incr or decr is True. These two variables hold the outcomes of the monotonic increasing or decreasing checks. In essence, the array is monotonic if it is either entirely non-decreasing or non-increasing.

By combining these checks, the problem is addressed in a concise manner that effectively determines the monotonicity of the array with minimal iteration, therefore optimizing the solution's time complexity to O(n), where n is the length of the input array.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Let's illustrate the solution approach using a small example array nums = [3, 3, 5, 5, 6, 7, 7].

  1. First, we create pairs of consecutive elements:

    • (3, 3)
    • (3, 5)
    • (5, 5)
    • (5, 6)
    • (6, 7)
    • (7, 7)

  2. Now, we apply the check to see if the array is monotonically increasing. For this example:

    • We compare 3 <= 3, which is True.
    • We compare 3 <= 5, which is True.
    • We compare 5 <= 5, which is True.
    • We compare 5 <= 6, which is True.
    • We compare 6 <= 7, which is True.
    • We compare 7 <= 7, which is True.

    These pairwise comparisons give us all True outcomes. Therefore, incr = True as all elements satisfy the condition a <= b.

  3. We don't necessarily need to proceed with checking for monotonically decreasing conditions because we have already found that the array is monotonically increasing. However, for the sake of understanding, we would check as follows:

    • Compare 3 >= 3, which is True.
    • Compare 3 >= 5, which is False.

    At this point, we already have a False, so we know decr will be False, and there's no need to continue. Every subsequent comparison (though not needed here) would have at least one more False, confirming the array isn't monotonically decreasing.

  4. Since the variable incr holds True (and decr holds False), the final result returned by the function is True.

In this example, we deduced that nums is monotonically increasing, and therefore, it is a monotonic array. The key takeaway is that the array only needs to fulfill one of the two monotonic conditions (increasing or decreasing), not both.

Solution Implementation

1from itertools import pairwise  # Ensure that pairwise is imported from itertools
2
3class Solution:
4    def isMonotonic(self, numbers: List[int]) -> bool:
5        # Check if the sequence is monotonically increasing
6        is_increasing = all(a <= b for a, b in pairwise(numbers))
7        # Check if the sequence is monotonically decreasing
8        is_decreasing = all(a >= b for a, b in pairwise(numbers))
9        # The sequence is monotonic if it's either increasing or decreasing
10        return is_increasing or is_decreasing
11
12# Note: If the Python environment is older than 3.10, you'll need this definition of pairwise:
13# def pairwise(iterable):
14#     "s -> (s0,s1), (s1,s2), (s2, s3), ..."
15#     a, b = tee(iterable)
16#     next(b, None)
17#     return zip(a, b)
18
1class Solution {
2    // Function to determine if the array is either entirely non-increasing or non-decreasing
3    public boolean isMonotonic(int[] nums) {
4        boolean isIncreasing = true; // To keep track if the array is non-decreasing
5        boolean isDecreasing = true; // To keep track if the array is non-increasing
6      
7        // Iterate over the array starting from the second element
8        for (int i = 1; i < nums.length; i++) {
9            if (nums[i] < nums[i - 1]) {
10                // If the current number is less than the previous, it's not non-decreasing
11                isIncreasing = false;
12            }
13            if (nums[i] > nums[i - 1]) {
14                // If the current number is greater than the previous, it's not non-increasing
15                isDecreasing = false;
16            }
17            // If the array is neither non-decreasing nor non-increasing, return false
18            if (!isIncreasing && !isDecreasing) {
19                return false;
20            }
21        }
22        // If we reach this point, the array is either non-decreasing, non-increasing, or all elements are equal
23        return true;
24    }
25}
26
1class Solution {
2public:
3    // Function to determine if the array is monotonic (either entirely non-increasing or non-decreasing)
4    bool isMonotonic(vector<int>& nums) {
5      
6        // Initialize two boolean flags for increasing and decreasing
7        bool isIncreasing = true;
8        bool isDecreasing = true;
9      
10        // Iterate over the array starting from the second element
11        for (int i = 1; i < nums.size(); ++i) {
12          
13            // If the current element is smaller than the previous, it's not increasing
14            if (nums[i] < nums[i - 1]) {
15                isIncreasing = false;
16            }
17          
18            // If the current element is larger than the previous, it's not decreasing
19            if (nums[i] > nums[i - 1]) {
20                isDecreasing = false;
21            }
22          
23            // If it's neither increasing nor decreasing, it's not monotonic
24            if (!isIncreasing && !isDecreasing) {
25                return false;
26            }
27        }
28      
29        // If the array is either increasing or decreasing, then it's monotonic
30        return true;
31    }
32};
33
1/**
2 * Determines if an array of numbers is monotonic.
3 * An array is monotonic if it is either monotone increasing or monotone decreasing.
4 * @param {number[]} nums The array of numbers to check.
5 * @returns {boolean} True if the array is monotonic, otherwise false.
6 */
7function isMonotonic(nums: number[]): boolean {
8    const length = nums.length;
9    let isIncreasing = false;
10    let isDecreasing = false;
11
12    // Traverse the array, starting from the second element
13    for (let i = 1; i < length; i++) {
14        const previous = nums[i - 1]; // Previous element
15        const current = nums[i]; // Current element
16
17        // Check if the current pair is increasing
18        if (previous < current) {
19            isIncreasing = true;
20        } 
21        // Check if the current pair is decreasing
22        else if (previous > current) {
23            isDecreasing = true;
24        }
25
26        // If the sequence has both increasing and decreasing pairs,
27        // it is not monotonic.
28        if (isIncreasing && isDecreasing) {
29            return false;
30        }
31    }
32
33    // If the loop completes without returning false,
34    // the array is monotonic.
35    return true;
36}
37
Not Sure What to Study? Take the 2-min Quiz：

Which of the following uses divide and conquer strategy?

Time and Space Complexity

The time complexity of the code is O(n) where n is the length of the nums list. This is because the pairwise function is going through the list only once for each check (increasing and decreasing). Each all() call iterates over the list in a pairwise fashion, which means there will be a total of n-1 comparisons for each call.

The space complexity of the code is O(1) since the space used does not depend on the size of the input nums list. The pairwise function generates a sequence of tuples which is consumed by the all() function, and this does not require additional space that scales with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫