Longest Turbulent Subarray: Tracking Alternating Comparisons

LeetCode's Longest Turbulent Subarray (problem 978) asks you to find the longest subarray where consecutive comparisons alternate between strictly increasing and strictly decreasing. It is a medium-level problem, but the optimal solution is short and elegant once you see the pattern behind it.

The problem

You are given an integer array arr. A subarray is turbulent if the comparison signs between consecutive elements strictly alternate. In other words, for every index k in the turbulent subarray (except the first and last), either:

• arr[k-1] is greater than arr[k] and arr[k] is less than arr[k+1], or
• arr[k-1] is less than arr[k] and arr[k] is greater than arr[k+1]

A single element is trivially turbulent (length 1). Two elements with different values form a turbulent subarray of length 2. Equal consecutive elements break any turbulent run.

Return the length of the longest turbulent subarray.

Approach: track inc and dec counters

The key idea is to maintain two counters as you scan the array from left to right:

• inc: the length of the longest turbulent subarray ending at the current index where the last step was an increase (arr[i] > arr[i-1])
• dec: the length of the longest turbulent subarray ending at the current index where the last step was a decrease (arr[i] is less than arr[i-1])

At each index, you compare arr[i] to arr[i-1] and update accordingly:

• If arr[i] > arr[i-1]: the last step is an increase, and it extends a chain that previously ended with a decrease. So inc = dec + 1, and dec resets to 1.
• If arr[i] is less than arr[i-1]: the last step is a decrease, and it extends a chain that previously ended with an increase. So dec = inc + 1, and inc resets to 1.
• If arr[i] == arr[i-1]: equal elements break any turbulent chain. Both inc and dec reset to 1.

After each step, update the running maximum.

Step-by-step walkthrough

Let's trace through arr = [9, 4, 2, 10, 7, 8, 8, 1, 9]. At each index we track inc, dec, and best.

The answer is 5, from the subarray [4, 2, 10, 7, 8] spanning indices 1 through 5. The alternation pattern is: 4 > 2 < 10 > 7 < 8.

Notice what happens at index 6: arr[6] == arr[5], so both counters reset to 1. The chain starting from index 1 cannot extend through the equal pair. After the reset, a new chain begins from index 6, but it only reaches length 3 by the end of the array.

The code

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

    inc = 1
    dec = 1
    best = 1

    for i in range(1, n):
        if arr[i] > arr[i - 1]:
            inc = dec + 1
            dec = 1
        elif arr[i] < arr[i - 1]:
            dec = inc + 1
            inc = 1
        else:
            inc = 1
            dec = 1
        best = max(best, inc, dec)

    return best

The loop body is four lines of logic. Here is what each branch does:

1. Increase (arr[i] > arr[i-1]): This step goes up, so it can extend a chain that previously went down. Set inc = dec + 1. Reset dec to 1 because the chain ending in a decrease just broke.
2. Decrease (arr[i] is less than arr[i-1]): Mirror of the above. Set dec = inc + 1. Reset inc to 1.
3. Equal: No turbulence possible through equal elements. Both counters reset.
4. After each branch, update best with the larger of inc and dec.

One subtle detail: the order of assignment matters. When you write inc = dec + 1 followed by dec = 1, the new inc uses the old dec value. If you reversed the order and reset dec first, you would lose the information you need. In the decrease branch, the same logic applies in reverse.

Complexity analysis

The brute force approach checks every subarray to see if it is turbulent. The DP approach processes each element exactly once with constant work per element.

The building blocks

Alternating state tracking

The core pattern here is maintaining two variables that alternate roles depending on the direction of comparison. This same idea appears in:

• Wiggle Subsequence: track the length of the longest subsequence (not subarray) with alternating ups and downs. The state machine is nearly identical, but you skip non-alternating elements instead of resetting.
• Paint House: alternate between cost states depending on the previous choice.

Whenever a problem involves two alternating conditions, consider tracking them with a pair of variables that swap on each transition.

DP with constant space

Many DP problems start with a full table, then get optimized down to O(1) space because each cell only depends on the previous row or column. This problem skips the table entirely. You only ever need the previous values of inc and dec, so two variables suffice.

The same optimization applies to problems like Fibonacci, Climbing Stairs, and House Robber, where the recurrence looks back a fixed number of steps.

Edge cases

• Single element [5]: return 1. A single element is trivially turbulent.
• All equal [3, 3, 3]: every comparison is equal, so no turbulent chain extends past length 1. Return 1.
• Two distinct elements [1, 2]: the pair is turbulent. Return 2.
• Strictly increasing [1, 2, 3, 4]: no alternation ever happens. The longest turbulent subarray is any adjacent pair, length 2.
• Strictly decreasing [4, 3, 2, 1]: same reasoning as strictly increasing. Return 2.
• Perfect zigzag [1, 3, 1, 3, 1]: every comparison alternates. The entire array is turbulent. Return 5.
• Equal pair in the middle [1, 3, 3, 1]: the equal pair at indices 1 and 2 splits the array. The longest turbulent subarray is length 2 (either [1, 3] or [3, 1]).

From understanding to recall

You have traced through the algorithm and seen how the inc and dec counters swap to track the alternating pattern. The logic is compact, but the details matter: which counter gets old value + 1, which one resets, and what happens on equality. These are the kinds of things that feel obvious while reading but slip away when you try to write the code from scratch.

The building blocks here, alternating state tracking and constant-space DP, are reusable across many problems. Once you can write the inc/dec swap from memory, problems like Wiggle Subsequence and similar alternation patterns become much faster to solve.

Related posts

• Longest Continuous Increasing Subsequence - Simpler version tracking only one direction
• Longest Mountain in Array - Finding up-then-down patterns in arrays
• Wiggle Subsequence - Similar alternating comparison pattern but for subsequences