Monotonic Array Problem

An array is monotonic if it is either increasing or monotonic decreasing.

Introduction

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, 4]

Output: true

Example 2:

Input:[1, 2, 6, 2, 3]

Output: false

Example 3:

Input: [7, 2, 1]

Output: true

Thought Process

An array is called monotonic if the index of each element increases from the first to the last, or if it decreases from the first to the last.

Algorithm

We need to run two for loops to check if either of the loops returns true.

For the monotonic increasing array, we need to check if the previous index is less than the current index. And for the monotonic decreasing array, we need to check if the previous index is greater than the current index.

Finally, we return true if either of the loops evaluates to true.

Optimal way: we can do this using one pass but let us take a look at both algorithms.

Solution

Approach#1: Two-Pass Algorithm

Code: Monotonic Array: Two-Pass

public class MonotonicArray {
  public static void main(String[] args) {
    int[] input = {1, 2, 2, 3};
    System.out.println(isMonotonic(input)); // true
  }

  public static boolean isMonotonic(int[] array) {
    return isIncreasing(array) || isDecreasing(array);
  }

  public static boolean isIncreasing(int[] nums) {
    for (int i = 1; i < nums.length; i++)
      if (nums[i - 1] > nums[i]) {
        return false;
      }
    return true;
  }

  public static boolean isDecreasing(int[] nums) {
    for (int i = 1; i < nums.length; i++)
      if (nums[i - 1] < nums[i]) {
        return false;
      }
    return true;
  }
}

Complexity Analysis

We are doing two for loops above, and the overall time complexity is O(n), and space complexity is O(1).

Let us optimize the above code snippet with a single loop.

Approach#2: One-Pass Algorithm

Code: Monotonic Array: One-Pass

public class MonotonicArray {
  public static void main(String[] args) {
    int[] input = {1, 2, 2, 3};
    System.out.println(isMonotonic(input)); // true
  }

  public static boolean isMonotonic(int[] array) {
    boolean isIncreasing = true;
    boolean isDecreasing = true;

    for (int i = 1; i < array.length; i++) {
      if (array[i] < array[i - 1]) {
        isDecreasing = false;
      }

      if (array[i] > array[i - 1]) {
        isIncreasing = false;
      }
    }

    return isIncreasing || isDecreasing;
  }
}

Complexity Analysis

Overall complexity analysis won’t change, but this optimised approach eliminates a loop here.

Hence, the complexity analysis for both approaches are time – O(n) and space – O(1).