Monotonic Array

Posted in

Monotonic Array
vinaykhatri

Vinay Khatri
Last updated on March 29, 2024

    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:

    Leave a Comment on this Post

    0 Comments