Teaching Kids Programming – Algorithm to Check If Array is Monotonic

Teaching Kids Programming: Videos on Data Structures and Algorithms

An array is monotonic if it is either monotone increasing or monotone decreasing. An array A is monotone increasing if for all i <= j, A[i] <= A[j]. An array A is monotone decreasing if for all i <= j, A[i] >= A[j].

Return true if and only if the given array A is monotonic.

Example 1:
Input: [1,2,2,3]
Output: true

Example 2:
Input: [6,5,4,4]
Output: true

Example 3:
Input: [1,3,2]
Output: false

Example 4:
Input: [1,2,4,5]
Output: true

Example 5:
Input: [1,1,1]
Output: true

Check Monotonic Array Algorithm

We can set two flags to True which indicates array monotonic increase or decreasing. Go through the array one pass and by comparing every two neighbouring elements, if it is decreasing, we set the increasing flag to false, and if it is increasing we set the decreasing flag to false. At the end, if either increasing or decreasing, we return true.

1
2
3
4
5
6
7
8
9

class Solution:
    def isMonotonic(self, A: List[int]) -> bool:
        increasing = decreasing = True
        for i in range(len(A) - 1):
            if A[i] > A[i+1]:
                increasing = False
            if A[i] < A[i+1]:
                decreasing = False
        return increasing or decreasing        

class Solution:
    def isMonotonic(self, A: List[int]) -> bool:
        increasing = decreasing = True
        for i in range(len(A) - 1):
            if A[i] > A[i+1]:
                increasing = False
            if A[i] < A[i+1]:
                decreasing = False
        return increasing or decreasing        

The time complexity is O(N) one pass. The space complexity is O(1). Alternatively, you can do the checks in two passes: is the array either monotonic increasing or monotonic decreasing.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def increasing(self, A: List[int]) -> bool:
        for i in range(len(A) - 1):
            if A[i] > A[i+1]:
                return False
        return True        
    
    def decreasing(self, A: List[int]) -> bool:
        for i in range(len(A) - 1):
            if A[i] < A[i+1]:
                return False
        return True        
    
    def isMonotonic(self, A: List[int]) -> bool:
        return self.increasing(A) or self.decreasing(A)

class Solution:
    def increasing(self, A: List[int]) -> bool:
        for i in range(len(A) - 1):
            if A[i] > A[i+1]:
                return False
        return True        
    
    def decreasing(self, A: List[int]) -> bool:
        for i in range(len(A) - 1):
            if A[i] < A[i+1]:
                return False
        return True        
    
    def isMonotonic(self, A: List[int]) -> bool:
        return self.increasing(A) or self.decreasing(A)

–EOF (The Ultimate Computing & Technology Blog) —