Welcome to my article! This article starts with "How we think about a solution". In other words, that is my thought process to solve the question. This article explains how I get to my solution instead of just posting solution codes or out of blue algorithms. I hope this article is helpful for someone.
Intuition
Use two flags to check this is increasing or decreasing.
Solution Video
896. Monotonic Array Solution Video
⭐️⭐️ Don't forget to subscribe to my channel! ⭐️⭐️
■ Subscribe URL
http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1
Subscribers: 2,533
My initial goal is 10,000
Thank you for your support!
Approach
How we think about a solution.
At first, I solved this question with two loops simply like this.
class Solution:
def isMonotonic(self, nums: List[int]) -> bool:
n = len(nums)
if n == 1: return True
# check if this is increasing
for i in range(1, n):
if nums[i] < nums[i-1]:
break
if i == n - 1:
return True
# check if this is decreasing
for i in range(1, n):
if nums[i] > nums[i-1]:
break
if i == n - 1:
return True
return False
This solution passed all test cases and beated about 60%... not bad. but I realized that we can check both simultaneously if we have two flags.
The two flags indicates that input is increasing or decreasing.
The both flags start with True
Input: nums = [1,2,2,3]
is_inc = True
is_dec = True
First of all, check length of input and if length of input is 1 return true.
Next, we start from index 1. Compare two numbers at index 1 and index 0
index 0: 1
index 1: 2
is_inc = True
is_dec = False
This is increasing case, so in the end the two flags should be above.
index 1: 2
index 2: 2
is_inc = True
is_dec = False
We can consider the same numbers as both cases, so this is increasing case because is_dec was already false, so in the end the two flags should be the same.
index 2: 2
index 3: 3
is_inc = True
is_dec = False
This is increasing case, the both flag should be the same. Then finish looping.
After that, check both flags and if one of them is still true, that means we have Monotonic Array, so return true.
Of course, during looping, if both flags are false, we can immediately return false.
And one more thing
I use or at the last step in the codes. It covers cases like [1,3,2]. In this case, loop 2 times and is_dec turn into false in the first loop and is_inc turn into false in the second loop.
So now both flags are false and finish looping.
What I'm trying to say is that
Finishing loop is not always true case.
That's why I check both flags with or.
Be careful.
Let's see a real algorithm!
Algorithm Overview:
- Initialize variables
is_incandis_dectoTrueto track whether the sequence is increasing or decreasing. - Iterate through the input list
numsstarting from the second element. - Update
is_inctoFalseif the current element is less than the previous element. - Update
is_dectoFalseif the current element is greater than the previous element. - If both
is_incandis_decareFalse, returnFalseas the sequence is neither strictly increasing nor strictly decreasing. - Return
Trueif eitheris_incoris_decisTrue, indicating that the sequence is either strictly increasing or strictly decreasing.
Detailed Explanation:
- Initialize variables
is_incandis_dectoTrueto indicate that the sequence is initially assumed to be both increasing and decreasing. - Iterate through the input list
numsstarting from the second element (index 1). - Check if the sequence is not both increasing and decreasing (i.e., both
is_incandis_decareFalse). If so, returnFalsesince the sequence is neither strictly increasing nor strictly decreasing. - Check if the current element (
nums[i]) is less than the previous element (nums[i-1]). If true, updateis_inctoFalsesince the sequence is no longer strictly increasing. - Check if the current element (
nums[i]) is greater than the previous element (nums[i-1]). If true, updateis_dectoFalsesince the sequence is no longer strictly decreasing. - After iterating through the entire list, if either
is_incoris_decisTrue, returnTrueindicating that the sequence is either strictly increasing or strictly decreasing. If both areFalse, returnFalse.
Complexity
Time complexity: O(n)
Space complexity: O(1)
Python
class Solution:
def isMonotonic(self, nums: List[int]) -> bool:
n = len(nums)
if n == 1: return True
is_inc = True
is_dec = True
for i in range(1, n):
if not is_inc and not is_dec:
return False
if nums[i] < nums[i-1]:
is_inc = False
if nums[i] > nums[i-1]:
is_dec = False
return is_inc or is_dec
JavaScript
/**
* @param {number[]} nums
* @return {boolean}
*/
var isMonotonic = function(nums) {
const n = nums.length;
if (n === 1) return true;
let isInc = true;
let isDec = true;
for (let i = 1; i < n; i++) {
if (!isInc && !isDec) {
return false;
}
if (nums[i] < nums[i - 1]) {
isInc = false;
}
if (nums[i] > nums[i - 1]) {
isDec = false;
}
}
return isInc || isDec;
};
Java
class Solution {
public boolean isMonotonic(int[] nums) {
int n = nums.length;
if (n == 1) return true;
boolean isInc = true;
boolean isDec = true;
for (int i = 1; i < n; i++) {
if (!isInc && !isDec) {
return false;
}
if (nums[i] < nums[i - 1]) {
isInc = false;
}
if (nums[i] > nums[i - 1]) {
isDec = false;
}
}
return isInc || isDec;
}
}
C++
class Solution {
public:
bool isMonotonic(vector<int>& nums) {
int n = nums.size();
if (n == 1) return true;
bool isInc = true;
bool isDec = true;
for (int i = 1; i < n; i++) {
if (!isInc && !isDec) {
return false;
}
if (nums[i] < nums[i - 1]) {
isInc = false;
}
if (nums[i] > nums[i - 1]) {
isDec = false;
}
}
return isInc || isDec;
}
};
Top comments (0)