Monotonic Array - Practice Coding Problems

Monotonic Array - Problem

Array Easy

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

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

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

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

Input & Output

Example 1 — Non-decreasing Array

$ Input: nums = [1,2,2,3]

› Output: true

💡 Note: Array is non-decreasing: 1 ≤ 2 ≤ 2 ≤ 3. Since it satisfies the monotonic increasing property, return true.

Example 2 — Non-monotonic Array

$ Input: nums = [6,5,4,4]

› Output: true

💡 Note: Array is non-increasing: 6 ≥ 5 ≥ 4 ≥ 4. Since it satisfies the monotonic decreasing property, return true.

Example 3 — Mixed Pattern

$ Input: nums = [1,3,2]

› Output: false

💡 Note: Array has both increasing (1<3) and decreasing (3>2) transitions, so it's not monotonic.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁵ ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array with elements to check for monotonic property

Check Pattern

Verify if array is only increasing, only decreasing, or constant

Result

Return true if monotonic, false if mixed pattern

Key Takeaway

🎯 Key Insight: An array is monotonic if it never exhibits both increasing and decreasing patterns

Asked in

F Facebook 28 a Amazon 15 G Google 12

The key insight is that an array is monotonic if it never has both increasing AND decreasing transitions. The optimal single-pass approach tracks both patterns simultaneously and returns false immediately when both are detected. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pass - Separate Checks	O(n)	O(1)	Make one pass checking for increasing, another for decreasing
Brute Force - Check All Pairs	O(n²)	O(1)	Check every pair (i,j) where i <= j to verify monotonic property
Single Pass - Track Violations	O(n)	O(1)	One pass tracking if we've seen both increases and decreases

Two Pass - Separate Checks — Algorithm Steps

First pass: check if nums[i] <= nums[i+1] for all i
Second pass: check if nums[i] >= nums[i+1] for all i
Return true if either pass succeeds

Visualization

Tap to expand

Step-by-Step Walkthrough

Pass 1

Check if non-decreasing (nums[i] <= nums[i+1])

Pass 2

If Pass 1 fails, check if non-increasing

Result

Return true if either pass succeeds

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int* nums, int numsSize) {
    if (numsSize <= 1) return true;
    
    // Check if non-decreasing
    bool isIncreasing = true;
    for (int i = 0; i < numsSize - 1; i++) {
        if (nums[i] > nums[i + 1]) {
            isIncreasing = false;
            break;
        }
    }
    
    if (isIncreasing) return true;
    
    // Check if non-increasing
    bool isDecreasing = true;
    for (int i = 0; i < numsSize - 1; i++) {
        if (nums[i] < nums[i + 1]) {
            isDecreasing = false;
            break;
        }
    }
    
    return isDecreasing;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int nums[1000];
    int size = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token != NULL) {
            nums[size++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    bool result = solution(nums, size);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two separate linear passes through the array, each taking O(n) time

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra variables to track monotonic properties

✓ Linear Space

180.0K Views

Medium Frequency

~15 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pass - Separate Checks — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler