#978

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Longest Turbulent Subarray

Find the length of the longest subarray where element comparisons alternate, using state transition dynamic programming efficiently.

array dynamic programming sliding window

Problem Statement

Given an integer array arr, determine the length of its longest turbulent subarray. A subarray is turbulent if each adjacent pair of elements flips between greater-than and less-than comparisons consistently.

Formally, a subarray [arr[i], arr[i+1], ..., arr[j]] is turbulent if for every k with i <= k < j, arr[k] > arr[k+1] when k is even and arr[k] < arr[k+1] when k is odd, or vice versa. Return the maximum length of any turbulent subarray within arr.

Examples

Example 1

Input: arr = [9,4,2,10,7,8,8,1,9]

Output: 5

arr[1] > arr[2] arr[4] < arr[5]

Example 2

Input: arr = [4,8,12,16]

Output: 2

Example details omitted.

Example 3

Input: arr = [100]

Output: 1

Example details omitted.

Constraints

1 <= arr.length <= 4 * 104
0 <= arr[i] <= 109

Solution Approach

Sliding Window with State Tracking

Use two pointers to track the start and end of a turbulent subarray. Incrementally check comparison flips between adjacent elements, and adjust the window when the turbulence condition fails. This ensures linear scanning without revisiting elements unnecessarily.

Dynamic Programming States

Maintain two variables representing the length of subarrays ending in 'up' and 'down' comparisons. Update these states iteratively: if arr[i] > arr[i-1], increase 'up' and reset 'down'; if arr[i] < arr[i-1], increase 'down' and reset 'up'. The maximum of these states gives the answer.

Optimization and Edge Cases

Handle single-element arrays and consecutive equal elements by resetting states appropriately. This prevents overcounting and ensures correctness under all array configurations, especially for arrays with repeated values or minimal length.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

The solution scans the array once, updating two state variables per element, yielding O(N) time. Only a constant number of variables are used, so space complexity is O(1).

What Interviewers Usually Probe

Focus on edge cases like repeated values or single-element arrays.
Expect clarification on handling the first element comparison and index parity.
Consider discussing the trade-off between sliding window and explicit DP arrays.

Common Pitfalls or Variants

Common pitfalls

Failing to reset state when consecutive elements are equal, leading to incorrect subarray length.
Confusing index parity with comparison direction, breaking the turbulence check.
Using O(N^2) nested loops instead of linear state tracking, which is inefficient for large arrays.

Follow-up variants

Return the actual subarray instead of just its length, requiring backtracking of start and end indices.
Compute turbulent subarrays on a 2D grid flattened row-wise, combining row and column alternations.
Find maximum turbulent segments where only '>' alternates with '<=' instead of strict '<', changing state transitions slightly.

FAQ

What is a turbulent subarray in this problem?

A turbulent subarray alternates between 'greater than' and 'less than' comparisons for every consecutive pair of elements.

Can this problem be solved without dynamic programming?

Yes, using a sliding window with careful comparison checks can achieve O(N), but tracking DP states ensures clarity and correctness.

How do equal consecutive elements affect the solution?

Equal elements break the turbulence, so states must reset, and the current subarray window should start after the repeated elements.

What is the time and space complexity?

Time complexity is O(N) due to single pass, and space complexity is O(1) using only two state variables.

How does the state transition dynamic programming pattern apply here?

It tracks lengths of 'up' and 'down' sequences iteratively, updating maximum length as the array is scanned to enforce alternating comparisons efficiently.

terminal

Solution

Solution 1: Dynamic Programming

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

1

2

3

4

5

6

7

8

9

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        ans = f = g = 1
        for a, b in pairwise(arr):
            ff = g + 1 if a < b else 1
            gg = f + 1 if a > b else 1
            f, g = ff, gg
            ans = max(ans, f, g)
        return ans

Continue Practicing

#1031 maximum sum of two non overlapping subarrays #718 maximum length of repeated subarray #689 maximum sum of 3 non overlapping subarrays