Wednesday, May 18, 2022

Easy_Question21 :Monotonic Array

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

An array nums is monotone increasing if for all i <= jnums[i] <= nums[j]. An array nums is monotone decreasing if for all i <= jnums[i] >= nums[j].

Given an integer array nums, return true if the given array is monotonic, or false otherwise.

Example 1:

Input: nums = [1,2,2,3]
Output: true

Example 2:

Input: nums = [6,5,4,4]
Output: true

Example 3:

Input: nums = [1,3,2]
Output: false

 

Constraints:

  • 1 <= nums.length <= 105
  • -105 <= nums[i] <= 105

Approach 1: Two Pass

class Solution { public boolean isMonotonic(int[] A) { return increasing(A) || decreasing(A); } public boolean increasing(int[] A) { for (int i = 0; i < A.length - 1; ++i) if (A[i] > A[i+1]) return false; return true; } public boolean decreasing(int[] A) { for (int i = 0; i < A.length - 1; ++i) if (A[i] < A[i+1]) return false; return true; } }
Complexity Analysis
Time Complexity: O(N), where NN is the length of A.
Space Complexity: O(1)

Approach 2: One Pass
Algorithm

Keep track of store, equal to the first non-zero comparison seen (if it exists.) If we see the opposite comparison, the answer is False.

Otherwise, every comparison was (necessarily) in the set \{-1, 0\}{−1,0}, or every comparison was in the set \{0, 1\}{0,1}, and therefore the array is monotonic.
class Solution { public boolean isMonotonic(int[] A) { int store = 0; for (int i = 0; i < A.length - 1; ++i) { int c = Integer.compare(A[i], A[i+1]); if (c != 0) { if (c != store && store != 0) return false; store = c; } } return true; } }
Complexity Analysis
Time Complexity: O(N), where NN is the length of A.
Space Complexity: O(1)

Approach 3: One Pass (Simple Variant)
class Solution { public boolean isMonotonic(int[] A) { boolean increasing = true; boolean decreasing = true; for (int i = 0; i < A.length - 1; ++i) { if (A[i] > A[i+1]) increasing = false; if (A[i] < A[i+1]) decreasing = false; } return increasing || decreasing; } }

Complexity Analysis
Time Complexity: O(N) where NN is the length of A.
Space Complexity: O(1)

You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS