【Video】896. Monotonic Array - Python, JavaScript, Java and C++

Kensuke — Fri, 29 Sep 2023 14:02:18 +0000

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_inc and is_dec to True to track whether the sequence is increasing or decreasing.
Iterate through the input list nums starting from the second element.
Update is_inc to False if the current element is less than the previous element.
Update is_dec to False if the current element is greater than the previous element.
If both is_inc and is_dec are False, return False as the sequence is neither strictly increasing nor strictly decreasing.
Return True if either is_inc or is_dec is True, indicating that the sequence is either strictly increasing or strictly decreasing.

Detailed Explanation:

Initialize variables is_inc and is_dec to True to indicate that the sequence is initially assumed to be both increasing and decreasing.
Iterate through the input list nums starting from the second element (index 1).
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.
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.
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.
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;        
    }
};