Longest Turbulent Subarray LeetCode 978

LeetCode 978 — Longest Turbulent Subarray — gives you an integer array arr. A subarray is turbulent if the comparison sign alternates between each pair of adjacent elements. Specifically, for a subarray arr[i..j], the signs of arr[i]-arr[i+1], arr[i+1]-arr[i+2], etc. must alternate between positive and negative.

For example, [9, 4, 2, 10, 7, 8, 8, 1, 9] has a longest turbulent subarray of length 5: [4, 2, 10, 7, 8] where the comparisons are >, <, >, < — perfectly alternating. Equal adjacent elements break any turbulent run.

This is a linear scan problem that can be solved with two counters or a sliding window. The two-counter approach is the most elegant: track the length of the longest turbulent subarray ending at each position with the last comparison being up versus down.

Define inc as the length of the longest turbulent subarray ending at the current position where the last step was an increase (arr[i] > arr[i-1]). Define dec similarly for a decrease. Initialize both to 1.

For each position i from 1 to n-1, compare arr[i] with arr[i-1]. If arr[i] > arr[i-1], the last step is an increase: inc = dec + 1 (extending a subarray that ended with a decrease) and dec = 1 (reset). If arr[i] < arr[i-1], the last step is a decrease: dec = inc + 1 and inc = 1.

If arr[i] == arr[i-1], both counters reset to 1 because equal elements cannot be part of a turbulent subarray. Track the maximum of inc and dec across all positions. This single pass gives the answer in O(n) time.

Consider arr = [9, 4, 2, 10, 7, 8, 8, 1, 9]. Start: inc=1, dec=1, maxLen=1. i=1: 4<9 (decrease), dec=inc+1=2, inc=1. max=2. i=2: 2<4 (decrease), dec=inc+1=2, inc=1. max=2. Note: two consecutive decreases do not extend turbulence.

i=3: 10>2 (increase), inc=dec+1=3, dec=1. max=3. i=4: 7<10 (decrease), dec=inc+1=4, inc=1. max=4. i=5: 8>7 (increase), inc=dec+1=5, dec=1. max=5.

i=6: 8==8 (equal), inc=1, dec=1. max stays 5. i=7: 1<8 (decrease), dec=inc+1=2, inc=1. max=5. i=8: 9>1 (increase), inc=dec+1=3, dec=1. max=5. Answer: 5 (the subarray [4, 2, 10, 7, 8]).

An alternative approach uses a sliding window with left and right pointers. Expand right while the turbulent condition holds: the comparison between arr[right] and arr[right-1] must be opposite to the comparison between arr[right-1] and arr[right-2].

When the condition breaks — either equal elements or same-direction comparison — move left to right-1 (or right if equal). Track the maximum window length throughout. This variant is equivalent to the two-counter approach but explicitly maintains window boundaries.

The sliding window variant is sometimes easier to extend to related problems. For instance, if the problem asked for the actual turbulent subarray (not just its length), the window boundaries give you the start and end indices directly.

In Python, the two-counter solution is about 12 lines. Initialize inc = dec = result = 1. Loop from 1 to len(arr)-1. Use if/elif/else for the three cases (greater, less, equal). Update result = max(result, inc, dec) each iteration.

In Java, use the same pattern with int inc = 1, dec = 1, result = 1. The comparison logic is identical. Java's ternary operator can make the updates compact but an explicit if-else chain is clearer.

Edge case: if the array has length 1, return 1 immediately. If all elements are equal, the answer is 1. If the array is strictly increasing or decreasing, the answer is 2 (any two adjacent elements form a trivial turbulent subarray of length 2).

Time complexity is O(n) — a single pass through the array with O(1) work per element. No nested loops, no sorting, no data structure operations beyond simple comparisons and assignments.

Space complexity is O(1) — only three integer variables (inc, dec, result) regardless of input size. This is optimal; you cannot solve the problem without reading every element, and you need no auxiliary storage.

This is among the simplest O(n) solutions on LeetCode. The elegance lies in the cross-referencing of inc and dec: each counter builds on the other, naturally enforcing the alternating constraint without explicit bookkeeping.

Wiggle Subsequence (LeetCode 376) is the subsequence version: find the longest subsequence with alternating differences. It uses a similar two-counter approach (up and down) but does not require contiguity. The greedy solution counts direction changes.

Longest Mountain in Array (LeetCode 845) finds the longest subarray that first strictly increases then strictly decreases. It uses a different two-pointer approach but shares the idea of tracking state transitions between increase and decrease.

Maximum Alternating Subsequence Sum (LeetCode 1911) combines alternating structure with optimization. It uses DP with two states (even/odd position) similar to the inc/dec counters here. Practicing all three builds strong intuition for state-based linear scans.