Longest Turbulent Subarray
Description
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. In other words, the elements must follow a zigzag pattern where they alternately increase and decrease (or decrease and increase).
More formally, a subarray [arr[i], arr[i+1], ..., arr[j]] is turbulent if and only if one of the following two patterns holds for every index k where i <= k < j:
- Pattern 1 (starts with decrease):
arr[k] > arr[k+1]whenkis even, andarr[k] < arr[k+1]whenkis odd. - Pattern 2 (starts with increase):
arr[k] < arr[k+1]whenkis even, andarr[k] > arr[k+1]whenkis odd.
A single element by itself is always considered turbulent (length 1). Two adjacent elements form a turbulent subarray of length 2 as long as they are not equal.
Examples
Example 1
Input: arr = [9, 4, 2, 10, 7, 8, 8, 1, 9]
Output: 5
Explanation: The longest turbulent subarray is arr[1..5] = [4, 2, 10, 7, 8]. Let us verify: 4 > 2 (decrease), 2 < 10 (increase), 10 > 7 (decrease), 7 < 8 (increase). The comparison signs alternate perfectly: >, <, >, <. So this subarray of length 5 is turbulent. Note that arr[5] == arr[6] == 8 breaks any turbulent pattern, so the subarray cannot extend beyond index 5.
Example 2
Input: arr = [4, 8, 12, 16]
Output: 2
Explanation: The array is strictly increasing: 4 < 8 < 12 < 16. No three consecutive elements alternate direction, so no turbulent subarray of length 3 or more exists. However, any two adjacent unequal elements form a turbulent subarray of length 2, for example [4, 8].
Example 3
Input: arr = [100]
Output: 1
Explanation: A single element is trivially a turbulent subarray of length 1.
Constraints
- 1 ≤ arr.length ≤ 4 × 10^4
- 0 ≤ arr[i] ≤ 10^9
Editorial
Brute Force
Intuition
The most straightforward way to solve this problem is to examine every possible subarray, check whether it is turbulent, and keep track of the longest one we find.
Think of it like inspecting every possible contiguous segment of the array. For each starting point, we try to extend the subarray as far as possible while the turbulent (zigzag) property holds. The moment two adjacent comparisons agree in direction (both increasing or both decreasing) or two adjacent elements are equal, the turbulent pattern breaks and we stop.
For each starting index i, we walk forward from i checking consecutive pairs. At each step, we compare the direction of the current pair with the previous pair. If the directions alternate, we continue; otherwise, we record the length and move to the next starting index.
Step-by-Step Explanation
Let's trace through arr = [9, 4, 2, 10, 7, 8, 8, 1, 9]:
Step 1: Start at i=0 (value 9). Compare 9 and 4: 9 > 4 (decrease). Continue.
Step 2: Compare 4 and 2: 4 > 2 (decrease). Previous was also decrease — directions don't alternate! Turbulent subarray from i=0 has length 2: [9, 4].
Step 3: Start at i=1 (value 4). Compare 4 and 2: 4 > 2 (decrease). Continue.
Step 4: Compare 2 and 10: 2 < 10 (increase). Previous was decrease — directions alternate! Continue.
Step 5: Compare 10 and 7: 10 > 7 (decrease). Previous was increase — alternate! Continue.
Step 6: Compare 7 and 8: 7 < 8 (increase). Previous was decrease — alternate! Continue.
Step 7: Compare 8 and 8: 8 == 8 (equal). Equal elements break turbulence. Turbulent subarray from i=1 has length 5: [4, 2, 10, 7, 8].
Step 8: We continue checking starting indices i=2, 3, ..., but none produce a longer subarray. The answer is 5.
Notice how for every starting index, we repeat checking pairs that overlap with previous attempts. This redundancy makes brute force slow.
Brute Force — Checking All Starting Points — Watch how we try each starting index and extend the turbulent subarray until the zigzag pattern breaks, repeating overlapping work.
Algorithm
- Initialize
max_len = 1(a single element is always turbulent) - For each starting index
ifrom 0 to n-1:
a. Setcurrent_len = 1
b. For each indexjfromi+1ton-1:- Compute the comparison between arr[j-1] and arr[j]
- If arr[j-1] == arr[j], break (equal elements end turbulence)
- If j == i+1, this is the first pair — always extends (current_len = 2)
- Else, check if the current direction differs from the previous direction
- If yes (alternates), increment current_len
- If no (same direction), break
c. Updatemax_len = max(max_len, current_len)
- Return
max_len
Code
class Solution {
public:
int maxTurbulenceSize(vector<int>& arr) {
int n = arr.size();
int maxLen = 1;
for (int i = 0; i < n; i++) {
int curLen = 1;
int prevSign = 0; // 0 = none, 1 = increase, -1 = decrease
for (int j = i + 1; j < n; j++) {
int curSign = 0;
if (arr[j] > arr[j - 1]) curSign = 1;
else if (arr[j] < arr[j - 1]) curSign = -1;
else break; // equal elements break turbulence
if (prevSign == 0) {
// First pair from this start
curLen = 2;
} else if (curSign != prevSign) {
// Direction alternated — extend
curLen++;
} else {
// Same direction — not turbulent
break;
}
prevSign = curSign;
}
maxLen = max(maxLen, curLen);
}
return maxLen;
}
};class Solution:
def maxTurbulenceSize(self, arr: list[int]) -> int:
n = len(arr)
max_len = 1
for i in range(n):
cur_len = 1
prev_sign = 0 # 0 = none, 1 = increase, -1 = decrease
for j in range(i + 1, n):
if arr[j] > arr[j - 1]:
cur_sign = 1
elif arr[j] < arr[j - 1]:
cur_sign = -1
else:
break # equal elements break turbulence
if prev_sign == 0:
cur_len = 2 # first pair
elif cur_sign != prev_sign:
cur_len += 1 # direction alternated
else:
break # same direction
prev_sign = cur_sign
max_len = max(max_len, cur_len)
return max_lenclass Solution {
public int maxTurbulenceSize(int[] arr) {
int n = arr.length;
int maxLen = 1;
for (int i = 0; i < n; i++) {
int curLen = 1;
int prevSign = 0;
for (int j = i + 1; j < n; j++) {
int curSign = Integer.compare(arr[j], arr[j - 1]);
if (curSign == 0) break;
if (prevSign == 0) {
curLen = 2;
} else if (curSign != prevSign) {
curLen++;
} else {
break;
}
prevSign = curSign;
}
maxLen = Math.max(maxLen, curLen);
}
return maxLen;
}
}Complexity Analysis
Time Complexity: O(n²)
For each of the n starting indices, we may scan up to n elements in the inner loop. In the worst case (e.g., a perfectly turbulent array), the inner loop runs nearly the full array length for every starting index near the beginning. This gives us O(n²) total comparisons.
Space Complexity: O(1)
We only use a few integer variables (max_len, cur_len, prev_sign, cur_sign). No additional data structures are allocated.
Why This Approach Is Not Efficient
The brute force approach takes O(n²) time because it re-examines overlapping portions of the array for every starting index. When we find that the turbulent subarray starting at index 1 extends to index 5, we already know the comparison results for pairs (1,2), (2,3), (3,4), (4,5). But when we then check starting index 2, we recompute comparisons for (2,3), (3,4), (4,5) from scratch.
With n up to 4 × 10^4, the brute force performs up to ~8 × 10^8 operations, which will likely exceed time limits.
The key insight is: when we process pairs left-to-right, we can carry forward information about what kind of turbulent subarray we can extend at each position. If the current pair goes "up" (increase), it can only extend a turbulent subarray that last went "down" (decrease), and vice versa. This observation leads us to a dynamic programming approach that avoids redundant work.
Better Approach - Dynamic Programming with Two States
Intuition
Instead of rechecking from every starting index, we can track the state of the turbulent subarray as we scan the array once.
Imagine you are riding a wave on the ocean. At any moment, you are either going up (the wave is rising) or going down (the wave is falling). A valid turbulent pattern is like a perfect zigzag wave — every time you go up, the next movement must be down, and vice versa.
We define two DP arrays:
inc[i]= length of the longest turbulent subarray ending at indexiwherearr[i-1] < arr[i](the last movement was an increase)dec[i]= length of the longest turbulent subarray ending at indexiwherearr[i-1] > arr[i](the last movement was a decrease)
The transitions are elegant:
- If
arr[i] > arr[i-1](current pair is increasing):inc[i] = dec[i-1] + 1(extend a previously-decreasing subarray), anddec[i] = 1(can't extend a decreasing pattern with an increase) - If
arr[i] < arr[i-1](current pair is decreasing):dec[i] = inc[i-1] + 1(extend a previously-increasing subarray), andinc[i] = 1 - If
arr[i] == arr[i-1](equal): Both reset to 1
The answer is the maximum value across all inc[i] and dec[i].
Step-by-Step Explanation
Let's trace through arr = [9, 4, 2, 10, 7, 8, 8, 1, 9]:
Step 1: Initialize inc[0] = 1, dec[0] = 1 (single element is turbulent of length 1).
Step 2: i=1, compare arr[0]=9 vs arr[1]=4. 9 > 4 → decrease.
- dec[1] = inc[0] + 1 = 2 (extend the "increase" state by adding this decrease)
- inc[1] = 1 (can't extend an increase with a decrease)
- max_len = 2
Step 3: i=2, compare arr[1]=4 vs arr[2]=2. 4 > 2 → decrease.
- dec[2] = inc[1] + 1 = 1 + 1 = 2 (inc[1] was 1, so we get length 2)
- inc[2] = 1
- max_len = 2
Step 4: i=3, compare arr[2]=2 vs arr[3]=10. 2 < 10 → increase.
- inc[3] = dec[2] + 1 = 2 + 1 = 3 (extend [4, 2] + increase → [4, 2, 10])
- dec[3] = 1
- max_len = 3
Step 5: i=4, compare arr[3]=10 vs arr[4]=7. 10 > 7 → decrease.
- dec[4] = inc[3] + 1 = 3 + 1 = 4 (extend [4, 2, 10] + decrease → [4, 2, 10, 7])
- inc[4] = 1
- max_len = 4
Step 6: i=5, compare arr[4]=7 vs arr[5]=8. 7 < 8 → increase.
- inc[5] = dec[4] + 1 = 4 + 1 = 5 (extend [4, 2, 10, 7] + increase → [4, 2, 10, 7, 8])
- dec[5] = 1
- max_len = 5
Step 7: i=6, compare arr[5]=8 vs arr[6]=8. Equal!
- inc[6] = 1, dec[6] = 1 (both reset)
- max_len stays 5
Step 8: i=7, compare arr[6]=8 vs arr[7]=1. 8 > 1 → decrease.
- dec[7] = inc[6] + 1 = 1 + 1 = 2
- inc[7] = 1
- max_len stays 5
Step 9: i=8, compare arr[7]=1 vs arr[8]=9. 1 < 9 → increase.
- inc[8] = dec[7] + 1 = 2 + 1 = 3
- dec[8] = 1
- max_len stays 5
Final answer: 5.
DP with Two States — Tracking inc[] and dec[] Arrays — Watch how the inc and dec arrays build up as we scan left to right. When the direction alternates, the opposite state extends; when it doesn't, states reset.
Algorithm
- Create two arrays
incanddecof size n, initialized to 1 - For each index i from 1 to n-1:
- If
arr[i] > arr[i-1](increase):inc[i] = dec[i-1] + 1(extend previous decrease)dec[i] = 1(reset)
- Else if
arr[i] < arr[i-1](decrease):dec[i] = inc[i-1] + 1(extend previous increase)inc[i] = 1(reset)
- Else (equal):
inc[i] = 1,dec[i] = 1(both reset)
- If
- Return the maximum value across all
inc[i]anddec[i]
Code
class Solution {
public:
int maxTurbulenceSize(vector<int>& arr) {
int n = arr.size();
vector<int> inc(n, 1), dec(n, 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 = max({maxLen, inc[i], dec[i]});
}
return maxLen;
}
};class Solution:
def maxTurbulenceSize(self, arr: list[int]) -> int:
n = len(arr)
inc = [1] * n # length ending with increase
dec = [1] * n # length ending with decrease
max_len = 1
for i in range(1, n):
if arr[i] > arr[i - 1]:
inc[i] = dec[i - 1] + 1
dec[i] = 1
elif arr[i] < arr[i - 1]:
dec[i] = inc[i - 1] + 1
inc[i] = 1
else:
inc[i] = 1
dec[i] = 1
max_len = max(max_len, inc[i], dec[i])
return max_lenclass Solution {
public int maxTurbulenceSize(int[] arr) {
int n = arr.length;
int[] inc = new int[n];
int[] dec = new int[n];
Arrays.fill(inc, 1);
Arrays.fill(dec, 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;
}
}Complexity Analysis
Time Complexity: O(n)
We make a single pass through the array, performing O(1) work at each index: one comparison, two assignments, and one max operation. Total: O(n).
Space Complexity: O(n)
We allocate two arrays inc and dec of size n. Each stores one integer per array element, giving O(n) extra space.
Why This Approach Is Not Efficient
The DP approach with two arrays runs in O(n) time, which is optimal for this problem since we must examine every element at least once. However, it uses O(n) extra space for the inc and dec arrays.
Looking at the recurrence more closely, we see that inc[i] and dec[i] only depend on inc[i-1] and dec[i-1] — the values from the immediately preceding index. This means we never look back more than one step. We can replace the entire arrays with just two variables, reducing space from O(n) to O(1) while keeping the same O(n) time complexity.
This is a classic space optimization pattern in dynamic programming: when the current state depends only on the previous state, arrays can be replaced with constant-space variables.
Optimal Approach - Space-Optimized DP (Sliding Window)
Intuition
Since each DP state only depends on the previous position, we can collapse our two arrays into just two variables: f (length of turbulent subarray ending here with an increase) and g (length ending here with a decrease).
Think of it as sliding a window of size 2 across the array. At each position, we look at only the previous pair of (f, g) values and compute the new pair. We never need to look further back because the turbulent property is entirely local — it depends only on whether the most recent direction change alternated from the one before it.
This approach is also naturally a sliding window: we implicitly maintain a window of the current turbulent subarray. When the pattern continues (directions alternate), the window expands. When the pattern breaks (same direction or equal elements), the window contracts to the current position.
Step-by-Step Explanation
Let's trace through arr = [9, 4, 2, 10, 7, 8, 8, 1, 9] using just two variables f (inc) and g (dec):
Step 1: Initialize f=1, g=1, max_len=1.
Step 2: Compare 9 and 4. 9 > 4 → decrease.
- new_f = 1 (can't extend increase with decrease)
- new_g = f + 1 = 1 + 1 = 2 (extend previous increase state)
- f=1, g=2, max_len=2
Step 3: Compare 4 and 2. 4 > 2 → decrease.
- new_f = 1, new_g = f + 1 = 1 + 1 = 2
- f=1, g=2, max_len=2
Step 4: Compare 2 and 10. 2 < 10 → increase.
- new_f = g + 1 = 2 + 1 = 3 (extend previous decrease)
- new_g = 1
- f=3, g=1, max_len=3
Step 5: Compare 10 and 7. 10 > 7 → decrease.
- new_f = 1, new_g = f + 1 = 3 + 1 = 4
- f=1, g=4, max_len=4
Step 6: Compare 7 and 8. 7 < 8 → increase.
- new_f = g + 1 = 4 + 1 = 5
- new_g = 1
- f=5, g=1, max_len=5
Step 7: Compare 8 and 8. Equal → both reset.
- f=1, g=1, max_len=5
Step 8: Compare 8 and 1. 8 > 1 → decrease.
- new_f = 1, new_g = f + 1 = 1 + 1 = 2
- f=1, g=2, max_len=5
Step 9: Compare 1 and 9. 1 < 9 → increase.
- new_f = g + 1 = 2 + 1 = 3
- new_g = 1
- f=3, g=1, max_len=5
Final answer: 5.
Space-Optimized DP — Two Variables Sliding Through the Array — Watch how just two variables f and g track the turbulent subarray length as we scan left to right. When directions alternate, one variable grows by extending the other's value.
Algorithm
- Initialize
f = 1(inc length),g = 1(dec length),max_len = 1 - For each index i from 1 to n-1:
- If
arr[i] > arr[i-1](increase):new_f = g + 1(extend previous decrease)new_g = 1
- Else if
arr[i] < arr[i-1](decrease):new_f = 1new_g = f + 1(extend previous increase)
- Else (equal):
new_f = 1,new_g = 1
- Update
f = new_f,g = new_g - Update
max_len = max(max_len, f, g)
- If
- Return
max_len
Code
class Solution {
public:
int maxTurbulenceSize(vector<int>& arr) {
int n = arr.size();
int f = 1, g = 1; // f = inc length, g = dec length
int maxLen = 1;
for (int i = 1; i < n; i++) {
int nf, ng;
if (arr[i] > arr[i - 1]) {
nf = g + 1; // increase extends previous decrease
ng = 1;
} else if (arr[i] < arr[i - 1]) {
nf = 1;
ng = f + 1; // decrease extends previous increase
} else {
nf = 1;
ng = 1;
}
f = nf;
g = ng;
maxLen = max({maxLen, f, g});
}
return maxLen;
}
};class Solution:
def maxTurbulenceSize(self, arr: list[int]) -> int:
n = len(arr)
f = g = 1 # f = inc length, g = dec length
max_len = 1
for i in range(1, n):
if arr[i] > arr[i - 1]:
f, g = g + 1, 1 # increase extends previous decrease
elif arr[i] < arr[i - 1]:
f, g = 1, f + 1 # decrease extends previous increase
else:
f, g = 1, 1 # equal resets both
max_len = max(max_len, f, g)
return max_lenclass Solution {
public int maxTurbulenceSize(int[] arr) {
int n = arr.length;
int f = 1, g = 1; // f = inc length, g = dec length
int maxLen = 1;
for (int i = 1; i < n; i++) {
int nf, ng;
if (arr[i] > arr[i - 1]) {
nf = g + 1;
ng = 1;
} else if (arr[i] < arr[i - 1]) {
nf = 1;
ng = f + 1;
} else {
nf = 1;
ng = 1;
}
f = nf;
g = ng;
maxLen = Math.max(maxLen, Math.max(f, g));
}
return maxLen;
}
}Complexity Analysis
Time Complexity: O(n)
We traverse the array exactly once. At each position, we perform O(1) work: one comparison between adjacent elements, two variable assignments, and one max operation. Total: O(n).
Space Complexity: O(1)
We use only a fixed number of variables (f, g, nf, ng, maxLen) regardless of input size. The two DP arrays from the previous approach have been replaced by two scalar variables, achieving constant space.