Monotonic Array - Leetcode Solution

Problem Description:

Given an array of integers, determine whether the array is monotonic or not. An array is monotonic if it is either monotone increasing or monotone decreasing.

Example 1: Input: [1,2,2,3] Output: true

Example 2: Input: [6,5,4,4] Output: true

Example 3: Input: [1,3,2] Output: false

Solution:

To solve the given problem, we need to understand the meaning of a monotonic array. A monotonic array is the one in which the elements are either increasing or decreasing. Hence, there can only two possible cases for the monotonic array - either monotone increasing or monotone decreasing. If the array does not have either of these characteristics, the array is not monotonic.

The approach to solve this problem can be divided into two main parts. First, we will check if the array is monotone increasing, and if not, we will check if the array is monotone decreasing. We will start by checking if the array is monotone increasing.

For a monotone increasing array, the condition is that the adjacent element in the array must be greater than or equal to the previous element in the array. We will iterate through the array and check if the current element is greater than or equal to the previous element in the array. If all the elements in the array follow this condition, we can say that the array is monotone increasing and return true. If at any point, this condition is not satisfied, we will move to the next step to check if the array is monotone decreasing.

For a monotone decreasing array, the condition is that the adjacent element in the array must be lesser than or equal to the previous element in the array. We will iterate through the array and check if the current element is lesser than or equal to the previous element in the array. If all the elements in the array follow this condition, we can say that the array is monotone decreasing and return true. If at any point, this condition is not satisfied, we will return false as the array is not monotonic.

Pseudo Code:

isMonotonic(array): isIncreasing = true isDecreasing = true

for i = 0 to length of array - 2:
    if array[i] > array[i+1]:
        isIncreasing = false
        
    if array[i] < array[i+1]:
        isDecreasing = false
        
if isIncreasing or isDecreasing:
    return true

return false

Time Complexity:

The time complexity of the above algorithm is O(N), where N is the length of the input array. The algorithm needs to traverse the input array only once to determine whether the array is monotonic or not.

Space Complexity:

The space complexity of the above algorithm is O(1). We are not using any extra space to solve this problem. We are just using two Boolean variables to keep track of whether the array is monotone increasing or monotone decreasing or not, which does not incur any significant space.

1