Longest Turbulent Subarray

LeetCode 978

Problem Description

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 (e.g., arr[i-1] > arr[i] < arr[i+1]).

Turbulent Pattern Visualization

Maximum turbulent subarray: [4, 2, 10, 7, 8] with pattern > < > < (length = 5)

Approach: Dynamic Programming with Two States

Track two states at each position:

• state[i][0] = length of turbulent subarray ending at i where arr[i-1] > arr[i] (goes down)
• state[i][1] = length of turbulent subarray ending at i where arr[i-1] < arr[i] (goes up)

State Transition Diagram

Transition Rules

Condition	Action
arr[i] < arr[i-1]	state[i][0] = state[i-1][1] + 1 (flip from up to down)
arr[i] > arr[i-1]	state[i][1] = state[i-1][0] + 1 (flip from down to up)
arr[i] == arr[i-1]	Reset both states to 0

Example Walkthrough

Complexity Analysis

• Time Complexity: $O(N)$ - single pass through array
• Space Complexity: $O(N)$ using the state array

Optimization Note: Can be reduced to $O(1)$ by only storing the previous state.

Solution

public int MaxTurbulenceSize(int[] A)
{
    int n = A.Length;
    int[,] state = new int[n, 2];
    int maxLen = 0;

    for (int i = 1; i < n; i++)
    {
        if (A[i] < A[i - 1])
        {
            state[i, 0] = state[i - 1, 1] + 1;
            maxLen = Math.Max(maxLen, state[i, 0]);
        }
        else if (A[i] > A[i - 1])
        {
            state[i, 1] = state[i - 1, 0] + 1;
            maxLen = Math.Max(maxLen, state[i, 1]);
        }
    }

    return maxLen + 1;

}

Key Insights

Interview Tips

• Two-state DP: When tracking alternating patterns, use two states
• Space optimization: Only need previous state, can use O(1) space
• Edge case: Array length 1 returns 1 (single element is trivially turbulent)