Longest Strictly Increasing or Strictly Decreasing Subarray

Longest Strictly Increasing or Strictly Decreasing Subarray - Problem

Array Easy

You are given an array of integers nums. Return the length of the longest subarray of nums which is either strictly increasing or strictly decreasing.

A subarray is a contiguous non-empty sequence of elements within an array.

A strictly increasing subarray means each element is larger than the previous one.

A strictly decreasing subarray means each element is smaller than the previous one.

Input & Output

Example 1 — Mixed Pattern

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

› Output: 2

💡 Note: The longest valid subarrays are [1,4] (strictly increasing) and [4,3] or [3,2] (strictly decreasing), all with length 2

Example 2 — Longer Increasing

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

› Output: 1

💡 Note: All elements are equal, so no strictly increasing or decreasing subarray exists longer than 1

Example 3 — Perfect Sequence

$ Input: nums = [3,1,5,6,9]

› Output: 4

💡 Note: The subarray [1,5,6,9] is strictly increasing with length 4

Constraints

1 ≤ nums.length ≤ 1000
-10⁹ ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 25 a Amazon 18 M Microsoft 12

The key insight is tracking both increasing and decreasing streaks simultaneously during a single pass. Best approach is the single-pass state tracking solution with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Check every possible subarray to see if it's strictly increasing or decreasing
Single Pass with State Tracking	O(n)	O(1)	Track increasing and decreasing streaks simultaneously in one pass

Brute Force — Algorithm Steps

Iterate through each starting position
For each start, check all possible ending positions
Verify if subarray is strictly increasing or decreasing
Update maximum length if current subarray is valid

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate All Subarrays

Create every possible contiguous subarray

Check Each Pattern

Verify if strictly increasing or decreasing

Track Maximum

Keep the longest valid subarray length

Code -

solution.c — C

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

int solution(int* nums, int numsSize) {
    int maxLength = 1;
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j <= numsSize; j++) {
            if (j - i <= 1) continue;
            
            // Check if strictly increasing
            int isIncreasing = 1;
            for (int k = i + 1; k < j; k++) {
                if (nums[k] <= nums[k - 1]) {
                    isIncreasing = 0;
                    break;
                }
            }
            
            // Check if strictly decreasing
            int isDecreasing = 1;
            for (int k = i + 1; k < j; k++) {
                if (nums[k] >= nums[k - 1]) {
                    isDecreasing = 0;
                    break;
                }
            }
            
            if (isIncreasing || isDecreasing) {
                int length = j - i;
                if (length > maxLength) {
                    maxLength = length;
                }
            }
        }
    }
    
    return maxLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int count = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[count++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int result = solution(nums, count);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops: O(n) start positions × O(n) end positions × O(n) to check each subarray

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables for tracking positions and maximum length

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

850 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

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler