# Monotonic Array Problem

For the monotonic increasing array, we need to check if the previous index is less than the current index. And for the monotonic decreasing array, we need to check if the previous index is greater than the current index.

An array is monotonic if it is either increasing or monotonic decreasing.

### Introduction

An array `A`

is monotone increasing if for all `i <= j`

, `A[i] <= A[j]`

.

An array `A`

is monotone decreasing if for all `i <= j`

, `A[i] >= A[j]`

, return `true`

if and only if the given array `A`

is monotonic.

**Example 1:**

```
Input:[1, 2, 2, 4]
Output: true
```

**Example 2:**

```
Input:[1, 2, 6, 2, 3]
Output: false
```

**Example 3:**

```
Input: [7, 2, 1]
Output: true
```

### Thought Process

An `array`

is called **monotonic** if the `index`

of each element increases from the first to the last, or if it decreases from the first to the last.

### Algorithm

We need to run two for loops to check if either of the loops returns true.

For the monotonic increasing array, we need to check if the previous index is less than the current index. And for the monotonic decreasing array, we need to check if the previous index is greater than the current index.

Finally, we return `true`

if either of the loops evaluates to `true`

.

Optimal way:we can do this using one pass but let us take a look at both algorithms.

## Solution

### Approach#1: Two-Pass Algorithm

*Code*: Monotonic Array: Two-Pass

```
public class MonotonicArray {
public static void main(String[] args) {
int[] input = {1, 2, 2, 3};
System.out.println(isMonotonic(input)); // true
}
public static boolean isMonotonic(int[] array) {
return isIncreasing(array) || isDecreasing(array);
}
public static boolean isIncreasing(int[] nums) {
for (int i = 1; i < nums.length; i++)
if (nums[i - 1] > nums[i]) {
return false;
}
return true;
}
public static boolean isDecreasing(int[] nums) {
for (int i = 1; i < nums.length; i++)
if (nums[i - 1] < nums[i]) {
return false;
}
return true;
}
}
```

**Complexity** **Analysis**

We are doing two for loops above, and the overall time complexity is `O(n)`

, and space complexity is `O(1)`

.

Let us optimize the above code snippet with a single loop.

### Approach#2: One-Pass Algorithm

**Code:** **Monotonic Array: One-Pass**

```
public class MonotonicArray {
public static void main(String[] args) {
int[] input = {1, 2, 2, 3};
System.out.println(isMonotonic(input)); // true
}
public static boolean isMonotonic(int[] array) {
boolean isIncreasing = true;
boolean isDecreasing = true;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
isDecreasing = false;
}
if (array[i] > array[i - 1]) {
isIncreasing = false;
}
}
return isIncreasing || isDecreasing;
}
}
```

**Complexity Analysis**

Overall complexity analysis won’t change, but this optimised approach eliminates a loop here.

Hence, the complexity analysis for both approaches are time – `O(n)`

and space – `O(1)`

.