LeetCode 978 - Longest Turbulent Subarray

The problem asks us to find the length of the longest turbulent subarray inside a given integer array arr. A subarray is considered turbulent if the relationship between every adjacent pair of numbers alternates between greater than () and less than (<).

leetcodemediumarraydynamic-programmingsliding-window

LeetCode Problem 978

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Sliding Window

Solution

Problem Understanding

The problem asks us to find the length of the longest turbulent subarray inside a given integer array arr.

A subarray is considered turbulent if the relationship between every adjacent pair of numbers alternates between greater than (>) and less than (<). In other words, the comparison sign must continuously flip as we move through the subarray.

For example, consider:

[4, 2, 10, 7, 8]

The comparisons are:

4 > 2 < 10 > 7 < 8

Since the comparison alternates between > and < at every step, this subarray is turbulent.

The problem does not care which pattern starts first. Both of the following are valid:

a > b < c > d

and

a < b > c < d

The input is an integer array arr, where:

  • arr[i] represents the value at index i
  • The array length can be as large as 4 * 10^4
  • Each value can be as large as 10^9

The output should be the maximum length of any contiguous turbulent subarray.

The constraints are important because they immediately rule out inefficient solutions. Since n can be up to 40,000, an O(n²) solution may be too slow in practice, and anything worse is definitely infeasible. This strongly suggests that we should aim for a linear or near-linear approach.

There are several important edge cases to think about upfront.

If the array contains only one element, the answer must be 1 because a single element is trivially turbulent.

If adjacent elements are equal, turbulence immediately breaks because neither > nor < holds. For example:

[9, 9]

This has a longest turbulent subarray of length 1.

Arrays that are strictly increasing or strictly decreasing are also interesting:

[1, 2, 3, 4]

The comparisons never alternate, so the best answer is 2, because any adjacent pair is technically turbulent.

We also need to handle cases where turbulence breaks and restarts multiple times.

Approaches

Brute Force Approach

A straightforward solution is to examine every possible subarray and check whether it is turbulent.

For every starting index i, we try every ending index j, then verify whether the comparisons alternate correctly between every adjacent pair.

To validate a subarray, we compare consecutive elements and ensure that:

  • No adjacent values are equal
  • The comparison direction alternates

If any comparison fails, the subarray is not turbulent.

This method is correct because it exhaustively checks all possibilities and guarantees that the maximum valid length will eventually be found.

However, it is computationally expensive. There are O(n²) subarrays, and checking each subarray can take O(n) time, resulting in O(n³) complexity. Even with some optimization, it remains too slow for n = 40,000.

Key Insight for an Optimal Solution

The key observation is that turbulence depends only on the relationship between adjacent elements.

Instead of repeatedly checking entire subarrays, we can process the array in one pass and track the current turbulent window.

At every index, we compare:

arr[i - 1] and arr[i]

There are three possibilities:

  1. arr[i] > arr[i - 1]
  2. arr[i] < arr[i - 1]
  3. arr[i] == arr[i - 1]

If the comparison alternates compared to the previous comparison, the turbulent sequence continues.

If the comparison becomes equal, turbulence resets completely.

If the comparison repeats the same direction, the current turbulent sequence breaks, but we can restart from the previous element.

This naturally leads to a sliding window / dynamic programming style solution that runs in linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Checks every subarray and validates turbulence
Optimal O(n) O(1) Tracks alternating comparisons in one pass

Algorithm Walkthrough

Optimal Sliding Window Approach

We maintain:

  • current_length, the length of the current turbulent subarray
  • max_length, the best answer found so far
  • previous_comparison, which stores whether the previous pair was increasing, decreasing, or equal

We represent comparisons as:

1  -> increasing
-1 -> decreasing
0  -> equal

Step 1: Initialize Variables

Start with:

max_length = 1
current_length = 1
previous_comparison = 0

A single element is always turbulent, so the minimum answer is 1.

Step 2: Iterate Through Adjacent Pairs

For each index i from 1 to n - 1, compare:

arr[i] with arr[i - 1]

Determine the current comparison:

  • 1 if increasing
  • -1 if decreasing
  • 0 if equal

Step 3: Handle Equal Elements

If:

arr[i] == arr[i - 1]

Then turbulence breaks immediately.

Reset:

current_length = 1

because the current element starts a new possible subarray.

Step 4: Extend a Turbulent Sequence

If the current comparison alternates with the previous one:

current_comparison != previous_comparison

and neither is 0, then the turbulent pattern continues.

Increase:

current_length += 1

Step 5: Restart the Sequence

If the comparison direction repeats:

>, >

or

<, <

then turbulence breaks.

However, the current pair itself forms a valid turbulent subarray of length 2.

So reset:

current_length = 2

Step 6: Update the Maximum

After processing each element:

max_length = max(max_length, current_length)

Store the current comparison for the next iteration.

Why it works

The algorithm maintains the invariant that current_length always represents the length of the longest turbulent subarray ending at the current index.

Whenever adjacent comparisons alternate, we safely extend the current subarray. When the pattern breaks, we restart at the smallest valid turbulent segment. Since every index is processed exactly once and every possible turbulent ending is considered, the maximum length found is guaranteed to be correct.

Python Solution

from typing import List

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        n = len(arr)

        if n == 1:
            return 1

        max_length = 1
        current_length = 1
        previous_comparison = 0

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

            if current_comparison == 0:
                current_length = 1
            elif current_comparison == -previous_comparison:
                current_length += 1
            else:
                current_length = 2

            max_length = max(max_length, current_length)
            previous_comparison = current_comparison

        return max_length

The implementation begins by handling the smallest edge case, an array of length one.

We then maintain three variables:

  • max_length stores the best answer.
  • current_length tracks the turbulent subarray ending at the current index.
  • previous_comparison remembers the direction of the previous comparison.

At each iteration, we determine whether the current pair is increasing, decreasing, or equal.

If the elements are equal, turbulence resets because equal numbers cannot satisfy either alternating condition.

If the current comparison is the opposite of the previous one, we extend the turbulent segment.

Otherwise, turbulence breaks, but the current adjacent pair still forms a valid turbulent subarray of length 2.

Finally, we update the global maximum after each step.

Go Solution

func maxTurbulenceSize(arr []int) int {
	n := len(arr)

	if n == 1 {
		return 1
	}

	maxLength := 1
	currentLength := 1
	previousComparison := 0

	for i := 1; i < n; i++ {
		currentComparison := 0

		if arr[i] > arr[i-1] {
			currentComparison = 1
		} else if arr[i] < arr[i-1] {
			currentComparison = -1
		}

		if currentComparison == 0 {
			currentLength = 1
		} else if currentComparison == -previousComparison {
			currentLength++
		} else {
			currentLength = 2
		}

		if currentLength > maxLength {
			maxLength = currentLength
		}

		previousComparison = currentComparison
	}

	return maxLength
}

The Go implementation mirrors the Python solution closely.

Go slices are already reference types, so no special array handling is needed. Since the constraints fit comfortably inside Go's int, integer overflow is not a concern here. We explicitly initialize currentComparison to 0, which naturally represents equal elements.

Unlike Python, Go does not provide a built in max() function for integers, so we update maxLength using a simple conditional comparison.

Worked Examples

Example 1

Input:

arr = [9,4,2,10,7,8,8,1,9]
i Pair Comparison Previous Current Length Max Length
1 9,4 -1 0 2 2
2 4,2 -1 -1 2 2
3 2,10 1 -1 3 3
4 10,7 -1 1 4 4
5 7,8 1 -1 5 5
6 8,8 0 1 1 5
7 8,1 -1 0 2 5
8 1,9 1 -1 3 5

Final answer:

5

The longest turbulent segment is:

[4,2,10,7,8]

Example 2

Input:

arr = [4,8,12,16]
i Pair Comparison Previous Current Length Max Length
1 4,8 1 0 2 2
2 8,12 1 1 2 2
3 12,16 1 1 2 2

Final answer:

2

No alternating pattern exists.

Example 3

Input:

arr = [100]

Since there is only one element:

answer = 1

Complexity Analysis

Measure Complexity Explanation
Time O(n) We scan the array once
Space O(1) Only a few variables are used

The algorithm processes each adjacent pair exactly once. No nested loops are used, and no auxiliary data structures grow with input size. This gives linear runtime and constant extra space.

Test Cases

solution = Solution()

assert solution.maxTurbulenceSize([9,4,2,10,7,8,8,1,9]) == 5  # example case
assert solution.maxTurbulenceSize([4,8,12,16]) == 2  # monotonic increasing
assert solution.maxTurbulenceSize([100]) == 1  # single element

assert solution.maxTurbulenceSize([9,9]) == 1  # equal adjacent elements
assert solution.maxTurbulenceSize([1,2]) == 2  # smallest turbulent pair
assert solution.maxTurbulenceSize([2,1]) == 2  # decreasing pair

assert solution.maxTurbulenceSize([1,2,1,2,1]) == 5  # fully turbulent
assert solution.maxTurbulenceSize([1,2,3,4,5]) == 2  # strictly increasing
assert solution.maxTurbulenceSize([5,4,3,2,1]) == 2  # strictly decreasing

assert solution.maxTurbulenceSize([1,1,1,1]) == 1  # all equal
assert solution.maxTurbulenceSize([9,4,9]) == 3  # short turbulence
assert solution.maxTurbulenceSize([4,8,4,8,4,8]) == 6  # long alternating
assert solution.maxTurbulenceSize([1,3,2,2,4,5]) == 3  # reset after equality
assert solution.maxTurbulenceSize([100,50,100,50,100]) == 5  # repeated alternation
Test Why
[9,4,2,10,7,8,8,1,9] Validates the main example
[4,8,12,16] Monotonic increasing sequence
[100] Smallest valid input
[9,9] Equal values break turbulence
[1,2] Minimal increasing pair
[2,1] Minimal decreasing pair
[1,2,1,2,1] Fully alternating sequence
[1,2,3,4,5] No alternation
[5,4,3,2,1] Strictly decreasing
[1,1,1,1] Entire array equal
[9,4,9] Small valid turbulence
[4,8,4,8,4,8] Longest possible turbulence
[1,3,2,2,4,5] Equality resets sequence
[100,50,100,50,100] Repeated alternating comparisons

Edge Cases

Single Element Array

An array with only one element is trivially turbulent because there are no adjacent comparisons to violate the rule.

This case can easily cause bugs if the implementation assumes at least one comparison exists. Our implementation handles it immediately with:

if n == 1:
    return 1

Equal Adjacent Elements

Equal values are especially important because they completely break turbulence.

For example:

[4, 4, 5]

The pair 4 == 4 cannot participate in any alternating comparison pattern. Our implementation resets current_length to 1, ensuring the algorithm correctly starts fresh afterward.

Monotonic Arrays

Arrays that are entirely increasing or entirely decreasing can be deceptive.

For example:

[1,2,3,4]

A naive implementation might incorrectly return 1, but any adjacent pair of elements already forms a valid turbulent subarray of length 2.

Our implementation correctly resets to 2 whenever the comparison direction repeats, ensuring the minimum valid adjacent turbulent pair is preserved.