Monotonic Array LeetCode Solution

Difficulty Level Easy
Frequently asked in Amazon Facebook
algorithms Array coding Interview interviewprep LeetCode LeetCodeSolutionsViews 5364

Problem statement

In the problem “Monotonic Array” we are given an array. Our task is to check if the array is a monotonic array or not.

A monotonic array is an array where elements are either sorted in increasing order or in decreasing order. If the array is sorted in increasing order then for an array arr[], arr[i]<=arr[i+1]. For an array sorted in decreasing order, arr[i]>=arr[i+1].

The function should return true only when the array is monotonic. Otherwise, return false.

Example

arr={1,2,4,5}
true

Explanation:  In the given array for each i arr[i]<arr[i+1], so it is sorted in increasing order. The output is true because an increasing array is a monotonic array.

Approach

To solve this problem it is very important to understand clearly what is monotonic array.

a monotonic array is an array in which if we plot a graph between index number and value at that index of the array then it forms either monotonic increasing or decreasing graph. The image below shows a monotonic increasing and decreasing graph.

leetcode solution to Monotonic Array

The approach to this problem is like, we will traverse the array and check if it is an increasing array by checking arr[i]<=arr[i+1]. If it is an increasing array then the given array is a monotonic array else we will traverse the array again and check if it is a decreasing array by checking if arr[i]>=arr[i+1]. If it is a decreasing array then the given array is a monotonic array else it is not a monotonic array.

We can also check if the array is increasing or decreasing using only a single traversal. We will use two flags isincr and isdec and initialize it with true. If A[i] > A[i+1]  then isincr will become false and if A[i] < A[i+1] then isdec will become false. if the array is monotonic then at least one of isincr and isdec will be true. When both are false means the array is not monotonic as both false values suggest that the value in the array is both increasing and decreasing.

 

Code

C++ Monotonic Array LeetCode Solution

#include <bits/stdc++.h> 
using namespace std; 
        bool isMonotonic(vector<int>& A) {
        bool isincr = true;
        bool isdec = true;
        int n=A.size();
        for (int i = 0; i < n- 1; ++i) {
            if (A[i] > A[i+1])
                isincr = false;
            if (A[i] < A[i+1])
               isdec = false;
        }

        return isincr || isdec;   
    }

int main() 
{ 
 vector<int> arr = {1,2,4,5}; 
 cout <<boolalpha;
 cout<<isMonotonic(arr)<<endl; 
 return 0;
}
true

Java Monotonic Array LeetCode Solution

import java.util.Arrays; 
public class Tutorialcup {
    public  static  boolean isMonotonic(int[] A) {
        boolean isincr = true;
        boolean isdec = true;
        int n=A.length;
        for (int i = 0; i < n- 1; ++i) {
            if (A[i] > A[i+1])
                isincr = false;
            if (A[i] < A[i+1])
               isdec = false;
        }

        return isincr || isdec;   
}
  public static void main(String[] args) {
    int [] arr = {1,2,4,5}; 
    boolean ans= isMonotonic(arr);
    System.out.println(ans);
  }
}
true

Complexity Analysis of Monotonic Array

Time complexity

The time complexity of the above code is O(n) because we are only traversing the array once to check if it is a monotonic array or not. Here n is the size of the input array.

Space complexity

The space complexity of the above code is O(1) because we are using only a variable to store answers.

References

Translate »