Longest Turbulent Subarray — Solution in Python, Java & C++
Longest Turbulent Subarray solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Longest Turbulent Subarray is a medium coding problem on arrays, dynamic programming and sliding window, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Sliding Window
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A subarray is turbulent if the comparison sign between every pair of adjacent elements flips: a < b > c < d > … or a > b < c > d < ….
Given an integer array arr, return the length of the longest turbulent subarray.
Example 1
Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: The subarray [4,2,10,7,8].
Example 2
Input: arr = [4,8,12,16]
Output: 2
Example 3
Input: arr = [100]
Output: 1
Constraints
1 <= arr.length <= 400 <= arr[i] <= 1000
Hints for Longest Turbulent Subarray
Hint 1
Track two running lengths: the best turbulent run ending with a rise, and the one ending with a fall.
Hint 2
A rise sets
up = down + 1and resetsdownto 1; a fall does the mirror image.Hint 3
Equal neighbours break turbulence entirely — reset both to 1.
How to solve Longest Turbulent Subarray
Track the longest turbulent run ending with a rise and with a fall; a rise sets up = down + 1 and resets down, a fall does the mirror, equality resets both.
Approach
- Start
up = down = best = 1. - For each adjacent pair: rise →
up = down + 1, down = 1; fall →down = up + 1, up = 1; equal → both 1. - Track the maximum of
upanddown.
Why it works
A turbulent subarray must alternate, so the run ending in a rise can only extend one ending in a fall and vice versa; equal neighbours cannot belong to any turbulent subarray of length > 1.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Unlike Wiggle Subsequence this is a subarray — resets are mandatory, not optional.
Reference solution
Python
def maxTurbulenceSize(arr) -> int:
best = up = down = 1
for i in range(1, len(arr)):
if arr[i] > arr[i - 1]:
up, down = down + 1, 1
elif arr[i] < arr[i - 1]:
down, up = up + 1, 1
else:
up = down = 1
best = max(best, up, down)
return bestJava
public static int maxTurbulenceSize(int[] arr) {
int best = 1, up = 1, down = 1;
for (int i = 1; i < arr.length; i++) {
if (arr[i] > arr[i - 1]) {
int prevDown = down;
up = prevDown + 1;
down = 1;
} else if (arr[i] < arr[i - 1]) {
int prevUp = up;
down = prevUp + 1;
up = 1;
} else {
up = 1;
down = 1;
}
best = Math.max(best, Math.max(up, down));
}
return best;
}C++
int maxTurbulenceSize(vector<int>& arr) {
int best = 1, up = 1, down = 1;
for (int i = 1; i < (int) arr.size(); i++) {
if (arr[i] > arr[i - 1]) {
int prevDown = down;
up = prevDown + 1;
down = 1;
} else if (arr[i] < arr[i - 1]) {
int prevUp = up;
down = prevUp + 1;
up = 1;
} else {
up = 1;
down = 1;
}
best = max(best, max(up, down));
}
return best;
}JavaScript
var maxTurbulenceSize = function(arr) {
let best = 1, up = 1, down = 1;
for (let i = 1; i < arr.length; i++) {
if (arr[i] > arr[i - 1]) {
const prevDown = down;
up = prevDown + 1;
down = 1;
} else if (arr[i] < arr[i - 1]) {
const prevUp = up;
down = prevUp + 1;
up = 1;
} else {
up = 1;
down = 1;
}
const cur = Math.max(up, down);
if (cur > best) best = cur;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming