AlgoMaster Logo

Longest Turbulent Subarray

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We need to find the longest subarray where the comparison between consecutive elements alternates between "greater than" and "less than." The pattern is a zigzag: up, down, up, down (or down, up, down, up). When two consecutive elements are equal, or the pattern stops alternating, the turbulent subarray breaks.

Equal adjacent elements (arr[k] == arr[k+1]) break any turbulent subarray. They count as neither "up" nor "down," they are flat, and a flat segment is not turbulent.

We can track the current turbulent subarray length while scanning left to right. At each position, we only need to know whether the comparison sign flipped relative to the previous comparison. If it flipped, the current subarray extends. If it did not flip, or the elements are equal, the count resets.

Key Constraints:

  • 1 <= arr.length <= 4 * 10^4 -- With n up to 40,000, an O(n^2) scan does up to 1.6 billion comparisons in the worst case, which is too slow. An O(n) pass is required.
  • 0 <= arr[i] <= 10^9 -- Values fit in a 32-bit signed integer, so comparing two elements cannot overflow. Equal adjacent elements must be handled separately because they break turbulence.

Approach 1: Brute Force

Intuition

Check every possible subarray and determine whether it is turbulent. For each starting index, extend the subarray as far as the turbulent pattern holds, then record the length.

A subarray starting at index i remains turbulent as long as each consecutive pair alternates between "up" and "down." Once two consecutive comparisons share the same sign (both up, both down, or either one flat), the turbulent subarray starting at i has ended.

Algorithm

  1. Initialize maxLen = 1 (a single element is always turbulent).
  2. For each starting index i from 0 to n - 2:
    • Set currentLen = 1.
    • For each index j from i + 1 to n - 1:
      • Compute the comparison between arr[j-1] and arr[j].
      • If arr[j-1] == arr[j], the subarray breaks. Stop extending from i.
      • If j == i + 1, this is the first pair so any non-equal comparison extends the subarray.
      • Otherwise, check if the current comparison sign is different from the previous one. If not, stop.
      • Increment currentLen and update maxLen.
  3. Return maxLen.

Visualization and Code

Loading animation...

The brute force re-examines overlapping subarrays. When the turbulent subarray starting at index i breaks at index j, the scan restarts at i + 1 and re-reads elements already visited. The next approach extends or resets a running turbulent length in a single pass, with no backtracking.

Approach 2: Dynamic Programming (Two-State Tracking)

Intuition

Instead of checking every starting position, work from the other direction: for each index i, find the longest turbulent subarray that ends at i.

A turbulent subarray ending at i ends in one of two ways: the last move was "up" (arr[i-1] < arr[i]), or the last move was "down" (arr[i-1] > arr[i]). Track two values:

  • inc: the length of the longest turbulent subarray ending at i where the last move was an increase (up).
  • dec: the length of the longest turbulent subarray ending at i where the last move was a decrease (down).

The transitions follow directly:

  • If arr[i] > arr[i-1] (up move): inc = dec + 1 (extend the subarray that ended with a down move), and dec = 1 (a "down" ending subarray resets to a single element).
  • If arr[i] < arr[i-1] (down move): dec = inc + 1 (extend the subarray that ended with an up move), and inc = 1.
  • If arr[i] == arr[i-1] (flat): both reset to 1.

This works because turbulence requires alternation. An "up" move can only follow a "down" move, so the only subarray it can extend is one whose previous step was a "down," whose length is exactly the old dec. The reverse holds for a "down" move.

Algorithm

  1. Initialize inc = 1, dec = 1, and maxLen = 1.
  2. Iterate from index 1 to n - 1:
    • If arr[i] > arr[i-1]: set inc = dec + 1, set dec = 1.
    • Else if arr[i] < arr[i-1]: set dec = inc + 1, set inc = 1.
    • Else (equal): set both inc = 1 and dec = 1.
    • Update maxLen with the maximum of inc and dec.
  3. Return maxLen.

Visualization and Code

Loading animation...