Longest Turbulent Subarray
Medium · Sliding Window · Array · Dynamic Programming · Sliding Window
Problem
A subarray is turbulent when the comparison between each pair of neighboring elements flips direction every time: a c b d …. Equal neighbors break turbulence, and any single element is turbulent by itself.
Given an integer array arr, return the length of its longest turbulent subarray.
Examples
Input: arr = [2,5,1,6,6,3] Output: 4
2 1 3 alone is only length 2.
Input: arr = [7,7,7] Output: 1
Every neighbor pair is equal, so only single elements are turbulent.
Input: arr = [9,4,2,10,7,8,8,1,9] Output: 5
4 > 2 7 4 > 2 goes down twice, and the equal pair 8, 8 ends it.
Constraints
- 1 <= len(arr) <= 4 · 10^4
- 0 <= arr[i] <= 10^9
Approaches
- Baseline: extend from every start — time O(n²), space O(1)
Follow-up
How would you count every turbulent subarray instead of finding the longest? The run length ending at i is exactly the number of turbulent subarrays that end there, so the answer is the sum of those lengths. That is the first use case below.
Related problems
Start free on Cariara · Coding problems · System design studio
