Monotonic Array

Problem

Given an array. Check if it is monotonic increasing or decreasing. An array is monotonic increasing if for all i<=j, a[i]<=a[j]. An array is monotonic decreasing if for all i<=j, a[i]>=a[j]

Sample Input

1 2 2

Sample Output

True

Explanation

1 <= 2 <= 2 for indexes 0 < 1 < 2

Approach

We can initialize two variables with a boolean value of true. We iterate the array and for all ‘i’, keep doing bitwise AND of the variables with arr[i] >= arr[i] and arr[i] <= arr[i], respectively. We did bitwise AND because if the condition of monotonicity is false, then the variables will be 0, otherwise, either or both of both will be 1.

Complexity Analysis

The time complexity is O(N) with no extra space required

C++ Programming

#include <iostream>
#include<vector>

using namespace std;

// function to check if array is monotonic
bool isMonotonic(vector<int> arr) {
        bool inc = true, dec = true;

        // iterate the array
        for (int i = 1; i < arr.size(); ++i)
        {
            // keep doing bitwise AND according to monotonicity condition
            inc &= arr[i - 1] <= arr[i], dec &= arr[i - 1] >= arr[i];
        }
        return inc || dec;
    }

int main() {
    vector<int> arr{1, 2, 2};
    if(isMonotonic(arr))
      { cout<<"True";}
    else
      { cout<<"False";}
}

Output

True

Java Programming

import java.io.*;

class Solution {

  // function to check if array is monotonic
  public static boolean isMonotonic(int[] A) {
    boolean inc = true, dec = true;

    // iterate the array
    for (int i = 1; i < A.length; ++i) {
      // keep doing bitwise AND according to monotonicity condition
      inc &= A[i - 1] <= A[i];
      dec &= A[i - 1] >= A[i];
    }
    return inc || dec;
  }

  public static void main(String[] args) {

    int[] A = {1, 2, 2};

    System.out.println(isMonotonic(A));
  }
}

Output

true

Python Programming

# function to check if array is monotonic
def isMonotonic(arr):
    inc = True
    dec = True

    # iterate the list
    for i in range(1,len(arr)):
        # keep doing bitwise AND according to monotonicity condition
        inc &= arr[i-1] <= arr[i]
        dec &= arr[i-1] >= arr[i]

    return inc or dec

arr = [1, 2, 2]

print(isMonotonic(arr))

Output

True

People are also reading:

• Binary Gap
• Arranging Coins
• Maximum Units
• Missing Numbers
• Mountain Array
• What is Pseudocode?
• Pass by Reference vs Pass by Pointer in C++
• Delete Nodes and Return Forest
• Find MSB in O(1)
• Nth Root of M