Problem Description

You are given an integer array arr. Your task is to find the length of the longest turbulent subarray within this array.

A subarray is considered turbulent when the comparison signs between adjacent elements alternate throughout the subarray. In other words, the elements should follow a zigzag pattern where they alternately increase and decrease (or decrease and increase).

Specifically, a subarray [arr[i], arr[i + 1], ..., arr[j]] is turbulent if one of these two patterns holds:

Pattern 1:

• When the index k is odd: arr[k] > arr[k + 1]
• When the index k is even: arr[k] < arr[k + 1]

Pattern 2:

• When the index k is even: arr[k] > arr[k + 1]
• When the index k is odd: arr[k] < arr[k + 1]

For example:

• [9, 4, 7, 2, 5] is turbulent because 9 > 4 < 7 > 2 < 5
• [1, 2, 3, 4] is not turbulent because it only increases
• [2, 2, 2] is not turbulent because consecutive elements are equal

The solution uses dynamic programming with two variables f and g to track the longest turbulent subarray ending at the current position. Variable f represents the length when the last comparison was "less than" (increasing), and g represents the length when the last comparison was "greater than" (decreasing). For each pair of adjacent elements, the algorithm updates these variables based on their comparison and maintains the maximum length found.

Intuition

The key insight is recognizing that a turbulent subarray has two alternating states: increasing and decreasing. When we're at any position in the array, we need to know what kind of turbulent subarray we can extend based on the previous element's state.

Think of it like riding a wave - you're either going up or down, and a valid turbulent pattern means you must alternate between these two states. If the last move was up, the next valid move must be down, and vice versa.

This naturally leads us to track two different states at each position:

• How long can our turbulent subarray be if we just went up (current element is greater than previous)?
• How long can our turbulent subarray be if we just went down (current element is less than previous)?

When we compare arr[i] with arr[i-1]:

• If arr[i] > arr[i-1] (we're going up), we can extend any turbulent subarray that was previously going down. So the new "up" length becomes the previous "down" length plus 1.
• If arr[i] < arr[i-1] (we're going down), we can extend any turbulent subarray that was previously going up. So the new "down" length becomes the previous "up" length plus 1.
• If arr[i] == arr[i-1], we can't form a turbulent pattern, so we reset both lengths to 1.

The beauty of this approach is that we only need to remember the lengths from the previous position, not the entire history. This is why we can optimize from using arrays f[i] and g[i] to just two variables f and g, making the space complexity O(1).

At each step, we track the maximum length seen so far, which gives us our final answer.

Learn more about Dynamic Programming and Sliding Window patterns.

Solution Approach

We implement the solution using dynamic programming with space optimization. Instead of maintaining arrays for all positions, we use two variables to track the current state:

• f: Length of the longest turbulent subarray ending at the current position with an increasing state (current element > previous element)
• g: Length of the longest turbulent subarray ending at the current position with a decreasing state (current element < previous element)

Algorithm Steps:

1. Initialize variables: Set ans = f = g = 1. All start at 1 because a single element forms a valid turbulent subarray of length 1.

2. Iterate through adjacent pairs: Use pairwise(arr) to get consecutive elements (a, b) where a = arr[i-1] and b = arr[i].

3. Update states based on comparison:

   • If a < b (increasing):
     • ff = g + 1 - We can extend the previous decreasing sequence by 1
     • gg = 1 - We can't extend a decreasing sequence when elements are increasing
   • If a > b (decreasing):
     • ff = 1 - We can't extend an increasing sequence when elements are decreasing
     • gg = f + 1 - We can extend the previous increasing sequence by 1
   • If a == b (equal):
     • Both ff = 1 and gg = 1 - Equal elements break the turbulent pattern

4. Update variables: Replace f and g with their new values ff and gg.

5. Track maximum: Update ans = max(ans, f, g) to keep track of the longest turbulent subarray found so far.

6. Return result: After processing all pairs, ans contains the maximum turbulent subarray length.

Time Complexity: O(n) where n is the length of the array, as we traverse the array once.

Space Complexity: O(1) as we only use a constant amount of extra space for variables f, g, ff, gg, and ans.

The elegance of this solution lies in its state transition logic - by tracking both increasing and decreasing states simultaneously and updating them based on the current comparison, we ensure that turbulent patterns are correctly identified and their lengths are properly calculated.

Example Walkthrough

Let's walk through the algorithm with array arr = [9, 4, 7, 2, 5].

Initial State:

• ans = 1, f = 1, g = 1
• f tracks turbulent length ending with increase (↑)
• g tracks turbulent length ending with decrease (↓)

Step 1: Compare 9 and 4

• Since 9 > 4 (decreasing ↓):
  • ff = 1 (can't extend an increase with a decrease)
  • gg = f + 1 = 1 + 1 = 2 (extend previous increase with this decrease)
• Update: f = 1, g = 2
• Update max: ans = max(1, 1, 2) = 2

Step 2: Compare 4 and 7

• Since 4 < 7 (increasing ↑):
  • ff = g + 1 = 2 + 1 = 3 (extend previous decrease with this increase)
  • gg = 1 (can't extend a decrease with an increase)
• Update: f = 3, g = 1
• Update max: ans = max(2, 3, 1) = 3
• Subarray [9, 4, 7] has length 3

Step 3: Compare 7 and 2

• Since 7 > 2 (decreasing ↓):
  • ff = 1 (can't extend an increase with a decrease)
  • gg = f + 1 = 3 + 1 = 4 (extend previous increase with this decrease)
• Update: f = 1, g = 4
• Update max: ans = max(3, 1, 4) = 4
• Subarray [9, 4, 7, 2] has length 4

Step 4: Compare 2 and 5

• Since 2 < 5 (increasing ↑):
  • ff = g + 1 = 4 + 1 = 5 (extend previous decrease with this increase)
  • gg = 1 (can't extend a decrease with an increase)
• Update: f = 5, g = 1
• Update max: ans = max(4, 5, 1) = 5
• Subarray [9, 4, 7, 2, 5] has length 5

Result: The longest turbulent subarray has length 5 (the entire array forms a turbulent pattern: 9 > 4 < 7 > 2 < 5).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array. The algorithm iterates through the array once using pairwise(arr), which generates n-1 consecutive pairs. For each pair, it performs a constant amount of work (comparisons, assignments, and max operations), resulting in linear time complexity.

Space Complexity: O(1). The algorithm uses only a fixed number of variables (ans, f, g, ff, gg, a, b) regardless of the input size. The pairwise function returns an iterator that doesn't create additional space proportional to the input, maintaining constant space usage.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing State Variable Meanings

One of the most common mistakes is misunderstanding what up_down and down_up represent. Developers often incorrectly assume these track the entire pattern rather than just the last comparison.

Incorrect Understanding:

• Thinking up_down means "pattern that goes up then down"
• Thinking down_up means "pattern that goes down then up"

Correct Understanding:

• up_down (or f in the original): Length of turbulent subarray ending at current position where the last comparison was "up" (previous < current)
• down_up (or g in the original): Length of turbulent subarray ending at current position where the last comparison was "down" (previous > current)

2. Incorrect State Transitions

A critical error occurs when updating the wrong state variable or using the wrong previous state for extension.

Common Mistake:

if prev_val < curr_val:
    new_up_down = up_down + 1  # WRONG! Should extend down_up, not up_down
    new_down_up = 1

Why it's wrong: When current comparison is "up" (prev < curr), we need a previous "down" comparison to form a turbulent pattern. Therefore, we should extend down_up, not up_down.

Correct Approach:

if prev_val < curr_val:
    new_up_down = down_up + 1  # Correct: extend the opposite pattern
    new_down_up = 1

3. Forgetting to Handle Equal Elements

Equal consecutive elements break the turbulent pattern, but developers sometimes forget this case entirely or handle it incorrectly.

Mistake:

if prev_val < curr_val:
    new_up_down = down_up + 1
    new_down_up = 1
elif prev_val > curr_val:
    new_up_down = 1
    new_down_up = up_down + 1
# Missing the else case for equal elements!

Solution: Always include the equality case and reset both states to 1:

else:  # prev_val == curr_val
    new_up_down = 1
    new_down_up = 1

4. Not Updating Maximum Length Inside the Loop

Some implementations forget to update the maximum length at each iteration, only checking at the end.

Mistake:

for i in range(1, len(arr)):
    # ... state updates ...
    up_down = new_up_down
    down_up = new_down_up
# Only checking max at the end - might miss intermediate maximums
return max(up_down, down_up)

Solution: Update the maximum at each iteration:

for i in range(1, len(arr)):
    # ... state updates ...
    up_down = new_up_down
    down_up = new_down_up
    max_length = max(max_length, up_down, down_up)

5. Edge Case Handling

Failing to handle arrays with 0 or 1 element can cause index errors or incorrect results.

Solution: Add explicit checks at the beginning:

if len(arr) <= 1:
    return len(arr)

6. Variable Naming Confusion

Using ambiguous variable names like f and g makes the code harder to understand and more prone to logical errors. Clear, descriptive names like up_down and down_up (or even better: last_was_increasing and last_was_decreasing) help prevent mistakes and improve code maintainability.