Longest Turbulent Subarray — LC 978 Sliding Window with Direction Toggle

Problem Statement#

A turbulent subarray has strictly alternating comparison signs between adjacent elements. Return the length of the longest turbulent subarray.

Constraints:

• 1 less than or equal to arr.length less than or equal to 4 times 10 to the 4
• 0 less than or equal to arr[i] less than or equal to 10 to the 9

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

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

Why This Problem Matters#

LeetCode 978 — Longest Turbulent Subarray is a Google and Amazon staple because it tests state-machine-style sliding windows. Most candidates default to two DP arrays — one tracking longest ending in greater-than, one tracking longest ending in less-than — but a tighter two-pointer expansion works in O(1) space. Knowing both demonstrates breadth.

The wrinkle: equality between adjacent elements terminates any turbulent run, regardless of which comparison sign came before. Forgetting this is the most common interview slip.

In production, alternation detection appears in oscillation analysis, signal processing for zero crossings, and trader-action sequence pattern recognition.

The Core Insight#

Define a sign function sign(a, b) returning -1, 0, or 1 for less-than, equal, or greater-than. Iterate over consecutive comparisons:

• If the current sign is 0, reset the current window to length 1 starting here.
• If the current sign equals the previous sign, the alternation breaks — reset the window to length 2 starting at the previous index.
• Otherwise, the alternation continues — extend the window by 1.

Track the maximum window length. This single-pass approach uses O(1) auxiliary memory.

The DP variant maintains two values, up[i] (longest turbulent run ending at i with arr[i - 1] less than arr[i]) and down[i] (the mirror), and gives the same answer with slightly more storage but cleaner reasoning.

Visual Dry Run#

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

Best length 5.

Solution (Optimal)#

class Solution:
    def maxTurbulenceSize(self, arr):
        def sign(a, b):
            if a < b:
                return -1
            if a > b:
                return 1
            return 0
        n = len(arr)
        if n < 2:
            return n
        best, run, prev = 1, 1, 0
        for i in range(1, n):
            s = sign(arr[i - 1], arr[i])
            if s == 0:
                run = 1
            elif s == prev:
                run = 2
            else:
                run += 1
            if run > best:
                best = run
            prev = s
        return best

var maxTurbulenceSize = function(arr) {
    const sign = (a, b) => a < b ? -1 : (a > b ? 1 : 0);
    const n = arr.length;
    if (n < 2) return n;
    let best = 1, run = 1, prev = 0;
    for (let i = 1; i < n; i++) {
        const s = sign(arr[i - 1], arr[i]);
        if (s === 0) run = 1;
        else if (s === prev) run = 2;
        else run += 1;
        if (run > best) best = run;
        prev = s;
    }
    return best;
};

Time: O(n) — single pass. Space: O(1).

Common Mistakes#

• Treating equality as a valid alternation step. Equality always breaks the run.
• Resetting run to 1 after a same-sign repeat instead of 2. The new pair still forms a length-2 turbulent subarray.
• Initializing best to 0 for n equals 1. Single-element arrays should return 1.
• Comparing arrays of length 0 — guard with the early return.
• Using arr[i] less than or equal to arr[i + 1] because of a typo, which collapses two states.

Interview Tips#

• State the sign function explicitly so the interviewer sees your state design.
• Trace [9, 4, 2, 10, 7, 8, 8, 1, 9] showing the equality reset at position 6.
• Compare DP and one-pass approaches for breadth.
• Mention edge cases: length 0, length 1, all equal.
• Emphasize O(1) space if the interviewer asks for memory bounds.

Follow-up Questions#

• What if equal pairs do not break the run but contribute length 1? Handle the equality case as run = max(run, 2).
• Return the indices of the longest turbulent subarray. Track (start, end) when best updates.
• Generalize to any custom comparator. Replace sign with the user-provided function.
• Stream version: process arrivals one at a time. Same algorithm, no array buffer.
• Find the count of distinct turbulent subarrays. Sum lengths of maximal turbulent runs.

Key Takeaways#

• LeetCode 978 — Longest Turbulent Subarray solves in O(n) time and O(1) space.
• Equal adjacent elements always break the run; reset to length 1.
• Same-sign repeats reset the run to length 2, not 1.
• A sign function returning -1, 0, 1 keeps the state machine clean.
• Asked at Google and Amazon as a sliding-window plus state-tracking warm-up.
• DP arrays up and down are an equivalent alternative formulation.
• The same alternation detection appears in zero-crossing and oscillation analysis problems.