978. Longest Turbulent Subarray - Solution

The problem

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:

For i <= k < j:
- arr[k] > arr[k + 1] when k is odd, and
- arr[k] < arr[k + 1] when k is even.
Or, for i <= k < j:
- arr[k] > arr[k + 1] when k is even, and
- arr[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 * 10⁴
0 <= arr[i] <= 10⁹

Approach overview

Problem 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 1: Sliding Window

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.

Python

def maxTurbulenceSize(arr):
    n = len(arr)
    max_len = 1
    current_len = 1
    for i in range(1, n):
        if arr[i - 1] < arr[i]:
            current_len = 2 if i % 2 == 0 else 1
        elif arr[i - 1] > arr[i]:
            current_len = 2 if i % 2 == 1 else 1
        else:
            current_len = 1
        max_len = max(max_len, current_len)
    return max_len

Java

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        int max_len = 1, current_len = 1;
        for (int i = 1; i < n; ++i) {
            if (arr[i - 1] < arr[i]) {
                current_len = (i % 2 == 0) ? 2 : 1;
            } else if (arr[i - 1] > arr[i]) {
                current_len = (i % 2 == 1) ? 2 : 1;
            } else {
                current_len = 1;
            }
            max_len = Math.max(max_len, current_len);
        }
        return max_len;
    }
}

C++

#include <vector>
using namespace std;
int maxTurbulenceSize(vector<int>& arr) {
    int n = arr.size();
    if (n < 2) return n;
    int max_len = 1, current_len = 1;
    for (int i = 1; i < n; ++i) {
        if (arr[i - 1] < arr[i]) {
            current_len = (i % 2 == 0) ? 2 : 1;
        } else if (arr[i - 1] > arr[i]) {
            current_len = (i % 2 == 1) ? 2 : 1;
        } else {
            current_len = 1;
        }
        max_len = max(max_len, current_len);
    }
    return max_len;
}

JavaScript

var maxTurbulenceSize = function(arr) {
    let n = arr.length;
    let max_len = 1, current_len = 1;
    for (let i = 1; i < n; ++i) {
        if (arr[i - 1] < arr[i]) {
            current_len = (i % 2 === 0) ? 2 : 1;
        } else if (arr[i - 1] > arr[i]) {
            current_len = (i % 2 === 1) ? 2 : 1;
        } else {
            current_len = 1;
        }
        max_len = Math.max(max_len, current_len);
    }
    return max_len;
};

#include <stdio.h>
int maxTurbulenceSize(int* arr, int arrSize) {
    if (arrSize < 2) return arrSize;
    int max_len = 1, current_len = 1;
    for (int i = 1; i < arrSize; ++i) {
        if (arr[i - 1] < arr[i]) {
            current_len = (i % 2 == 0) ? 2 : 1;
        } else if (arr[i - 1] > arr[i]) {
            current_len = (i % 2 == 1) ? 2 : 1;
        } else {
            current_len = 1;
        }
        max_len = (current_len > max_len) ? current_len : max_len;
    }
    return max_len;
}

public class Solution {
    public int MaxTurbulenceSize(int[] arr) {
        int n = arr.Length;
        int max_len = 1, current_len = 1;
        for (int i = 1; i < n; ++i) {
            if (arr[i - 1] < arr[i]) {
                current_len = (i % 2 == 0) ? 2 : 1;
            } else if (arr[i - 1] > arr[i]) {
                current_len = (i % 2 == 1) ? 2 : 1;
            } else {
                current_len = 1;
            }
            max_len = Math.Max(max_len, current_len);
        }
        return max_len;
    }
}

The Python version of the solution iterates through the list and uses a conditional logic to determine the length of turbulent subarrays, updating the maximum length found with the built-in max function.

Complexity

Time Complexity: O(n), iterating over the list.
Space Complexity: O(1), uses a fixed number of variables.

Try this approach in the editor

Approach 2: Dynamic Programming

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.

Python

def maxTurbulenceSize(arr):
    inc = 1
    dec = 1
    max_len = 1
    for i in range(1, len(arr)):
        if arr[i - 1] < arr[i]:
            inc = dec + 1
            dec = 1
        elif arr[i - 1] > arr[i]:
            dec = inc + 1
            inc = 1
        else:
            inc = dec = 1
        max_len = max(max_len, inc, dec)
    return max_len

Java

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int inc = 1;
        int dec = 1;
        int max_len = 1;
        for (int i = 1; i < arr.length; ++i) {
            if (arr[i - 1] < arr[i]) {
                inc = dec + 1;
                dec = 1;
            } else if (arr[i - 1] > arr[i]) {
                dec = inc + 1;
                inc = 1;
            } else {
                inc = dec = 1;
            }
            max_len = Math.max(max_len, Math.max(inc, dec));
        }
        return max_len;
    }
}

C++

#include <vector>
using namespace std;
int maxTurbulenceSize(vector<int>& arr) {
    int inc = 1, dec = 1, max_len = 1;
    for (int i = 1; i < arr.size(); ++i) {
        if (arr[i - 1] < arr[i]) {
            inc = dec + 1;
            dec = 1;
        } else if (arr[i - 1] > arr[i]) {
            dec = inc + 1;
            inc = 1;
        } else {
            inc = dec = 1;
        }
        max_len = max({max_len, inc, dec});
    }
    return max_len;
}

JavaScript

var maxTurbulenceSize = function(arr) {
    let inc = 1, dec = 1;
    let max_len = 1;
    for (let i = 1; i < arr.length; ++i) {
        if (arr[i - 1] < arr[i]) {
            inc = dec + 1;
            dec = 1;
        } else if (arr[i - 1] > arr[i]) {
            dec = inc + 1;
            inc = 1;
        } else {
            inc = dec = 1;
        }
        max_len = Math.max(max_len, inc, dec);
    }
    return max_len;
};

#include <stdio.h>
int maxTurbulenceSize(int* arr, int arrSize) {
    if (arrSize < 2) return arrSize;
    int inc = 1, dec = 1, max_len = 1;
    for (int i = 1; i < arrSize; ++i) {
        if (arr[i - 1] < arr[i]) {
            inc = dec + 1;
            dec = 1;
        } else if (arr[i - 1] > arr[i]) {
            dec = inc + 1;
            inc = 1;
        } else {
            inc = dec = 1;
        }
        if (inc > max_len) max_len = inc;
        if (dec > max_len) max_len = dec;
    }
    return max_len;
}

public class Solution {
    public int MaxTurbulenceSize(int[] arr) {
        int inc = 1, dec = 1, max_len = 1;
        for (int i = 1; i < arr.Length; ++i) {
            if (arr[i - 1] < arr[i]) {
                inc = dec + 1;
                dec = 1;
            } else if (arr[i - 1] > arr[i]) {
                dec = inc + 1;
                inc = 1;
            } else {
                inc = dec = 1;
            }
            max_len = Math.Max(max_len, Math.Max(inc, dec));
        }
        return max_len;
    }
}

This Python function employs dynamic programming logic to evaluate the turbulent pattern. Two variables, inc and dec, capture subarray lengths, updated dynamically on each iteration.

Complexity

Time Complexity: O(n), requires a single traverse through the list.
Space Complexity: O(1), employs a fixed number of extra variables.

Try this approach in the editor

Approach 3: Dynamic Programming

We define f[i] as the length of the longest turbulent subarray ending at nums[i] with an increasing state, and g[i] as the length of the longest turbulent subarray ending at nums[i] with a decreasing state. Initially, f[0] = 1, g[0] = 1. The answer is max(f[i], g[i]).

For i \gt 0, if nums[i] \gt nums[i - 1], then f[i] = g[i - 1] + 1, otherwise f[i] = 1; if nums[i] \lt nums[i - 1], then g[i] = f[i - 1] + 1, otherwise g[i] = 1.

Since f[i] and g[i] are only related to f[i - 1] and g[i - 1], two variables can be used instead of arrays.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

TypeScript

function maxTurbulenceSize(arr: number[]): number {
    let f = 1;
    let g = 1;
    let ans = 1;
    for (let i = 1; i < arr.length; ++i) {
        const ff = arr[i - 1] < arr[i] ? g + 1 : 1;
        const gg = arr[i - 1] > arr[i] ? f + 1 : 1;
        f = ff;
        g = gg;
        ans = Math.max(ans, f, g);
    }
    return ans;
}

func maxTurbulenceSize(arr []int) int {
	ans, f, g := 1, 1, 1
	for i, x := range arr[1:] {
		ff, gg := 1, 1
		if arr[i] < x {
			ff = g + 1
		}
		if arr[i] > x {
			gg = f + 1
		}
		f, g = ff, gg
		ans = max(ans, max(f, g))
	}
	return ans
}

Rust

impl Solution {
    pub fn max_turbulence_size(arr: Vec<i32>) -> i32 {
        let mut ans = 1;
        let mut f = 1;
        let mut g = 1;

        for i in 1..arr.len() {
            let ff = if arr[i - 1] < arr[i] { g + 1 } else { 1 };
            let gg = if arr[i - 1] > arr[i] { f + 1 } else { 1 };
            f = ff;
            g = gg;
            ans = ans.max(f.max(g));
        }

        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sliding Window	Time Complexity: O(n), iterating over the list. Space Complexity: O(1), uses a fixed number of variables.
Dynamic Programming	Time Complexity: O(n), requires a single traverse through the list. Space Complexity: O(1), employs a fixed number of extra variables.
Dynamic Programming	–

Complexity analysis

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.

Frequently asked questions

Is Longest Turbulent Subarray easy or hard?

Longest Turbulent Subarray is classified as a Medium difficulty problem. The challenge lies in correctly handling alternating comparisons and resetting the window when the pattern breaks. Once you recognize the sliding window pattern, the implementation becomes straightforward.

Longest Turbulent Subarray Python/Java solution

Both Python and Java implementations follow the same sliding window logic. Track the sign of the previous comparison and update the window length as you iterate. The code typically uses a single loop and a few variables, resulting in O(n) time and O(1) space.

How to solve Longest Turbulent Subarray in O(n)?

Iterate through the array and compute the comparison between consecutive elements. Track the previous comparison sign and extend the current window when the sign alternates. If the sign repeats or elements are equal, reset the window start. Maintain the maximum window length during the scan.

What is the best approach for Longest Turbulent Subarray?

The sliding window approach is the most efficient and commonly expected solution. It scans the array once while tracking whether adjacent comparisons alternate between greater and smaller. This produces an O(n) time complexity with O(1) extra space, making it optimal for large arrays.

Is Longest Turbulent Subarray asked at Google/Amazon/Meta?

Longest Turbulent Subarray appears in interview preparation lists for companies that emphasize array and pattern-detection problems. Variants of alternating comparison or longest pattern subarray questions have been reported in interviews at companies like Amazon and Google.

What data structure is used in Longest Turbulent Subarray?

The problem mainly uses arrays and simple integer comparisons. The optimal approach applies the sliding window technique over the array, while an alternative solution uses dynamic programming states such as 'up' and 'down' arrays to track alternating comparisons.

What is the time complexity of Longest Turbulent Subarray?

The optimal solution runs in O(n) time because the array is traversed once while maintaining a current turbulent window. Each element contributes to at most one extension or reset of the window. Space complexity is O(1) for the sliding window implementation.

Longest Turbulent Subarray solution and explanation

The problem

Approach overview

Approach 1: Sliding Window

Approach 2: Dynamic Programming

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Longest Turbulent Subarray solution and explanation

The problem

Approach overview

Approach 1: Sliding Window

Approach 2: Dynamic Programming

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems