How to check if a given array is Monotonic in Python, Java, C, C++, JavaScript
In programming, a monotonic array is an array that is either entirely non-increasing or non-decreasing. Understanding whether an array is monotonic can be useful in various algorithms and data processing tasks. In this article, we’ll explore how to check if a given array is monotonic in multiple programming languages, including Python, Java, C, C++, and JavaScript. We’ll also discuss the concept of monotonic arrays and provide code examples and explanations for each language.
Article Contents
What is a Monotonic Array?
An array is considered monotonic if it is either:
- Non-increasing: Each element is greater than or equal to the following element.
- Non-decreasing: Each element is less than or equal to the following element.
For example, the arrays [1, 2, 2, 3] and [5, 4, 4, 3] are both monotonic.
Why Check for Monotonicity?
Checking for monotonicity can be beneficial in scenarios such as:
- Sorting Algorithms: Optimizing the performance of sorting algorithms.
- Data Analysis: Analyzing trends in datasets.
- Algorithm Design: Creating efficient algorithms that rely on sorted data.
How to check if a Given Array is Monotonic
To check if an array is monotonic, we can use a straightforward approach. The algorithm involves iterating through the array and comparing adjacent elements. If we find any pair of elements that violates the monotonic condition, we can conclude that the array is not monotonic.
Python Implementation:
Here’s a simple implementation to check if a given array is Monotonic in Python:
def is_monotonic(arr):
increasing = decreasing = True
for i in range(1, len(arr)):
if arr[i] > arr[i - 1]:
decreasing = False
elif arr[i] < arr[i - 1]:
increasing = False
return increasing or decreasing
# Example Usage
arr = [1, 2, 2, 3]
print(is_monotonic(arr)) # Output: True
Java Implementation:
To check if a given Array is Monotonic in Java, we can implement the same logic using a method:
public class MonotonicArray {
public static boolean isMonotonic(int[] arr) {
boolean increasing = true;
boolean decreasing = true;
for (int i = 1; i < arr.length; i++) {
if (arr[i] > arr[i - 1]) {
decreasing = false;
} else if (arr[i] < arr[i - 1]) {
increasing = false;
}
}
return increasing || decreasing;
}
public static void main(String[] args) {
int[] arr = {1, 2, 2, 3};
System.out.println(isMonotonic(arr)); // Output: true
}
}
C Implementation
To check if a given Array is Monotonic in C, we can achieve the same result using a function:
#include <stdio.h>
#include <stdbool.h>bool isMonotonic(int arr[], int n) {
bool increasing = true;
bool decreasing = true;for (int i = 1; i < n; i++) {
if (arr[i] > arr[i - 1]) {
decreasing = false;
} else if (arr[i] < arr[i - 1]) {
increasing = false;
}
}return increasing || decreasing;
}int main() {
int arr[] = {1, 2, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
printf("%s\n", isMonotonic(arr, n) ? "True" : "False"); // Output: True
return 0;
}
C++ Implementation
To check if a given Array is Monotonic in C++, the implementation is quite similar to C:
#include <iostream>
#include <vector>
using namespace std;
bool isMonotonic(const vector<int>& arr) {
bool increasing = true;
bool decreasing = true;
for (size_t i = 1; i < arr.size(); i++) {
if (arr[i] > arr[i - 1]) {
decreasing = false;
} else if (arr[i] < arr[i - 1]) {
increasing = false;
}
}
return increasing || decreasing;
}
int main() {
vector<int> arr = {1, 2, 2, 3};
cout << (isMonotonic(arr) ? "True" : "False") << endl; // Output: True
return 0;
}
JavaScript Implementation
Finally, let’s look at how to implement this to check if a given Array is Monotonic in JavaScript:
function isMonotonic(arr) {
let increasing = true;
let decreasing = true;
for (let i = 1; i < arr.length; i++) {
if (arr[i] > arr[i - 1]) {
decreasing = false;
} else if (arr[i] < arr[i - 1]) {
increasing = false;
}
}
return increasing || decreasing;
}
// Example Usage
const arr = [1, 2, 2, 3];
console.log(isMonotonic(arr)); // Output: true
Time Complexity Analysis
The time complexity for all implementations is O(n), where n is the number of elements in the array. This is because we make a single pass through the array to check the monotonic condition. The space complexity is O(1), as we are using only a few variables to store state information.
Conclusion
In this article, we explored how to check if a given array is monotonic across five different programming languages: Python, Java, C, C++, and JavaScript. Monotonicity is a valuable property in various computational tasks, and recognizing it can lead to optimizations in algorithms. The implementations provided demonstrate a simple and efficient way to determine if an array meets the monotonic condition.
