LeetCode 978: Longest Turbulent Subarray

Problem Restatement

We are given an integer array arr.

We need to return the length of the longest contiguous subarray where the comparison signs between adjacent elements alternate.

That means the subarray must go up, down, up, down, or down, up, down, up.

For example:

[9, 4, 2, 10, 7]

The comparisons are:

9 > 4
4 > 2
2 < 10
10 > 7

This is not fully turbulent because the first two comparisons both go downward.

But this subarray is turbulent:

[4, 2, 10, 7]

Its comparisons are:

4 > 2
2 < 10
10 > 7

The signs alternate, so its length is 4.

The official constraints are 1 <= arr.length <= 4 * 10^4 and 0 <= arr[i] <= 10^9. The problem asks for the maximum length of a turbulent subarray.

Input and Output

Function shape:

def maxTurbulenceSize(arr: list[int]) -> int:
    ...

Examples

Example 1:

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

One longest turbulent subarray is:

[4, 2, 10, 7, 8]

The comparisons are:

4 > 2
2 < 10
10 > 7
7 < 8

The signs alternate.

Answer:

5

Example 2:

arr = [4, 8, 12, 16]

Every comparison goes upward:

4 < 8
8 < 12
12 < 16

No length 3 subarray is turbulent because the signs do not alternate.

Any two unequal adjacent numbers form a turbulent subarray of length 2.

Answer:

2

Example 3:

arr = [100]

A single element is a valid turbulent subarray of length 1.

Answer:

1

First Thought: Check Every Subarray

The direct solution is to try every subarray and check whether its comparisons alternate.

For each starting index, extend the subarray to the right while the signs keep alternating.

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

        for start in range(n):
            for end in range(start + 1, n):
                ok = True

                for k in range(start + 1, end):
                    left = arr[k - 1]
                    mid = arr[k]
                    right = arr[k + 1]

                    if not ((left < mid > right) or (left > mid < right)):
                        ok = False
                        break

                if ok:
                    best = max(best, end - start + 1)

        return best

This follows the definition directly.

Problem With Brute Force

The brute force solution checks many subarrays, and each subarray may require another scan.

That is too slow for an array length up to 4 * 10^4.

We need to process the array once and keep only the information needed for the current turbulent run.

Key Insight

For each adjacent pair, only three things can happen:

arr[i] > arr[i - 1]
arr[i] < arr[i - 1]
arr[i] == arr[i - 1]

A turbulent subarray continues only when the current comparison has the opposite sign from the previous comparison.

So we can keep two lengths:

If the current value is greater than the previous value, then the previous comparison must have been downward.

So:

up = down + 1
down = 1

If the current value is smaller than the previous value, then the previous comparison must have been upward.

So:

down = up + 1
up = 1

If the values are equal, turbulence breaks:

up = 1
down = 1

Algorithm

Start with:

up = 1
down = 1
answer = 1

Then scan from index 1 to the end.

For each index i:

1. If arr[i] > arr[i - 1], extend a previous downward run.
2. If arr[i] < arr[i - 1], extend a previous upward run.
3. If arr[i] == arr[i - 1], reset both lengths to 1.
4. Update the answer with the larger of up and down.

Correctness

At every index i, up stores the length of the longest turbulent subarray ending at i whose last comparison is upward.

Similarly, down stores the length of the longest turbulent subarray ending at i whose last comparison is downward.

When arr[i] > arr[i - 1], the last comparison is upward. For the subarray to remain turbulent, the previous comparison must have been downward. Therefore, the best upward turbulent subarray ending at i has length down + 1 from the previous step.

When arr[i] < arr[i - 1], the same reasoning applies in the opposite direction. The best downward turbulent subarray ending at i has length up + 1 from the previous step.

When the two adjacent values are equal, there is no greater-than or less-than sign, so no turbulent subarray of length greater than 1 can continue through this pair. Both states reset to 1.

The algorithm updates the global answer after processing each index. Since every turbulent subarray has some ending index, and the algorithm considers the best valid turbulent subarray ending at each index, the maximum value recorded is the correct answer.

Complexity

Implementation

class Solution:
    def maxTurbulenceSize(self, arr: list[int]) -> int:
        up = 1
        down = 1
        answer = 1

        for i in range(1, len(arr)):
            if arr[i] > arr[i - 1]:
                up = down + 1
                down = 1
            elif arr[i] < arr[i - 1]:
                down = up + 1
                up = 1
            else:
                up = 1
                down = 1

            answer = max(answer, up, down)

        return answer

Code Explanation

We initialize both states to 1:

up = 1
down = 1
answer = 1

A single element is always a turbulent subarray of length 1.

Then we scan adjacent pairs:

for i in range(1, len(arr)):

If the current value is larger:

if arr[i] > arr[i - 1]:

then the last comparison is upward. It can only extend a previous downward state:

up = down + 1
down = 1

If the current value is smaller:

elif arr[i] < arr[i - 1]:

then the last comparison is downward. It can only extend a previous upward state:

down = up + 1
up = 1

If the values are equal, the turbulent run breaks:

else:
    up = 1
    down = 1

After each step, we update the best length:

answer = max(answer, up, down)

Finally, return the longest length found:

return answer

Testing

def run_tests():
    s = Solution()

    assert s.maxTurbulenceSize([9, 4, 2, 10, 7, 8, 8, 1, 9]) == 5
    assert s.maxTurbulenceSize([4, 8, 12, 16]) == 2
    assert s.maxTurbulenceSize([100]) == 1
    assert s.maxTurbulenceSize([1, 1, 1]) == 1
    assert s.maxTurbulenceSize([1, 2, 1, 2, 1]) == 5
    assert s.maxTurbulenceSize([1, 2, 2, 1]) == 2

    print("all tests passed")

run_tests()