Code Implementation

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

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        if (n == 1) return 1;
        int inc = 1, dec = 1, max_len = 1;
        for (int i = 1; i < n; ++i) {
            if (arr[i] > arr[i-1]) {
                inc = dec + 1;
                dec = 1;
            } else if (arr[i] < arr[i-1]) {
                dec = inc + 1;
                inc = 1;
            } else {
                inc = dec = 1;
            }
            max_len = max(max_len, max(inc, dec));
        }
        return max_len;
    }
};
      

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        if (n == 1) return 1;
        int inc = 1, dec = 1, maxLen = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) {
                inc = dec + 1;
                dec = 1;
            } else if (arr[i] < arr[i - 1]) {
                dec = inc + 1;
                inc = 1;
            } else {
                inc = dec = 1;
            }
            maxLen = Math.max(maxLen, Math.max(inc, dec));
        }
        return maxLen;
    }
}
      

var maxTurbulenceSize = function(arr) {
    let n = arr.length;
    if (n === 1) return 1;
    let inc = 1, dec = 1, maxLen = 1;
    for (let i = 1; i < n; i++) {
        if (arr[i] > arr[i - 1]) {
            inc = dec + 1;
            dec = 1;
        } else if (arr[i] < arr[i - 1]) {
            dec = inc + 1;
            inc = 1;
        } else {
            inc = dec = 1;
        }
        maxLen = Math.max(maxLen, inc, dec);
    }
    return maxLen;
};
      

Problem Description

Given an integer array arr, your task is to find the length of the longest subarray that is turbulent. A subarray is considered turbulent if the comparison signs between each adjacent pair of elements alternate between greater-than and less-than.

• Formally, for a subarray arr[i..j] of length at least 2, for every k in i <= k < j:
• Either arr[k] > arr[k+1] and arr[k+1] < arr[k+2] and so on,
• Or arr[k] < arr[k+1] and arr[k+1] > arr[k+2] and so on.
• You must return the length of the longest such subarray.
• Constraints:
  • 1 <= arr.length <= 4 * 10^4
  • 0 <= arr[i] <= 10^9

You may not reuse elements (each subarray must be contiguous), and there is always at least one valid answer.

Thought Process

At first glance, the problem seems to ask for the longest contiguous subarray where the "up" and "down" relationships between consecutive elements alternate. A brute-force approach would check all possible subarrays, but with up to 40,000 elements, this is not feasible due to time constraints.

To optimize, we can notice that we only need to track the current "turbulent" streak as we scan the array. If the current comparison alternates from the previous one, we can extend the streak; otherwise, we reset. We can do this efficiently in a single pass.

This leads naturally to a sliding window or dynamic programming approach, where we keep counts of the current increasing and decreasing streaks.

Solution Approach

We'll use a dynamic programming approach with two variables to represent the length of the current turbulent subarray ending at position i:

• inc: Length of turbulent subarray ending at i where arr[i] > arr[i-1].
• dec: Length of turbulent subarray ending at i where arr[i] < arr[i-1].

1. Initialize inc = dec = 1 for the first element, since a single element is trivially a turbulent subarray of length 1.
2. Loop through the array from the second element onward.
3. At each step:
   • If arr[i] > arr[i-1], increment inc as dec + 1 (because we can extend a "down" streak), and reset dec to 1.
   • If arr[i] < arr[i-1], increment dec as inc + 1, and reset inc to 1.
   • If arr[i] == arr[i-1], reset both inc and dec to 1.
4. At each step, update the maximum length found so far.
5. Return the maximum length at the end.

This algorithm is efficient because it only needs a single pass and constant space.

Example Walkthrough

Let's take arr = [9,4,2,10,7,8,8,1,9].

• Start at index 1: 4 < 9, so dec = inc + 1 = 2, inc = 1. Max so far: 2.
• Index 2: 2 < 4, so dec = inc + 1 = 2, inc = 1. (Not turbulent, since two downs in a row.) Max remains 2.
• Index 3: 10 > 2, so inc = dec + 1 = 3, dec = 1. Max so far: 3.
• Index 4: 7 < 10, so dec = inc + 1 = 4, inc = 1. Max so far: 4.
• Index 5: 8 > 7, so inc = dec + 1 = 5, dec = 1. Max so far: 5.
• Index 6: 8 == 8, so reset both to 1. Max remains 5.
• Index 7: 1 < 8, so dec = inc + 1 = 2, inc = 1. Max remains 5.
• Index 8: 9 > 1, so inc = dec + 1 = 3, dec = 1. Max remains 5.

The answer is 5, corresponding to the subarray [4,2,10,7,8].

Time and Space Complexity

• Brute-force: Checking all subarrays would take O(n²) time, since there are O(n²) possible subarrays and each check could take O(1) to O(n).
• Optimized approach: The presented solution scans the array once, so it is O(n) time. Space complexity is O(1) because we only use a few variables.

This efficiency is possible because the problem's nature allows us to make decisions based only on the last comparison, not the entire subarray.

Summary

In summary, the problem asks for the longest contiguous subarray with alternating up and down comparisons. By tracking the current increasing and decreasing streaks as we iterate, we can efficiently determine the answer in linear time. The key insight is to recognize the problem's alternating pattern and update our counters accordingly, avoiding unnecessary re-computation. The solution is elegant, efficient, and easy to implement.