Skip to main content

Monotonic Array Algorithm

Ayesha
EditReport

Monotonic Array

An array is considered monotonic if it is either entirely non-increasing (monotonic decreasing) or entirely non-decreasing (monotonic increasing).

Video Explanation​

Characteristics​

  • Time Complexity: O(N)O(N), where NN is the length of the array. We only need to traverse the array once.
  • Space Complexity: O(1)O(1), as we are only using two boolean flags for evaluation without any extra auxiliary data structures.

Java Implementation​

Instead of looping through the array twice, this approach assumes the array is both increasing and decreasing at the start. As we iterate through the array in a single pass, we invalidate these flags if we find a violation.

public class MonotonicArray {

    /**
     * Checks if the given array is monotonic.
     * @param nums the array of integers.
     * @return true if the array is monotonic, false otherwise
     */
    public static boolean isMonotonic(int[] nums) {
        // Defensive check to prevent NullPointerException
        if (nums == null || nums.length <= 1) {
            return true;
        }
    public static boolean isMonotonic(int[] nums) {
        if (nums == null) {
            return false;
        }
        boolean isIncreasing = true;
        boolean isDecreasing = true;

        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                isIncreasing = false;
            }
            if (nums[i] < nums[i + 1]) {
                isDecreasing = false;
            }
            
            // Optimization: If it breaks both properties, terminate early
            if (!isIncreasing && !isDecreasing) {
                return false;
            }
        }

        return isIncreasing || isDecreasing;
    }
}
Track Your Progress

Done with this topic? Mark it as complete to track your progress.

Was this page helpful?

💬

Discuss this page

Have a question or spot something confusing in "Monotonic Array Algorithm"? Ask below. Backed by GitHub Discussions—maintainers receive system notifications directly.