# Longest Turbulent Subarray
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-turbulent-subarray)
Canonical: https://scaleengineer.com/dsa/problems/longest-turbulent-subarray
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
Given an integer array `arr`, return _the length of a maximum size turbulent subarray of_ `arr`.

A subarray is **turbulent** if the comparison sign flips between each adjacent pair of elements in the subarray.

More formally, a subarray `[arr[i], arr[i + 1], ..., arr[j]]` of `arr` is said to be turbulent if and only if:

* For `i <= k < j`:  
  * `arr[k] > arr[k + 1]` when `k` is odd, and
  * `arr[k] < arr[k + 1]` when `k` is even.
* Or, for `i <= k < j`:  
  * `arr[k] > arr[k + 1]` when `k` is even, and
  * `arr[k] < arr[k + 1]` when `k` is odd.

**Example 1:**

**Input:** arr = [9,4,2,10,7,8,8,1,9]
**Output:** 5
**Explanation:** arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

**Example 2:**

**Input:** arr = [4,8,12,16]
**Output:** 2

**Example 3:**

**Input:** arr = [100]
**Output:** 1

**Constraints:**

* `1 <= arr.length <= 4 * 104`
* `0 <= arr[i] <= 109`

# Approaches
## Brute Force by Checking All Subarrays
This approach is the most straightforward but least efficient. It involves systematically generating every possible contiguous subarray from the input array `arr`. For each of these subarrays, we perform a check to see if it is turbulent. We keep track of the longest turbulent subarray found so far and return its length after all subarrays have been examined.
**Time:** O(n^3) · **Space:** O(1)
**Pros:** Conceptually simple and easy to understand.
**Cons:** Extremely inefficient and will result in a 'Time Limit Exceeded' error on large inputs.; The logic to correctly check if a subarray is turbulent can be complex to implement without errors.
### Explanation
The brute-force method iterates through all possible start and end points of a subarray. For each subarray, it validates the turbulent property. A subarray is turbulent if the comparison sign flips between each adjacent pair of elements. For example, `[a, b, c]` is turbulent if `a > b` and `b < c`, or if `a < b` and `b > c`. This check must hold for the entire subarray. A subarray containing equal adjacent elements, like `[a, a]`, is not turbulent (its longest turbulent part is of length 1).

```java
class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int maxLen = 1;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                // Subarray is arr[i...j]
                if (isTurbulent(arr, i, j)) {
                    maxLen = Math.max(maxLen, j - i + 1);
                }
            }
        }
        return maxLen;
    }

    // Helper to check if subarray arr[start...end] is turbulent
    private boolean isTurbulent(int[] arr, int start, int end) {
        int len = end - start + 1;
        if (len <= 1) {
            return true;
        }
        for (int k = start; k < end; k++) {
            // Check for the alternating sign property
            if (k + 1 < end) {
                boolean c1 = arr[k] > arr[k+1] && arr[k+1] < arr[k+2];
                boolean c2 = arr[k] < arr[k+1] && arr[k+1] > arr[k+2];
                if (!c1 && !c2) {
                    return false;
                }
            }
            // A subarray of length 2 is turbulent if elements are not equal
            if (len == 2 && arr[start] == arr[end]) {
                return false;
            }
        }
        return true;
    }
}
```
*Note: The `isTurbulent` helper function is complex to implement correctly for all edge cases within a brute-force structure, and the provided snippet is a conceptual illustration.*
### Algorithm
- Initialize `maxLength` to 1.
- Use two nested loops, with `i` for the start and `j` for the end, to generate all possible subarrays `arr[i...j]`.
- For each subarray, call a helper function `isTurbulent(subarray)` to check if it meets the turbulent criteria.
- The `isTurbulent` check involves iterating through the subarray and ensuring that for any three consecutive elements `a, b, c`, it holds that `(a > b and b < c)` or `(a < b and b > c)`. Also, no two adjacent elements can be equal.
- If the subarray is turbulent, update `maxLength = max(maxLength, length of subarray)`.
- After checking all subarrays, return `maxLength`.

## Dynamic Programming
A more efficient method is to use dynamic programming. We can solve this problem in a single pass by keeping track of the state at each index. We define two DP states for each index `i`: the length of the longest turbulent subarray ending at `i` where the last comparison was `>` (`dec[i]`), and the length where the last comparison was `<` (`inc[i]`). The solution for index `i` can be calculated based on the solution for `i-1`.
**Time:** O(n) because it involves a single pass through the input array. · **Space:** O(n) for the two DP arrays.
**Pros:** Efficient time complexity of O(n).; The logic directly follows the recursive nature of the problem.
**Cons:** Uses O(n) extra space, which is not optimal.
### Explanation
This approach avoids re-computation by storing the results of subproblems. We iterate through the array and for each element `arr[i]`, we determine the length of the turbulent subarray ending at `i`. This length depends on the relationship between `arr[i]` and `arr[i-1]`, and the length of the turbulent subarray ending at `i-1`.

If `arr[i] > arr[i-1]`, we have an increasing step. A turbulent subarray can be formed by appending `arr[i]` to a turbulent subarray that ended at `i-1` with a decreasing step. Thus, the new length is `dec[i-1] + 1`.

If `arr[i] < arr[i-1]`, we have a decreasing step, which can extend a subarray that ended with an increasing step. The new length is `inc[i-1] + 1`.

If `arr[i] == arr[i-1]`, the turbulent property is broken, and any new subarray starts fresh with length 1.

```java
class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        if (n <= 1) {
            return n;
        }
        int[] inc = new int[n]; // Length of turbulent subarray ending at i with arr[i-1] < arr[i]
        int[] dec = new int[n]; // Length of turbulent subarray ending at i with arr[i-1] > arr[i]
        inc[0] = 1;
        dec[0] = 1;
        int maxLen = 1;

        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i-1]) {
                inc[i] = dec[i-1] + 1;
                dec[i] = 1;
            } else if (arr[i] < arr[i-1]) {
                dec[i] = inc[i-1] + 1;
                inc[i] = 1;
            } else {
                inc[i] = 1;
                dec[i] = 1;
            }
            maxLen = Math.max(maxLen, Math.max(inc[i], dec[i]));
        }
        return maxLen;
    }
}
```
### Algorithm
- Create two integer arrays, `inc` and `dec`, of the same size as `arr`.
- `inc[i]` will store the length of the longest turbulent subarray ending at index `i` with `arr[i] > arr[i-1]`.
- `dec[i]` will store the length of the longest turbulent subarray ending at index `i` with `arr[i] < arr[i-1]`.
- Initialize `inc[0] = 1`, `dec[0] = 1`, and `maxLength = 1`.
- Iterate through the array from `i = 1` to `n-1`:
  - If `arr[i] > arr[i-1]`, it can extend a sequence ending in a decrease. So, `inc[i] = dec[i-1] + 1`. Reset `dec[i] = 1`.
  - If `arr[i] < arr[i-1]`, it can extend a sequence ending in an increase. So, `dec[i] = inc[i-1] + 1`. Reset `inc[i] = 1`.
  - If `arr[i] == arr[i-1]`, the turbulence is broken. Reset both `inc[i] = 1` and `dec[i] = 1`.
- In each step of the loop, update `maxLength = Math.max(maxLength, inc[i], dec[i])`.
- Return `maxLength`.

## One-Pass Sliding Window (Space-Optimized)
This is the most optimal approach, improving upon the dynamic programming solution by optimizing space. We observe that to calculate the lengths for the current index `i`, we only need the lengths from the immediate previous index `i-1`. This allows us to discard the DP arrays and use only a few variables to keep track of the current state, reducing space complexity to O(1). This method can also be conceptualized as a sliding window that expands as long as the turbulent property is maintained and resets or shrinks when the property is violated.
**Time:** O(n), as it requires only one pass through the array. · **Space:** O(1), as it only uses a few constant extra variables.
**Pros:** Optimal time complexity of O(n).; Optimal space complexity of O(1).; Solves the problem in a single pass.
**Cons:** The logic for handling state transitions can be slightly more complex to reason about than the O(n) space DP approach.
### Explanation
Instead of full DP arrays, we only need to know the length of the turbulent subarray ending at the previous position. We can maintain this state in a single variable, `currentLength`. We iterate through the array, extending `currentLength` as long as the comparison sign alternates. When the pattern breaks (either by two consecutive identical comparisons or by equal adjacent elements), we reset `currentLength` and start counting a new potential turbulent subarray.

```java
class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        if (n < 2) {
            return n;
        }

        int maxLen = 1;
        int currentLen = 1;

        for (int i = 1; i < n; i++) {
            int c = Integer.compare(arr[i-1], arr[i]);
            
            // If elements are equal, the turbulent subarray has length 1.
            if (c == 0) {
                currentLen = 1;
            } else {
                // Check if it's the start of a new sequence or if the sign flips.
                // The previous comparison is Integer.compare(arr[i-2], arr[i-1]).
                // If the current comparison 'c' is different, the turbulence continues.
                if (i == 1 || c != Integer.compare(arr[i-2], arr[i-1])) {
                    currentLen++;
                } else {
                    // Sign did not flip (e.g., > followed by >), so a new turbulent
                    // subarray of length 2 starts with arr[i-1] and arr[i].
                    currentLen = 2;
                }
            }
            maxLen = Math.max(maxLen, currentLen);
        }
        return maxLen;
    }
}
```
### Algorithm
- Handle base cases where array length is less than 2.
- Initialize `maxLength = 1` and `currentLength = 1`.
- Iterate through the array from the second element (`i = 1`).
- In each iteration, determine the comparison sign between `arr[i-1]` and `arr[i]`. Let's use `c = Integer.compare(arr[i-1], arr[i])`.
- If `c == 0` (elements are equal), the current turbulent sequence is broken. Reset `currentLength` to 1.
- If `c != 0`:
  - Check if this is the start of a new sequence (i.e., `i == 1`) or if the sign `c` is different from the previous sign (`Integer.compare(arr[i-2], arr[i-1])`).
  - If so, the turbulence continues. Increment `currentLength`.
  - Otherwise, the sign pattern is broken (e.g., two `>` in a row). A new turbulent sequence of length 2 (formed by `arr[i-1]` and `arr[i]`) begins. Set `currentLength = 2`.
- After each step, update `maxLength = Math.max(maxLength, currentLength)`.
- Return `maxLength`.

# Solutions
### Java

```java
class Solution { public int maxTurbulenceSize ( int [] arr ) { int ans = 1 , f = 1 , g = 1 ; for ( int i = 1 ; i < arr . length ; ++ i ) { int ff = arr [ i - 1 ] < arr [ i ] ? g + 1 : 1 ; int gg = arr [ i - 1 ] > arr [ i ] ? f + 1 : 1 ; f = ff ; g = gg ; ans = Math . max ( ans , Math . max ( f , g )); } return ans ; } }
```

### CPP

```cpp
class Solution { public: int maxTurbulenceSize ( vector < int >& arr ) { int ans = 1 , f = 1 , g = 1 ; for ( int i = 1 ; i < arr . size (); ++ i ) { int ff = arr [ i - 1 ] < arr [ i ] ? g + 1 : 1 ; int gg = arr [ i - 1 ] > arr [ i ] ? f + 1 : 1 ; f = ff ; g = gg ; ans = max ({ ans , f , g }); } return ans ; } };
```

### Python

```python
class Solution : def maxTurbulenceSize ( self , arr : List [ int ]) -> int : ans = f = g = 1 for a , b in pairwise ( arr ): ff = g + 1 if a < b else 1 gg = f + 1 if a > b else 1 f , g = ff , gg ans = max ( ans , f , g ) return ans
```