【Video】896. Monotonic Array - Python, JavaScript, Java and C++
Tags: leetcode, python, javascript, java
Published: 2023-09-29 14:02:18

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](https://youtu.be/UVEDSDDSP-U)

### ⭐️⭐️ 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:
1. Initialize variables `is_inc` and `is_dec` to `True` to track whether the sequence is increasing or decreasing.
2. Iterate through the input list `nums` starting from the second element.
3. Update `is_inc` to `False` if the current element is less than the previous element.
4. Update `is_dec` to `False` if the current element is greater than the previous element.
5. If both `is_inc` and `is_dec` are `False`, return `False` as the sequence is neither strictly increasing nor strictly decreasing.
6. Return `True` if either `is_inc` or `is_dec` is `True`, indicating that the sequence is either strictly increasing or strictly decreasing.

Detailed Explanation:
1. Initialize variables `is_inc` and `is_dec` to `True` to indicate that the sequence is initially assumed to be both increasing and decreasing.
2. Iterate through the input list `nums` starting from the second element (index 1).
3. Check if the sequence is not both increasing and decreasing (i.e., both `is_inc` and `is_dec` are `False`). If so, return `False` since the sequence is neither strictly increasing nor strictly decreasing.
4. Check if the current element (`nums[i]`) is less than the previous element (`nums[i-1]`). If true, update `is_inc` to `False` since the sequence is no longer strictly increasing.
5. Check if the current element (`nums[i]`) is greater than the previous element (`nums[i-1]`). If true, update `is_dec` to `False` since the sequence is no longer strictly decreasing.
6. After iterating through the entire list, if either `is_inc` or `is_dec` is `True`, return `True` indicating that the sequence is either strictly increasing or strictly decreasing. If both are `False`, return `False`.

---


# 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;        
    }
};
```