Problem Description

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

Intuition

To solve this problem, we need to identify the subarrays within nums that are either strictly increasing or strictly decreasing. The goal is to find the length of the longest such subarray.

The approach involves a two-pass method:

1. First Pass: Finding Increasing Subarrays

   • Start with an initial length t of 1 for a potential subarray.
   • Traverse the array from the second element, comparing each element with the previous one.
   • If the current element is greater than the previous, it indicates a continuation of an increasing sequence, so we increase t.
   • If the current element is not greater, the increasing streak is broken, and t is reset to 1.
   • Keep track of the maximum length encountered using the ans variable.

2. Second Pass: Finding Decreasing Subarrays

   • Reset t and repeat the process, this time looking for strictly decreasing sequences.
   • If the current element is less than the previous, increase t.
   • If not, reset t to 1, as the sequence has ended.
   • Again, update ans to capture the longest decreasing sequence found.

After both passes, ans will contain the length of the longest monotonic subarray, whether increasing or decreasing.

Solution Approach

The solution is structured into two primary passes through the nums array, utilizing a linear scan approach. Here's how we execute the solution:

1. Initial Setup:

   • Initialize ans to store the maximum length found, and t to store the current subarray length, both starting at 1.

2. First Pass: Strictly Increasing Subarray:

   • Traverse nums from index 1 to the end.
   • Compare each element x with the previous element:
     • If x > nums[i], it indicates the subarray is strictly increasing, so increment t.
     • If x <= nums[i], reset t to 1 to start a new potential increasing subarray.
   • Update ans with the maximum of its current value and t.

for i, x in enumerate(nums[1:]):
    if nums[i] < x:
        t += 1
        ans = max(ans, t)
    else:
        t = 1

3. Reset for Second Pass:

   • Set t back to 1 to compute decreasing subarray lengths anew.

4. Second Pass: Strictly Decreasing Subarray:

   • Again, traverse nums, comparing each element x with the one before:
     • If x < nums[i], increment t indicating the array is decreasing.
     • Otherwise, reset t to 1.
   • Update ans similarly with any longer decreasing subarray discovered.

t = 1
for i, x in enumerate(nums[1:]):
    if nums[i] > x:
        t += 1
        ans = max(ans, t)
    else:
        t = 1

5. Conclusion:
   • After both passes, ans holds the length of the longest subarray that is either strictly increasing or strictly decreasing, effectively solving the problem.

Example Walkthrough

Let's illustrate the solution approach with an example. Consider the array nums = [3, 8, 5, 7, 6, 2, 4, 1]. Our goal is to find the length of the longest subarray that is either strictly increasing or strictly decreasing.

Step 1: Initial Setup

• Initialize ans to 1, which holds the maximum length found.
• Initialize t to 1, which holds the current subarray length.

Step 2: First Pass for Increasing Subarrays

• Start traversing nums from the second element (index 1).

1. Index 1: Compare 8 with 3.

   • Since 8 > 3, the sequence is increasing. Increment t to 2.
   • Update ans to the maximum of ans and t, which is now 2.

2. Index 2: Compare 5 with 8.

   • Since 5 <= 8, reset t to 1.

3. Index 3: Compare 7 with 5.

   • Since 7 > 5, increment t to 2.
   • ans remains 2, as it is still the maximum.

4. Index 4: Compare 6 with 7.

   • Since 6 <= 7, reset t to 1.

5. Index 5: Compare 2 with 6.

   • Since 2 <= 6, t remains 1.

6. Index 6: Compare 4 with 2.

   • Since 4 > 2, increment t to 2.

7. Index 7: Compare 1 with 4.

   • Since 1 <= 4, reset t to 1.

After the first pass, the longest increasing subarray has length 2 ([3, 8], [5, 7], or [2, 4]).

Step 3: Reset for Second Pass

• Reset t to 1 to check for decreasing subarrays.

Step 4: Second Pass for Decreasing Subarrays

• Traverse nums starting from index 1 again, but this time look for decreasing subarrays.

1. Index 1: Compare 8 with 3.

   • Since 8 <= 3, t remains 1.

2. Index 2: Compare 5 with 8.

   • Since 5 < 8, increment t to 2.
   • Update ans to the maximum of ans and t, which is now 2.

3. Index 3: Compare 7 with 5.

   • Since 7 >= 5, reset t to 1.

4. Index 4: Compare 6 with 7.

   • Since 6 < 7, increment t to 2.
   • ans remains 2.

5. Index 5: Compare 2 with 6.

   • Since 2 < 6, increment t to 3.
   • Update ans to 3, which is now the maximum.

6. Index 6: Compare 4 with 2.

   • Since 4 >= 2, reset t to 1.

7. Index 7: Compare 1 with 4.

   • Since 1 < 4, increment t to 2.

After the second pass, the longest decreasing subarray is [7, 6, 2] with a length of 3.

Step 5: Conclusion

• The longest subarray that is either strictly increasing or strictly decreasing has a length of 3, which is [7, 6, 2].

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the array. This is because the algorithm iterates through the list twice, each one being a linear scan.

The space complexity is O(1), as the algorithm uses a constant amount of extra space regardless of the input size. It only requires a few integer variables (ans and t) for its operations.

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