Monotonic Array

---

Intuition

• Can simply check in two passes for if all elements are increasing, then if all elements are decreasing.
• Alternatively, can do in one pass, noticing that if the elements aren’t increasing, then they are decreasing, and that in no circumstance should you go from increasing to decreasing or vice versa.

Complexity

Runtime

$O(N)$

Space

$O(1)$

Code

Small Improvement

class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        increasing = False
        decreasing = False
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                continue
            elif nums[i] > nums[i - 1]:
                if decreasing:
                    return False
                increasing = True
            else:
                if increasing:
                    return False
                decreasing = True
        
        return not (increasing and decreasing)

• Can return immediately if you go from increasing to decreasing or vice versa.

One Pass

class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        increasing = False
        decreasing = False
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                continue
            elif nums[i] > nums[i - 1]:
                increasing = True
            else:
                decreasing = True
        
        return not (increasing and decreasing)

• not (increasing and decreasing)
  • not increasing or not decreasing
  • i.e. one or the other can increase, but not both

Two Passes

class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        increasing = True
        for i in range(1, len(nums)):
            # Increasing
            if nums[i] >= nums[i - 1]:
                continue
            increasing = False
            break
        
        if increasing:
            return True
 
        for i in range(1, len(nums)):
            # Decreasing
            if nums[i] <= nums[i - 1]:
                continue
            return False
        return True

Cards

START Basic Front: Monotonic Array Back: If elements aren’t increasing, then they are decreasing.

END

---

References

• Monotonic Array