algoadvance

Leetcode 896. Monotonic Array

Problem Statement

A monotonic array is an array that is either entirely non-increasing or non-decreasing.

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

Examples:

  1. Input: nums = [1,2,2,3] Output: true
  2. Input: nums = [6,5,4,4] Output: true
  3. Input: nums = [1,3,2] Output: false
  4. Input: nums = [1,2,4,5] Output: true
  5. Input: nums = [1,1,1] Output: true

Constraints:

Clarifying Questions

  1. Q: Is the array guaranteed to have at least one element? A: Yes, as per the constraints 1 <= nums.length.
  2. Q: What should be returned if the array has only one element? A: Return true because a single element array is considered monotonic.
  3. Q: Are we considering equal adjacent elements as part of monotonicity? A: Yes, non-increasing or non-decreasing sequences can include equal elements.

Strategy

  1. Identify Direction:
    • Iterate through the array and determine if the array is non-decreasing or non-increasing.
  2. Check Monotonicity:
    • Once the direction is determined, iterate through the array again to confirm the entire array follows this direction.
  3. Edge Cases:
    • Single-element array should return true.
    • Arrays with all identical elements should return true.

Code

public class Solution {
    public boolean isMonotonic(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        
        boolean isNonDecreasing = true;
        boolean isNonIncreasing = true;
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                isNonIncreasing = false;
            }
            if (nums[i] < nums[i - 1]) {
                isNonDecreasing = false;
            }
        }
        
        return isNonDecreasing || isNonIncreasing;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        
        // Examples
        System.out.println(sol.isMonotonic(new int[]{1, 2, 2, 3})); // true
        System.out.println(sol.isMonotonic(new int[]{6, 5, 4, 4})); // true
        System.out.println(sol.isMonotonic(new int[]{1, 3, 2})); // false
        System.out.println(sol.isMonotonic(new int[]{1, 2, 4, 5})); // true
        System.out.println(sol.isMonotonic(new int[]{1, 1, 1})); // true
    }
}

Time Complexity

This solution efficiently determines whether the array is monotonic by checking both possible monotonic patterns in a single pass.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI