896. Monotonic Array
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:
- Monotone Increasing: To verify this, we need to check if every element at index
i
is less than or equal to the element at indexi+1
. This should be true for all consecutive pairs in the array. - Monotone Decreasing: Similarly, we need to check if every element at index
i
is greater than or equal to the element at indexi+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.
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:
-
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 itemsa
andb
in the array such thata
andb
are consecutive elements. Ifa
is always less than or equal tob
, meaning no violation of the increasing condition is found, theall
function will returnTrue
. -
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 thata
is greater than or equal tob
. If this is true for the whole array, theall
function returnsTrue
. -
As for the
pairwise
function, it is not explicitly defined within the solution, which implies it must be imported from Python'sitertools
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 thepairwise
function is unavailable, the same effect can be achieved withzip(nums, nums[1:])
. -
The crucial part of the solution is the
return incr or decr
line of code. What it does is returnTrue
if either variableincr
ordecr
isTrue
. 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example array nums = [3, 3, 5, 5, 6, 7, 7]
.
-
First, we create pairs of consecutive elements:
- (3, 3)
- (3, 5)
- (5, 5)
- (5, 6)
- (6, 7)
- (7, 7)
-
Now, we apply the check to see if the array is monotonically increasing. For this example:
- We compare
3 <= 3
, which isTrue
. - We compare
3 <= 5
, which isTrue
. - We compare
5 <= 5
, which isTrue
. - We compare
5 <= 6
, which isTrue
. - We compare
6 <= 7
, which isTrue
. - We compare
7 <= 7
, which isTrue
.
These pairwise comparisons give us all
True
outcomes. Therefore,incr = True
as all elements satisfy the conditiona <= b
. - We compare
-
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 isTrue
. - Compare
3 >= 5
, which isFalse
.
At this point, we already have a
False
, so we knowdecr
will beFalse
, and there's no need to continue. Every subsequent comparison (though not needed here) would have at least one moreFalse
, confirming the array isn't monotonically decreasing. - Compare
-
Since the variable
incr
holdsTrue
(anddecr
holdsFalse
), the final result returned by the function isTrue
.
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
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.
A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".
What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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 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