Monotonic Array

A monotonic array is one that is either entirely non-increasing or non-decreasing. That is, the elements either always increase or always decrease.

For example:

[1, 2, 4, 6, 8] is monotonic increasing [8, 6, 4, 2, 1] is monotonic decreasing

Java example to check if monotonic:

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

boolean isMonotonic(int[] arr) {
  boolean increasing = true;
  boolean decreasing = true;

  for (int i = 0; i < arr.length - 1; i++) {
    if (arr[i] > arr[i+1]) {
      increasing = false;
    }
    if (arr[i] < arr[i+1]) { 
      decreasing = false;
    }
  }

  return increasing || decreasing;
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

bool isMonotonic(vector<int>& arr) {
  bool inc = true, dec = true;

  for (int i = 0; i < arr.size() - 1; i++) {
    if (arr[i] > arr[i+1]) inc = false; 
    if (arr[i] < arr[i+1]) dec = false;
  }

  return inc || dec;
}

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def is_monotonic(arr):
  
  increasing = decreasing = True

  for i in range(len(arr) - 1):  
    if arr[i] < arr[i+1]:
      decreasing = False
    if arr[i] > arr[i+1]:
      increasing = False

  return increasing or decreasing

Monotonicity allows optimizing certain array algorithms. Useful for bounding and binary search.

To determine if an array is monotonic (either increasing or decreasing), we can simply iterate through the array and track the increasing and decreasing trends.

Approach:

  1. Initialize Variables: Create two variables increasing and decreasing and set them to True.
  2. Iterate Through the Array: Loop through the array from index 1 to len(nums) - 1.
  3. Check Monotonicity: Compare nums[i] with nums[i-1]:
    • If nums[i] < nums[i-1], set increasing to False.
    • If nums[i] > nums[i-1], set decreasing to False.
  4. Final Check: If either increasing or decreasing is True, return True. Otherwise, return False.

Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        increasing = decreasing = True

        for i in range(1, len(nums)):
            if nums[i] < nums[i-1]:
                increasing = False
            if nums[i] > nums[i-1]:
                decreasing = False

        return increasing or decreasing

Example:

  • Input: nums = [1,2,2,3]
  • Output: true
  • Explanation: The array is monotone increasing since every element is less than or equal to the next element.

Insights:

  • Time Complexity: The time complexity is (O(n)), where (n) is the length of the array.
  • Space Complexity: The space complexity is (O(1)) since we are using only a constant amount of space.
  • One-Pass Algorithm: This solution efficiently checks both monotonic increasing and decreasing trends in a single pass through the array.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def check(a)
  a.each_with_index do |element, index|
    break if index == a.size-1
    if yield(a[index], a[index+1])
      return false
    end
  end
  return true  
end

def is_increasing(a)
  check(a) do |x, y|
    if x < y
      return false
    end      
  end
end

def is_decreasing(a)
  check(a) do |x, y|
    if x > y
      return false
    end      
  end
end
# @param {Integer[]} a
# @return {Boolean}
def is_monotonic(a)
  is_increasing(a) || is_decreasing(a)
end