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] <= 109The goal of #978 Longest Turbulent Subarray is to find the maximum length of a subarray where the comparison signs between adjacent elements alternate (e.g., >, <, >, <). A common strategy is to track how comparisons change as you iterate through the array.
A practical solution uses a sliding window. As you move through the array, compare adjacent elements and determine whether the current comparison alternates with the previous one. If the pattern breaks (equal elements or repeated comparison direction), reset the window starting point. Continuously update the maximum window length during traversal.
Another perspective uses dynamic programming, maintaining two counters that track the length of turbulent sequences ending with > and <. Depending on the current comparison, update these counters accordingly while resetting the opposite one.
Both methods run in O(n) time since the array is processed once, while using O(1) additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window | O(n) | O(1) |
| Dynamic Programming (Up/Down counters) | O(n) | O(1) |
NeetCodeIO
In this approach, a sliding window technique is used to identify the longest turbulent subarray. We maintain two pointers: 'start' and 'end'. Initially, 'start' is set to 0, and 'end' is used to iterate over the array. At each step, we check the relationship between consecutive elements to determine the turbulence. When the pattern breaks, we calculate the length of the turbulent segment and adjust the pointers accordingly.
Time Complexity: O(n), where n is the length of the array, as the solution involves a single pass over the array.
Space Complexity: O(1), as it uses a constant amount of extra space.
1#include <stdio.h>
2int maxTurbulenceSize(int* arr, int arrSize) {
3 if (arrSize < 2) return arrSize;
4This C implementation iterates over the array, checking each adjacent pair of elements to determine if they are part of a turbulent sequence. It adjusts the length of the current turbulent subarray accordingly and keeps track of the maximum found so far.
This approach utilizes dynamic programming to maintain two arrays: inc and dec, which record the lengths of increasing and decreasing turbulent subarrays that end at each index. The solution updates these values based on the conditions of the current element relative to the previous one, and tracks the global maximum using the values in inc and dec.
Time Complexity: O(n), as the array is traversed once.
Space Complexity: O(1), minimal additional space is used.
1Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
A turbulent sequence breaks when two adjacent comparisons are the same or when two elements are equal. When this happens, the alternating pattern is lost and the current window or counters must be reset.
Yes, variations of this problem appear in coding interviews at large tech companies. It tests array traversal, pattern recognition, and sliding window or dynamic programming skills.
No complex data structure is required for this problem. Most efficient solutions rely on simple variables or counters to track alternating comparisons while iterating through the array.
The optimal approach typically uses a sliding window or dynamic programming technique. By tracking whether comparisons between adjacent elements alternate, we can update the window length in one pass. This results in O(n) time complexity and constant extra space.
This C implementation uses two variables, inc and dec, to manage the lengths of turbulent subarrays. During each iteration, they are updated based on comparisons between current and previous elements.