Monotonic Array - Java Solution
Tags: faang, leetcode, algorithms, programming
Published: 2022-02-18 16:54:50

## Introduction

A monotonic Array is an array if it is either increasing or monotonic decreasing. 

## Problem Statement
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:**

```javascript
  Input: [1, 2, 2, 3]

  Output: true
```

**Example 2:**

```javascript
  Input: [1, 2, 6, 2, 3]

  Output: false
```

**Example 3:**

```javascript
  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 its decreasing 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 using one pass but let us take a look at both the algorithms.

## Solution

### Approach 01: Two-Pass Algorithm

```java
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 02: One-Pass Algorithm

```java
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 we are eliminating a loop here with this optimized approach.

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

---

## Extras

If you are interested in mastering bit tricks, I've got a course that are loved by more than 100k+ programmers. 

In this course, you will learn how to solve problems using bit manipulation, a powerful technique that can be used to optimize your algorithmic and problem-solving skills. The course has simple explanation with sketches, detailed step-by-step drawings, and various ways to solve it using bitwise operators. 

These bit-tricks could help in competitive programming and coding interviews in running algorithms mostly in `O(1)` time.

This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG(Facebook, Amazon, Apple, Netflix, and Google) companies.

To kick things off, you’ll start by learning about the number system and how it’s represented. Then you’ll move on to learn about the six different bitwise operators: AND, OR, NOT, XOR, and bit shifting. Throughout, you will get tons of hands-on experience working through practice problems to help sharpen your understanding.

By the time you’ve completed this course, you will be able to solve problems faster with greater efficiency!! 🤩

Link to my course: [Master Bit Manipulation for Coding Interviews](https://www.educative.io/courses/bit-manipulation?aff=xjzd).