Problem Description

You are given an array of integers nums. Your task is to find the length of the longest subarray that is either strictly increasing or strictly decreasing.

A strictly increasing subarray means each element is greater than the previous one (e.g., [1, 2, 3, 5]).

A strictly decreasing subarray means each element is less than the previous one (e.g., [5, 3, 2, 1]).

The subarray must be contiguous (consecutive elements from the original array) and non-empty.

For example:

• If nums = [1, 4, 3, 3, 2], the longest strictly increasing subarray is [1, 4] with length 2, and the longest strictly decreasing subarray is [4, 3] or [3, 2] with length 2. So the answer is 2.
• If nums = [1, 2, 3, 4], the entire array is strictly increasing with length 4.
• If nums = [5, 4, 3, 2, 1], the entire array is strictly decreasing with length 5.

The solution uses two separate passes through the array:

1. First pass: Track the length of strictly increasing subarrays by comparing each element with the previous one. If nums[i] < nums[i+1], extend the current increasing subarray length; otherwise, reset to 1.
2. Second pass: Track the length of strictly decreasing subarrays by comparing each element with the previous one. If nums[i] > nums[i+1], extend the current decreasing subarray length; otherwise, reset to 1.

The answer is the maximum length found across both passes.

Intuition

The key observation is that we need to find the longest subarray that maintains a consistent monotonic pattern - either all elements are strictly increasing or all elements are strictly decreasing. These are two completely separate conditions that cannot overlap within the same subarray.

Since a subarray cannot be both strictly increasing and strictly decreasing at the same time, we can handle these two cases independently. This naturally leads to a two-pass approach where we search for each type of monotonic pattern separately.

For finding the longest strictly increasing subarray, we can use a sliding window technique. We traverse the array and keep extending our current subarray as long as each element is greater than the previous one. When we encounter an element that breaks this pattern (not greater than the previous), we know the current increasing subarray has ended and we must start a new one from the current position.

The same logic applies for finding the longest strictly decreasing subarray - we extend as long as each element is less than the previous one, and reset when the pattern breaks.

Why two separate passes? While we could try to track both increasing and decreasing lengths in a single pass, using two passes makes the logic cleaner and easier to understand. In the first pass, we focus only on nums[i] < nums[i+1] comparisons to find increasing subarrays. In the second pass, we focus only on nums[i] > nums[i+1] comparisons to find decreasing subarrays.

The variable t acts as a counter that grows when the monotonic pattern continues and resets to 1 when it breaks. We continuously update our answer ans with the maximum length seen so far across both types of monotonic subarrays.

Solution Approach

The solution implements the two-pass approach to find the longest monotonic subarray.

First Pass - Finding Longest Strictly Increasing Subarray:

1. Initialize ans = 1 (to store the maximum length found) and t = 1 (to track the current subarray length).
2. Iterate through the array starting from index 1 using enumerate(nums[1:]).
3. For each element x at position i in the sliced array:
   • Compare nums[i] with x (which is actually nums[i+1] in the original array)
   • If nums[i] < x, the sequence is still increasing:
     • Increment t by 1 to extend the current subarray
     • Update ans = max(ans, t) to keep track of the maximum length
   • Otherwise, the increasing pattern is broken:
     • Reset t = 1 to start counting a new subarray

Second Pass - Finding Longest Strictly Decreasing Subarray:

1. Reset t = 1 to start fresh for decreasing subarrays.
2. Again iterate through the array starting from index 1.
3. For each element x at position i:
   • If nums[i] > x, the sequence is still decreasing:
     • Increment t by 1 to extend the current subarray
     • Update ans = max(ans, t) to keep track of the maximum length
   • Otherwise, the decreasing pattern is broken:
     • Reset t = 1 to start counting a new subarray

Key Implementation Details:

• The use of enumerate(nums[1:]) allows us to iterate from the second element while still having access to the index i which refers to the previous element in the original array.
• The variable t acts as a running counter that tracks the current monotonic subarray length.
• The variable ans maintains the global maximum across both increasing and decreasing subarrays.
• Time complexity is O(n) where n is the length of the array, as we make exactly two passes through the array.
• Space complexity is O(1) as we only use a constant amount of extra space for variables.

The final answer returned is the maximum length found across both types of monotonic patterns.

Example Walkthrough

Let's walk through the solution with nums = [1, 4, 3, 3, 2]:

Initial Setup:

• ans = 1 (stores maximum length found)
• t = 1 (tracks current subarray length)

First Pass - Finding Longest Strictly Increasing:

After first pass: Found longest increasing subarray [1, 4] with length 2.

Second Pass - Finding Longest Strictly Decreasing:

Reset t = 1 for the second pass.

After second pass: Found longest decreasing subarrays [4, 3] and [3, 2], both with length 2.

Final Result: The maximum length across both passes is 2.

The algorithm correctly identifies that the longest monotonic subarray (either strictly increasing or strictly decreasing) has length 2.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm makes two separate passes through the array (excluding the first element in each pass). In the first loop, it iterates through nums[1:] to find the longest increasing subarray, and in the second loop, it iterates through nums[1:] again to find the longest decreasing subarray. Since each loop runs in O(n-1) time and we have two sequential loops, the total time complexity is O(n-1) + O(n-1) = O(2n-2) = O(n).

The space complexity is O(1). The algorithm only uses a constant amount of extra space for variables ans, t, i, and x, regardless of the input size. No additional data structures that scale with the input size are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Handling Equal Adjacent Elements Incorrectly

One of the most common mistakes is misunderstanding what "strictly" increasing or decreasing means. When adjacent elements are equal, the sequence is broken for both increasing and decreasing patterns.

Incorrect Implementation:

# Wrong: Using <= or >= instead of < or >
if nums[i - 1] <= nums[i]:  # This would include equal elements
    current_length += 1

Why it's wrong: The problem specifically requires strictly monotonic subarrays, meaning [1, 2, 2, 3] should be treated as two separate sequences: [1, 2] and [2, 3], not as one sequence of length 4.

Correct Implementation:

# Correct: Use strict inequality
if nums[i - 1] < nums[i]:  # Strictly less than
    current_length += 1

2. Not Resetting the Counter Between Passes

Another pitfall is forgetting to reset the current_length counter between the two passes through the array.

Incorrect Implementation:

def longestMonotonicSubarray(self, nums: List[int]) -> int:
    max_length = 1
    current_length = 1
  
    # First pass for increasing
    for i in range(1, len(nums)):
        if nums[i - 1] < nums[i]:
            current_length += 1
            max_length = max(max_length, current_length)
        else:
            current_length = 1
  
    # FORGOT TO RESET current_length HERE!
    # Second pass for decreasing
    for i in range(1, len(nums)):
        if nums[i - 1] > nums[i]:
            current_length += 1  # This continues from the previous value!
            max_length = max(max_length, current_length)
        else:
            current_length = 1

Why it's wrong: If the first pass ends with current_length = 3, the second pass would start counting from 3 instead of 1, leading to incorrect results.

Correct Implementation:

# ... after first pass
current_length = 1  # Reset before second pass

# Second pass for decreasing
for i in range(1, len(nums)):
    # ...

3. Edge Case: Single Element Array

While the provided solution handles this correctly by initializing max_length = 1, developers might overlook this edge case when implementing from scratch.

Potential Issue:

# If someone initializes max_length = 0
max_length = 0  # Wrong initialization

Why it matters: A single element is considered a valid monotonic subarray of length 1. The problem states the subarray must be "non-empty", so even nums = [5] should return 1.

4. Off-by-One Errors with Indexing

When using different iteration patterns, it's easy to make indexing mistakes.

Incorrect Implementation:

# Using enumerate(nums[1:]) incorrectly
for i, x in enumerate(nums[1:]):
    if nums[i+1] < x:  # Wrong! i+1 would go out of bounds
        current_length += 1

Why it's wrong: When using enumerate(nums[1:]), the index i starts from 0 but refers to position 1 in the original array. Using nums[i+1] would actually access nums[2] when i=1, skipping comparisons.

Correct Implementation:

# Either use standard range iteration
for i in range(1, len(nums)):
    if nums[i - 1] < nums[i]:
        current_length += 1

# Or if using enumerate(nums[1:]), adjust indexing carefully
for i, x in enumerate(nums[1:]):
    if nums[i] < x:  # nums[i] is the previous element, x is current
        current_length += 1

5. Attempting to Optimize with Single Pass

Some might try to track both increasing and decreasing sequences in a single pass, which can lead to complex logic and bugs.

Problematic Approach:

inc_length = dec_length = 1
for i in range(1, len(nums)):
    if nums[i - 1] < nums[i]:
        inc_length += 1
        dec_length = 1  # Reset decreasing
    elif nums[i - 1] > nums[i]:
        dec_length += 1
        inc_length = 1  # Reset increasing
    else:  # Equal elements
        inc_length = dec_length = 1

Why it's harder: While this can work, it's more error-prone and harder to debug. The two-pass approach is clearer, more maintainable, and has the same O(n) complexity.