Longest Turbulent Subarray

Medium
336.

Longest Turbulent Subarray

Longest Turbulent Subarray is a medium coding problem on arrays, dynamic programming and sliding window, asked in Amazon and Google interviews.

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 <= 40
  • 0 <= arr[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var maxTurbulenceSize = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 40
  • 0 <= arr[i] <= 1000

Hints for Longest Turbulent Subarray

  1. Hint 1

    Track two running lengths: the best turbulent run ending with a rise, and the one ending with a fall.

  2. Hint 2

    A rise sets up = down + 1 and resets down to 1; a fall does the mirror image.

  3. 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

  1. Start up = down = best = 1.
  2. For each adjacent pair: rise → up = down + 1, down = 1; fall → down = up + 1, up = 1; equal → both 1.
  3. Track the maximum of up and down.

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 best

Java

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