{x}
blog image

Longest Turbulent Subarray

Given an integer array arr, return the length of a maximum size turbulent subarray of arr.

A subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.

More formally, a subarray [arr[i], arr[i + 1], ..., arr[j]] of arr is said to be turbulent if and only if:

  • For i <= k < j:
    • arr[k] > arr[k + 1] when k is odd, and
    • arr[k] < arr[k + 1] when k is even.
  • Or, for i <= k < j:
    • arr[k] > arr[k + 1] when k is even, and
    • arr[k] < arr[k + 1] when k is odd.

 

Example 1:

Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

Example 2:

Input: arr = [4,8,12,16]
Output: 2

Example 3:

Input: arr = [100]
Output: 1

 

Constraints:

  • 1 <= arr.length <= 4 * 104
  • 0 <= arr[i] <= 109

Solution Explanation: Longest Turbulent Subarray

This problem asks to find the length of the longest turbulent subarray within a given integer array. A turbulent subarray is defined as a subarray where the comparison sign between adjacent elements alternates (i.e., >, <, >, <, ... or <, >, <, >, ...).

Approach: Dynamic Programming

The most efficient approach is to use dynamic programming. We can avoid redundant calculations by storing the lengths of the longest turbulent subarrays ending at each index.

State Definition:

  • f[i]: Length of the longest turbulent subarray ending at index i with an increasing trend (i.e., the last comparison was arr[i-1] < arr[i]).
  • g[i]: Length of the longest turbulent subarray ending at index i with a decreasing trend (i.e., the last comparison was arr[i-1] > arr[i]).

Recurrence Relation:

For each index i > 0:

  • If arr[i-1] < arr[i], then f[i] = g[i-1] + 1 (extend the decreasing subarray). Otherwise, f[i] = 1 (start a new subarray).
  • If arr[i-1] > arr[i], then g[i] = f[i-1] + 1 (extend the increasing subarray). Otherwise, g[i] = 1 (start a new subarray).

The base case is f[0] = 1 and g[0] = 1. The final answer will be the maximum value among all f[i] and g[i].

Optimization:

Because f[i] and g[i] only depend on f[i-1] and g[i-1], we can optimize space complexity to O(1) by using only two variables (f and g) instead of arrays.

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
  • Space Complexity: O(1). We use only a constant amount of extra space to store the variables f and g.

Code Implementation (Python)

from itertools import pairwise
 
class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        ans = f = g = 1
        for a, b in pairwise(arr):
            ff = g + 1 if a < b else 1
            gg = f + 1 if a > b else 1
            f, g = ff, gg
            ans = max(ans, f, g)
        return ans

This Python code utilizes itertools.pairwise for efficient pairwise comparison of array elements. The rest directly implements the dynamic programming approach outlined above.

Code Implementation (Other Languages)

The implementations in Java, C++, Go, TypeScript, and Rust follow the same dynamic programming logic, adjusting syntax and data structures as needed for each language. The core algorithm remains consistent. See the complete code provided in the original response for examples in these other languages.