Longest Turbulent Subarray

How it works

We can simplify the sliding window approach by just counting consecutive valid comparisons. We track the current count of alternating comparisons. When we see a comparison that properly alternates from the previous one, we increment the count. Otherwise, we reset to 1 (or 0 if elements are equal). The final answer is the maximum count plus one.

Steps

1. Initialize res = 0, cnt = 0, and sign = -1 (no previous comparison).
2. For each adjacent pair from index 0 to n - 2:
   • If arr[i] > arr[i+1]: if the previous sign was 0 (increase), increment cnt; otherwise reset cnt = 1. Set sign = 1.
   • If arr[i] < arr[i+1]: if the previous sign was 1 (decrease), increment cnt; otherwise reset cnt = 1. Set sign = 0.
   • If equal: reset cnt = 0 and sign = -1.
   • Update res = max(res, cnt).
3. Return res + 1 (to account for the element count, not comparison count).

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Forgetting to Handle Equal Adjacent Elements

When two adjacent elements are equal, the turbulent pattern breaks completely. A common mistake is treating equality as either an increase or decrease, or failing to reset the count. Equal elements should reset your tracking variables since no valid turbulent subarray can contain adjacent equal elements.

Miscounting Array Length vs Comparison Count

The turbulent subarray length is the number of elements, not the number of comparisons. If you track comparison counts, remember that n comparisons correspond to n + 1 elements. Many solutions return a result that is off by one because they confuse these two quantities.

Not Initializing Result to Handle Single-Element Arrays

A single-element array is a valid turbulent subarray of length 1. If your solution only updates the result when finding valid comparisons, it may return 0 for single-element inputs. Always initialize your result to at least 1 to handle this edge case correctly.

from typing import List

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        n = len(arr)
        res = cnt = 0
        sign = -1

        for i in range(n - 1):
            if arr[i] > arr[i + 1]:
                cnt = cnt + 1 if sign == 0 else 1
                sign = 1
            elif arr[i] < arr[i + 1]:
                cnt = cnt + 1 if sign == 1 else 1
                sign = 0
            else:
                cnt = 0
                sign = -1

            res = max(res, cnt)

        return res + 1

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        int res = 0, cnt = 0, sign = -1;

        for (int i = 0; i < n - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                cnt = (sign == 0) ? cnt + 1 : 1;
                sign = 1;
            } else if (arr[i] < arr[i + 1]) {
                cnt = (sign == 1) ? cnt + 1 : 1;
                sign = 0;
            } else {
                cnt = 0;
                sign = -1;
            }

            res = max(res, cnt);
        }

        return res + 1;
    }
};