Longest Turbulent Subarray

Difficulty: Medium Source: NeetCode

Problem

A subarray is turbulent if the comparison sign alternates between each adjacent pair of elements. That is, for arr[i], arr[i+1], arr[i+2], we need either arr[i] > arr[i+1] < arr[i+2] or arr[i] < arr[i+1] > arr[i+2]. Return the length of the longest turbulent subarray.

Example 1: Input: nums = [9, 4, 2, 10, 7, 8, 8, 1, 9] Output: 5 Explanation: [4, 2, 10, 7, 8] is turbulent.

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

Example 3: Input: nums = [100] Output: 1

Constraints:

• 1 <= nums.length <= 4 * 10^4
• 0 <= nums[i] <= 10^9

Prerequisites

Before attempting this problem, you should be comfortable with:

• Sliding Window — expanding and contracting a window based on conditions
• Maximum Subarray / Kadane’s — similar “extend or restart” pattern

1. Brute Force

Intuition

For each starting index, extend the subarray as long as it remains turbulent. Check each new element — if the alternating comparison property breaks, stop and record the length. Try all starting positions and track the maximum.

Algorithm

1. For each start i:
   • Extend j = i + 1, i + 2, ... while the subarray is turbulent.
   • Turbulence breaks when adjacent comparisons don’t alternate.
   • Record j - i as the length.
2. Return the maximum.

Solution

def maxTurbulenceSize(nums):
    n = len(nums)
    if n == 1:
        return 1

    def is_turbulent(arr):
        for i in range(1, len(arr) - 1):
            if arr[i - 1] < arr[i] and arr[i] < arr[i + 1]:
                return False
            if arr[i - 1] > arr[i] and arr[i] > arr[i + 1]:
                return False
            if arr[i - 1] == arr[i] or arr[i] == arr[i + 1]:
                return False
        return True

    max_len = 1
    for i in range(n):
        for j in range(i + 2, n + 1):
            if is_turbulent(nums[i:j]):
                max_len = max(max_len, j - i)
    return max_len


print(maxTurbulenceSize([9, 4, 2, 10, 7, 8, 8, 1, 9]))  # 5
print(maxTurbulenceSize([4, 8, 12, 16]))                  # 2
print(maxTurbulenceSize([100]))                            # 1

Complexity

• Time: O(n³) — outer loops are O(n²), inner check is O(n)
• Space: O(n)

2. Greedy — Sliding Window / Linear Scan

Intuition

Scan left to right. Keep track of the previous comparison direction (prev). If the current pair forms the opposite comparison from the previous (alternating), extend the current turbulent subarray. If they’re equal or continue in the same direction, the turbulence breaks — restart from the current position. This is exactly like Kadane’s “extend or restart” pattern.

Algorithm

1. Initialise max_len = 1, cur_len = 1.
2. For i from 1 to n-1:
   • Compute cmp: -1 if nums[i] < nums[i-1], 1 if greater, 0 if equal.
   • If cmp == 0: reset cur_len = 1.
   • Elif i == 1 or cmp == prev: cur_len = 2 (pair is valid but not alternating with before).
   • Else: cur_len += 1 (successfully alternated).
   • Update max_len = max(max_len, cur_len).
   • Set prev = cmp.
3. Return max_len.

Solution

def maxTurbulenceSize(nums):
    n = len(nums)
    if n == 1:
        return 1

    max_len = 1
    cur_len = 1
    prev = 0  # -1, 0, or 1

    for i in range(1, n):
        if nums[i] > nums[i - 1]:
            cmp = 1
        elif nums[i] < nums[i - 1]:
            cmp = -1
        else:
            cmp = 0

        if cmp == 0:
            cur_len = 1
        elif cmp == -prev:
            cur_len += 1  # alternated correctly
        else:
            cur_len = 2   # valid pair but didn't extend turbulence

        prev = cmp
        max_len = max(max_len, cur_len)

    return max_len


print(maxTurbulenceSize([9, 4, 2, 10, 7, 8, 8, 1, 9]))  # 5
print(maxTurbulenceSize([4, 8, 12, 16]))                  # 2
print(maxTurbulenceSize([100]))                            # 1
print(maxTurbulenceSize([9, 9]))                           # 1
print(maxTurbulenceSize([2, 0, 4, 3, 4]))                 # 5


# Cleaner version using sign comparison
def maxTurbulenceSize_v2(nums):
    n = len(nums)
    max_len = cur_len = 1

    for i in range(1, n):
        if nums[i] == nums[i - 1]:
            cur_len = 1
        elif i == 1:
            cur_len = 2
        elif (nums[i] > nums[i - 1]) != (nums[i - 1] > nums[i - 2]):
            cur_len += 1
        else:
            cur_len = 2
        max_len = max(max_len, cur_len)

    return max_len


print(maxTurbulenceSize_v2([9, 4, 2, 10, 7, 8, 8, 1, 9]))  # 5

Complexity

• Time: O(n)
• Space: O(1)

Common Pitfalls

Not resetting to 2 (not 1) when turbulence breaks. When the current pair (nums[i-1], nums[i]) forms a valid comparison but doesn’t continue the alternation, the subarray resets but includes the current pair. The length is 2, not 1.

Treating equal elements as valid turbulence. Two equal adjacent elements immediately break turbulence. Reset cur_len = 1 (not 2) when nums[i] == nums[i-1].

Comparing only adjacent pairs. Turbulence requires alternating comparisons — you need to check each pair against the previous pair’s direction, not just whether the current pair goes up or down.