Watch 10 video solutions for Longest Turbulent Subarray, a medium level problem involving Array, Dynamic Programming, Sliding Window. This walkthrough by NeetCodeIO has 22,539 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
i <= k < j:
arr[k] > arr[k + 1] when k is odd, andarr[k] < arr[k + 1] when k is even.i <= k < j:
arr[k] > arr[k + 1] when k is even, andarr[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 * 1040 <= arr[i] <= 109Problem Overview: You are given an integer array and need the length of the longest turbulent subarray. A subarray is turbulent when comparison signs alternate between adjacent elements (e.g., a[i] > a[i+1] < a[i+2] > a[i+3]). The task is to scan the array and find the maximum length segment where this alternating pattern holds.
Approach 1: Sliding Window (O(n) time, O(1) space)
This approach treats the problem as a variable-length window over the array. Iterate through the array and compare each pair of adjacent elements. Maintain a window where the comparison sign alternates between > and <. If the pattern breaks (equal elements or repeated comparison direction), reset the window start to the previous index. Each step updates the current window length and the global maximum. Because each element is processed once and the window moves forward without backtracking, the time complexity is O(n) with constant O(1) space.
The key insight is tracking the sign of the last comparison. When the current comparison multiplied by the previous comparison is -1, the alternating pattern continues. Otherwise the turbulent sequence must restart. This makes sliding window a natural fit for the problem.
Approach 2: Dynamic Programming (O(n) time, O(n) space)
The dynamic programming approach tracks two states for every index: the longest turbulent subarray ending at that index with the last comparison being >, and the longest ending with <. If arr[i] > arr[i-1], extend the sequence that previously ended with <. If arr[i] < arr[i-1], extend the sequence that ended with >. Otherwise both states reset to length 1.
You can implement this with two arrays up[] and down[], or reduce memory to two variables. Each step updates the current state based on the previous index. The algorithm still scans the array once, giving O(n) time complexity. The straightforward DP version uses O(n) space, though it can be optimized to O(1).
Recommended for interviews: The sliding window solution is what interviewers usually expect. It directly models the alternating comparison constraint and achieves optimal O(n) time with constant memory. Explaining the DP state transition first can demonstrate reasoning about alternating relationships, but implementing the sliding window shows stronger practical problem‑solving and familiarity with common array patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window | O(n) | O(1) | Best general solution. Minimal memory and straightforward single-pass logic. |
| Dynamic Programming | O(n) | O(n) (or O(1) optimized) | Useful for understanding alternating state transitions or when explaining the pattern step-by-step. |