Skip to content

Check If the Given Array Is Monotonic

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

Gopi Gorantala
Gopi Gorantala
2 min read
Monotonic Array
Monotonic Array

Table of Contents

Introduction

A monotonic array is an array it is either increasing or monotonic decreasing.

Monotonic Chart
Monotonic Chart

Problem Statement

An array A is monotone increasing(📈) if for all i <= j, A[i] <= A[j], where i and j are index elements.

An array A is monotone decreasing (📉) if for all i >= j, A[i] >= A[j]. true is returned if and only if the given array A is monotonic.

Explanation:

Monotone increasing: An array A is called monotone increasing if the first number is less than or equal to the second number, the second number is less than or equal to the third number, and so on, and vice versa.

Monotone decreasing: An array A is called monotone decreasing if the first number is greater than or equal to the second number, the second number is greater than or equal to the third number, and so on, and vice versa.

Example 1:

  Input: [1, 2, 2, 3]  
  
  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 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 must check if the previous index is less than the current one. And for the monotonic decreasing array, we must check if the previous index is greater than the current one.

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

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

Intuition

There are different ways to solve this problem, but the one that is simple yet powerful are:

  1. Two-pass approach
  2. One-pass approach

Two-pass approach

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; the overall time complexity is O(n), and the space complexity is O(1).

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

One-Pass approach

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 we are eliminating a loop with this optimized approach.

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

Coding Interview Questions

Gopi Gorantala Twitter

Gopi has been a Full Stack(Java+React) since 2016. He worked in Europe, and India, from startups to tech giants. He has a strong engineering professional with a Bachelor's in Satellite Communications.

Comments


Related Posts

Members Public

Two Sum Problem

In this two-sum problem, we use various approaches to solve the problem from brute force to an optimized approach. We also discuss the take-offs and talk about complexity analysis.

Members Public

Solution Review: Get the First Set Bit Position Using the Right Shift

In the kth bit set/unset problem, we first write the algorithm, then some pseudocode, and then implement the solution.

Members Public

Challenge 1: Get the First Set Bit Position Using the Right Shift

This problem is similar to the last lesson we discussed. If you need a clue, return to the previous lesson to further your understanding.