Check if given Array is Monotonic
Given an array arr[] containing N integers, the task is to check whether the array is monotonic or not (monotonic means either the array is in increasing order or in decreasing order).
Examples:
Input: arr[] = {1, 2, 2, 3}
Output: Yes
Explanation: Here 1 < 2 <= 2 < 3.
The array is in increasing order. Therefore it is monotonic.Input: arr[] = {6, 5, 4, 3}
Output: Yes
Explanation: Here 6 > 5 > 4 > 3.
The array is in decreasing order. So it is monotonic.Input: arr[] = {1, 5, 2}
Output: No
Explanation: Here 1 < 5 > 2. The array is neither increasing nor decreasing.
So the array is not monotonic
Approach: The problem can be solved by checking if the array is in increasing order or in decreasing order. This can be easily done in the following way:
- If for each i in range [0, N-2], arr[i] ≥ arr[i+1] the array is in decreasing order.
- If for each i in range [0, N-2], arr[i] ≤ arr[i+1], the array is in increasing order.
Follow the below steps to solve the problem:
- Traverse the array arr[] from i = 0 to N-2 and check if the array is increasing in order
- Traverse the array arr[] from i = 0 to N-2 and check if the array is decreasing in order
- If neither of the above two is true, then the array is not monotonic.
Below is the implementation of the above approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to check array is monotonic bool check(vector< int >& arr) { int N = arr.size(); bool inc = true ; bool dec = true ; // Loop to check if array is increasing for ( int i = 0; i < N - 1; i++) { // To check if // array is not increasing if (arr[i] > arr[i + 1]) { inc = false ; } } // Loop to check if array is decreasing for ( int i = 0; i < N - 1; i++) { // To check if // array is not decreasing if (arr[i] < arr[i + 1]) { dec = false ; } } // Pick one whether inc or dec return inc || dec; } // Driver code int main() { vector< int > arr = { 1, 2, 3, 3 }; // Function call bool ans = check(arr); if (ans) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java program for above approach import java.io.*; class GFG { // Function to check array is monotonic static boolean check( int arr[]) { int N = arr.length; boolean inc = true ; boolean dec = true ; // Loop to check if array is increasing for ( int i = 0 ; i < N - 1 ; i++) { // To check if // array is not increasing if (arr[i] > arr[i + 1 ]) { inc = false ; } } // Loop to check if array is decreasing for ( int i = 0 ; i < N - 1 ; i++) { // To check if // array is not decreasing if (arr[i] < arr[i + 1 ]) { dec = false ; } } // Pick one whether inc or dec return inc || dec; } // Driver code public static void main (String[] args) { int arr[] = { 1 , 2 , 3 , 3 }; // Function call boolean ans = check(arr); if (ans == true ) System.out.print( "Yes" ); else System.out.print( "No" ); } } // This code is contributed by hrithikgarg03188. |
Python3
# Python program for above approach # Function to check array is monotonic def check(arr): N = len (arr) inc = True dec = True # Loop to check if array is increasing for i in range ( 0 , N - 1 ): # To check if array is not increasing if arr[i] > arr[i + 1 ]: inc = False # Loop to check if array is decreasing for i in range ( 0 , N - 1 ): # To check if array is not decreasing if arr[i] < arr[i + 1 ]: dec = False # Pick one whether inc or dec return inc or dec # Driver code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 , 3 ] # Function call ans = check(arr) if ans = = True : print ( "Yes" ) else : print ( "No" ) # This code is contributed by Rohit Pradhan |
C#
// C# program for above approach using System; class GFG { // Function to check array is monotonic static bool check( int [] arr) { int N = arr.Length; bool inc = true ; bool dec = true ; // Loop to check if array is increasing for ( int i = 0; i < N - 1; i++) { // To check if // array is not increasing if (arr[i] > arr[i + 1]) { inc = false ; } } // Loop to check if array is decreasing for ( int i = 0; i < N - 1; i++) { // To check if // array is not decreasing if (arr[i] < arr[i + 1]) { dec = false ; } } // Pick one whether inc or dec return (inc || dec); } // Driver code public static void Main() { int [] arr = { 1, 2, 3, 3 }; // Function call bool ans = check(arr); if (ans) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program for above approach // Function to check array is monotonic const check = (arr) => { let N = arr.length; let inc = true ; let dec = true ; // Loop to check if array is increasing for (let i = 0; i < N - 1; i++) { // To check if // array is not increasing if (arr[i] > arr[i + 1]) { inc = false ; } } // Loop to check if array is decreasing for (let i = 0; i < N - 1; i++) { // To check if // array is not decreasing if (arr[i] < arr[i + 1]) { dec = false ; } } // Pick one whether inc or dec return inc || dec; } // Driver code let arr = [1, 2, 3, 3]; // Function call let ans = check(arr); if (ans) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by rakeshsahni </script> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Another Approach: (JavaScript) In this approach JavaScript’s array method, named as every() will be used and therefore we will further check using this method that the array passed is Monotonic in nature or not.
Follow the below mentioned steps:
- Traverse the array using every() method and check whether the current element is smaller than previous element.
- Similarly again using every() method as well as with the usage of Logical OR Operator ( | | ) check whether the current element is greater than the previous element or not.
- Return true if either of the increasing sequence or the decreasing sequence is found out.
Below is the implementation of the above approach:
C++
// c++ code #include <iostream> #include <algorithm> using namespace std; // Function to check monotonic sequence bool check_monotonic( int array[], int size) { // First check for decreasing order sequence... if (is_sorted(array, array + size, greater< int >())) return true ; // Then check for increasing order sequence... if (is_sorted(array, array + size)) return true ; // Not Monotonic return false ; } // Driver Code int main() { int array1[] = { 7, 5, 3, 1 }; int array2[] = { 4, 0, 3, 1 }; int array3[] = { 5, 4, 3 }; int size1 = sizeof (array1) / sizeof (array1[0]); int size2 = sizeof (array2) / sizeof (array2[0]); int size3 = sizeof (array3) / sizeof (array3[0]); if (check_monotonic(array1, size1)) cout << "Is Monotonic ?: true\n" ; else cout << "Is Monotonic ?: false\n" ; if (check_monotonic(array2, size2)) cout << "Is Monotonic ?: true\n" ; else cout << "Is Monotonic ?: false\n" ; if (check_monotonic(array3, size3)) cout << "Is Monotonic ?: true\n" ; else cout << "Is Monotonic ?: false\n" ; return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; public class GFG { // Function to check monotonic sequence static boolean checkMonotonic( int [] array) { int size = array.length; // First check for decreasing order sequence... if (isSorted(array, size, true )) return true ; // Then check for increasing order sequence... if (isSorted(array, size, false )) return true ; // Not Monotonic return false ; } // Function to check if an array is sorted in either ascending or descending order static boolean isSorted( int [] array, int size, boolean isDescending) { if (isDescending) { for ( int i = 1 ; i < size; i++) { if (array[i] > array[i - 1 ]) return false ; } } else { for ( int i = 1 ; i < size; i++) { if (array[i] < array[i - 1 ]) return false ; } } return true ; } // Driver Code public static void main(String[] args) { int [] array1 = { 7 , 5 , 3 , 1 }; int [] array2 = { 4 , 0 , 3 , 1 }; int [] array3 = { 5 , 4 , 3 }; if (checkMonotonic(array1)) System.out.println( "Is Monotonic ?: true" ); else System.out.println( "Is Monotonic ?: false" ); if (checkMonotonic(array2)) System.out.println( "Is Monotonic ?: true" ); else System.out.println( "Is Monotonic ?: false" ); if (checkMonotonic(array3)) System.out.println( "Is Monotonic ?: true" ); else System.out.println( "Is Monotonic ?: false" ); } } |
Python3
def check_monotonic(array): return ( # First check for decreasing order sequence... all (element < = array[index - 1 ] for index, element in enumerate (array) if index > 0 ) or # Then check for increasing order sequence... all (element > = array[index - 1 ] for index, element in enumerate (array) if index > 0 ) ) print ( "Is Monotonic ?: " , check_monotonic([ 7 , 5 , 3 , 1 ])) print ( "Is Monotonic ?: " , check_monotonic([ 4 , 0 , 3 , 1 ])) print ( "Is Monotonic ?: " , check_monotonic([ 5 , 4 , 3 ])) |
Javascript
let checkMonotonic = (array) => { return ( // First check for decreasing order sequence... array.every( (element, index) => index === 0 || element <= array[index - 1] ) || // Then check for increasing order sequence... array.every((element, index) => index === 0 || element >= array[index - 1]) ); }; console.log( "Is Monotonic ?: " + checkMonotonic([7, 5, 3, 1])); console.log( "Is Monotonic ?: " + checkMonotonic([4, 0, 3, 1])); console.log( "Is Monotonic ?: " + checkMonotonic([5, 4, 3])); // This code is contributed by Aman Singla... |
C#
using System; using System.Linq; class Gfg { static void Main() { int [] array1 = { 7, 5, 3, 1 }; int [] array2 = { 4, 0, 3, 1 }; int [] array3 = { 5, 4, 3 }; Console.WriteLine( "Is Monotonic ?: " + checkMonotonic(array1)); Console.WriteLine( "Is Monotonic ?: " + checkMonotonic(array2)); Console.WriteLine( "Is Monotonic ?: " + checkMonotonic(array3)); } static bool checkMonotonic( int [] array) { return ( // First check for decreasing order sequence... array.Take(1).Count() == array.Length || Enumerable.Range(1, array.Length - 1).All(i => array[i] <= array[i - 1]) || // Then check for increasing order sequence... Enumerable.Range(1, array.Length - 1).All(i => array[i] >= array[i - 1]) ); } } |
Is Monotonic ?: true Is Monotonic ?: false Is Monotonic ?: true
Time Complexity: O(NlogN), as the time complexity of the is_sorted() function in the standard library is O(NlogN), where N is the size of the array.
Auxiliary Space: O(1), as it requires constant extra space for storing the size of the array.