Longest Turbulent Subarray [Medium] — Two Pointer Direction Track
Sanjeev SharmaAdvertisement
Problem Statement
A subarray is turbulent if comparisons between consecutive elements alternate between > and <. Find the maximum length.
Input: [9,4,2,10,7,8,8,1,9] → Output: 5 ([4,2,10,7,8])
Intuition
Track previous comparison direction. If direction changes, extend; else reset. Use inc, dec pointers for runs of increasing/decreasing.
Solutions
C++
int maxTurbulenceSize(vector<int>& arr) {
int n=arr.size(), ans=1, inc=1, dec=1;
for(int i=1;i<n;i++){
if(arr[i]>arr[i-1]){inc=dec+1;dec=1;}
else if(arr[i]<arr[i-1]){dec=inc+1;inc=1;}
else{inc=dec=1;}
ans=max(ans,max(inc,dec));
}
return ans;
}
Python
def maxTurbulenceSize(arr: list[int]) -> int:
n = len(arr)
if n < 2: return n
ans = inc = dec = 1
for i in range(1, n):
if arr[i] > arr[i-1]: inc, dec = dec+1, 1
elif arr[i] < arr[i-1]: dec, inc = inc+1, 1
else: inc = dec = 1
ans = max(ans, inc, dec)
return ans
Complexity
- Time: O(n), Space: O(1)
Advertisement
