Monotonic Array | discussion and solution

November 10, 2020   Interview Questions

An array is called a monotonic array if it is either monotone growing or monotone shrinking. In simple words, if your array is either in non-increasing order or nor-decreasing order then this type of array is called a monotonic array.

Example:

{1,2,2,3,4,5,6} -> This is a monotonic array (Non-decreasing)
{1,4,6,3,4,3,6} -> This array is not a monotonic array
{7,6,5,4,4,3,1} -> This is a monotonic array (Non-increasing)

Algorithmic Definition

An array A is monotone growing if for all i <= j, A[i] <= A[j]. An array A is a monotone shrinking if for all i <= j, A[i] >= A[j]..

Approach to find montonic array

You can solve this problem by using various techniques. The solution to the problem is not that complex as you are considering. It’s just a little bit tricky. Before addressing, the solution let’s initially examine the problem. By observing we can assume that if you find a non-decreasing or non-increasing component we reach our solution by stating it as a non-monotonic problem.

So How we find an un-matching element in the array. You can tackle this difficulty using two pointers while iterating the array. We use two pointers i and j where i is following j we compare values at ith and jth index and using that result we further analyze the next element in the array with our result if it meets the function requirement. we further iterate the array else we break the loop and return the contemporary status of the function to the user.

Algorithm for monotonic array

1. initiate j =1 ; status= 2 (non-monotonic)
2. iterate a for loop from zero to size of the array-1;
3. if j will become less then i or equal to the size of the array return the current status.
4.  else if the value at  i is greater than the value at j. Mark status = 0.
   • if the value at j+1 is greater than the value at j or status =1. Mark status=2 and return it. else increase j by 1.
5. else if the value at i is less than the value at j. Mark status = 1
   • if the value at j+1 is less than the value at j or status =0. Mark status=2 and return it. else increase j by 1
6. else increase j by 1.
7. do all 4,5,6 until 3 is not true.
8. return the status.

Implementation of the monotonic array in c++

/*  Monotonic array :
    If an array is entriely non-decreasing 
             or non-increasing order
    Problem description :
    you have given array find if it is monotonic or not..
    */
#include<iostream>
#include<vector>
int isMonotoinc(std::vector<int>v)
{
    int j=1;
    // 2=> null direction  0=> decreasing 1=> increasing
    int status=2; 
    for(int i=0;i<v.size();i++)
    {
        if(j<=i || j>=v.size()){
            break;
        }
        else if(v.at(i)>v.at(j)){
            status=0;
            if(v.at(j+1)>v.at(j) || status ==1){
               status=2;
                return status;
            }
            j++;
        }
        else if(v.at(i)<v.at(j)){
            status=1;
            if(v.at(j+1)<v.at(j) || status ==0){
                flag=2;
                return status;
            }
            j++;
        }
        else
            {
            j++;
        }
    }
    return status;
}
int main(){
    std::vector<int>v1={1,2,2,3,4,5,6,6};
    if(isMonotoinc(v1)==1) {
        std::cout << " IT is non decreasing";
    }
    else if(isMonotoinc(v1)==0){
    std::cout << " IT is non  Increasing";
}
    else{
        std::cout << " IT is not monolotic";
    }
}