Monotonic Array

Posted in

Vinay Khatri
Last updated on December 4, 2023

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``