Longest Turbulent Subarray

Master this topic with zero to advance depth.

Longest Turbulent Subarray

Find the maximum size of a 'turbulent' subarray where the comparison sign flips between adjacent pairs (e.g., a > b < c > d).

Visual Representation

arr = [9, 4, 2, 10, 7, 8, 8, 1, 9]

[9 > 4]          (Turbulent? Yes, Len 2)
[9 > 4 < 2]      (Turbulent? No, 4 > 2 is same sign as 9 > 4)
[2 < 10 > 7 < 8] (Turbulent? Yes, Len 4)
[8 == 8]         (Reset window)

Medium

Examples

Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5

Approach 1

Level I: Brute Force

Intuition

Iterate through all possible starting points i. For each i, expand the subarray as long as it remains turbulent. Track the maximum length.

Thought Process

Outer loop i from 0 to n-1.
Inner loop j starts from i.
Check if arr[j...j+1] satisfies the turbulent condition based on arr[j-1...j].
If it breaks, record length and start next i.
Maximize the findings.

⏱ O(N^2)💾 O(1)

Detailed Dry Run

i	Turbulent Subarray	Length
0	[9, 4]	2
1	[4, 2]	2
2	[2, 10, 7, 8]	4
6	[8, 8]	1

java

public class Main {
    public static int maxTurbulenceSize(int[] arr) {
        int n = arr.length, maxLen = 1;
        for (int i = 0; i < n; i++) {
            int cur = 1;
            for (int j = i + 1; j < n; j++) {
                if (j == i + 1) {
                    if (arr[j] != arr[j-1]) cur++;
                    else break;
                } else {
                    if ((arr[j-1] > arr[j-2] && arr[j] < arr[j-1]) ||
                        (arr[j-1] < arr[j-2] && arr[j] > arr[j-1])) cur++;
                    else break;
                }
            }
            maxLen = Math.max(maxLen, cur);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(maxTurbulenceSize(new int[]{9,4,2,10,7,8,8,1,9})); // 5
    }
}

Approach 2

Level III: Optimal (Sliding Window)

Intuition

Thought Process

We essentially track the 'alternating sign' property. If the comparison between arr[i-1] and arr[i] matches the alternating expectation, we expand. If they are equal, we reset. If they have the same sign as the previous pair, we slide the start to the previous element.

Patterns

Comparison Matching: Use Integer.compare or sign functions.
Dynamic Anchor: Move anchor point based on where turbulence breaks.

⏱ O(N)💾 O(1)

Detailed Dry Run

i	Comparison	anchor	res
1	9 > 4 (1)	0	2
2	4 > 2 (1)	1	2
3	2 < 10 (-1)	2	2
4	10 > 7 (1)	2	3
5	7 < 8 (-1)	2	4

java

public class Main {
    public static int maxTurbulenceSize(int[] arr) {
        int n = arr.length, res = 1, anchor = 0;
        for (int i = 1; i < n; i++) {
            int c = Integer.compare(arr[i-1], arr[i]);
            if (c == 0) anchor = i;
            else if (i == n-1 || c * Integer.compare(arr[i], arr[i+1]) != -1) {
                res = Math.max(res, i - anchor + 1);
                anchor = i;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(maxTurbulenceSize(new int[]{9,4,2,10,7,8,8,1,9})); // 5
    }
}

⚠️ Common Pitfalls & Tips

Equal elements (e.g., 8, 8) break the turbulence immediately and reset the anchor to the current index.

← Previous QuestionSubarray Product Less Than K

Next Question →Replace the Substring for Balanced String

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.