Longest Strictly Increasing or Strictly Decreasing Subarray

Difficulty: Easy | Acceptance: 64.90% | Paid: No Topics: Array

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

A subarray is a contiguous non-empty sequence of elements in the array.

Table of Contents

• Examples
• Constraints
• Brute Force
• Single Pass

Examples

Example 1:

Input: nums = [1,4,3,3,2]
Output: 2
Explanation: The longest strictly increasing subarray is [1,4] and the longest strictly decreasing subarray is [4,3,3,2]. Their lengths are both 2, so we return 2.

Example 2:

Input: nums = [3,3,3,3]
Output: 1
Explanation: The longest strictly increasing subarray is [3] and the longest strictly decreasing subarray is [3]. Their lengths are both 1, so we return 1.

Example 3:

Input: nums = [3,2,1]
Output: 3
Explanation: The longest strictly increasing subarray is [3] and the longest strictly decreasing subarray is [3,2,1]. Their lengths are 1 and 3, so we return 3.

Constraints

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Brute Force

Intuition Check all possible subarrays and determine if they are strictly increasing or strictly decreasing, keeping track of the maximum length found.

Steps

• Iterate through all possible starting indices
• For each starting index, expand to the right and check if the subarray is strictly increasing or strictly decreasing
• Update the maximum length whenever a longer valid subarray is found

from typing import List

class Solution:
    def longestMonotonicSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        max_len = 1
        
        for i in range(n):
            # Check strictly increasing
            inc_len = 1
            for j in range(i + 1, n):
                if nums[j] > nums[j - 1]:
                    inc_len += 1
                else:
                    break
            max_len = max(max_len, inc_len)
            
            # Check strictly decreasing
            dec_len = 1
            for j in range(i + 1, n):
                if nums[j] < nums[j - 1]:
                    dec_len += 1
                else:
                    break
            max_len = max(max_len, dec_len)
        
        return max_len

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple but inefficient for large arrays

Single Pass

Intuition Maintain two counters for the current increasing and decreasing subarray lengths, updating them as we iterate through the array once.

Steps

• Initialize inc and dec to 1 (minimum length for any valid subarray)
• Iterate through the array starting from index 1
• For each element, compare with the previous element and update inc/dec accordingly
• Track the maximum length seen

from typing import List

class Solution:
    def longestMonotonicSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 1
        
        max_len = 1
        inc = 1
        dec = 1
        
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                inc += 1
                dec = 1
            elif nums[i] < nums[i - 1]:
                dec += 1
                inc = 1
            else:
                inc = 1
                dec = 1
            max_len = max(max_len, inc, dec)
        
        return max_len

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Optimal solution with single pass through the array