978. Longest Turbulent Subarray - Explanation

Description

You are 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 = [2,4,3,2,2,5,1,4]

Output: 4

Explanation: The longest turbulent subarray is [2,5,1,4].

Example 2:

Input: arr = [1,1,2]

Output: 2

Constraints:

1 <= arr.length <= 40,000
0 <= arr[i] <= 1,000,000,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

A turbulent subarray alternates between increasing and decreasing comparisons. For each starting index, we extend as far as possible while the comparison sign keeps flipping. If two adjacent elements are equal, the turbulent pattern breaks immediately. We track the maximum length found across all starting positions.

Algorithm

Initialize res = 1 to store the maximum turbulent subarray length.
For each starting index i:
- Skip if the next element equals the current one (no valid turbulent pair).
- Determine the initial comparison sign (greater or less).
- Extend j forward while the sign alternates and elements are not equal.
- Update res with the length j - i + 1.
Return res.

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

        for i in range(n - 1):
            if arr[i] == arr[i + 1]:
                continue

            sign = 1 if arr[i] > arr[i + 1] else 0
            j = i + 1
            while j < n - 1:
                if arr[j] == arr[j + 1]:
                    break
                curSign = 1 if arr[j] > arr[j + 1] else 0
                if sign == curSign:
                    break
                sign = curSign
                j += 1

            res = max(res, j - i + 1)

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$ extra space.

2. Dynamic Programming (Top-Down)

Intuition

We can think of this problem recursively: from each position, we try to extend a turbulent subarray by checking if the next comparison matches the expected direction. If we expect a decrease and find one, we flip the expectation and recurse. Memoization prevents redundant calculations by caching results for each (index, expected sign) pair.

Algorithm

Define dfs(i, sign) which returns the length of the longest turbulent subarray starting at index i with the expected comparison direction sign.
Base case: if i == n - 1, return 1 (single element).
If the comparison between arr[i] and arr[i+1] matches the expected sign, return 1 + dfs(i + 1, opposite sign).
Otherwise, return 1.
Cache results in a memo table to avoid recomputation.
Try starting from each index with both possible initial signs and return the maximum.

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        n = len(arr)
        memo = {}

        def dfs(i, sign):
            if i == n - 1:
                return 1
            if (i, sign) in memo:
                return memo[(i, sign)]

            res = 1
            if ((sign and arr[i] > arr[i + 1]) or
                (not sign and arr[i] < arr[i + 1])
            ):
                res = 1 + dfs(i + 1, not sign)

            memo[(i, sign)] = res
            return res

        max_len = 1
        for i in range(n):
            max_len = max(max_len, dfs(i, True), dfs(i, False))

        return max_len

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Dynamic Programming (Bottom-Up)

Intuition

Instead of recursion, we build the solution iteratively. At each position, we track two values: the length of the turbulent subarray ending here with an increasing comparison, and the length ending with a decreasing comparison. When we see an increase, we extend the previous decreasing sequence (and vice versa), since turbulence requires alternation.

Algorithm

Create a 2D DP array where dp[i][0] stores the turbulent length ending at i with a decrease, and dp[i][1] stores the length ending with an increase.
Initialize all values to 1.
For each index i from 1 to n - 1:
- If arr[i] > arr[i-1] (increase), set dp[i][1] = dp[i-1][0] + 1.
- If arr[i] < arr[i-1] (decrease), set dp[i][0] = dp[i-1][1] + 1.
Track the maximum value across all dp entries.
Return the maximum.

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        n = len(arr)
        if n == 1:
            return 1

        dp = [[1] * 2 for _ in range(n)]

        max_len = 1
        for i in range(1, n):
            if arr[i] > arr[i - 1]:
                dp[i][1] = dp[i - 1][0] + 1
            elif arr[i] < arr[i - 1]:
                dp[i][0] = dp[i - 1][1] + 1

            max_len = max(max_len, dp[i][0], dp[i][1])

        return max_len

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Sliding Window

Intuition

We maintain a window that represents a valid turbulent subarray. As we move the right pointer, we check if the current comparison alternates from the previous one. If it does, we extend the window. If not (or if elements are equal), we shrink the window by moving the left pointer to start fresh from the breaking point.

Algorithm

Initialize two pointers l = 0 and r = 1, result res = 1, and a variable prev to track the previous comparison direction.
While r < n:
- If arr[r-1] > arr[r] and prev != ">", extend the window, update result, increment r, and set prev = ">".
- Else if arr[r-1] < arr[r] and prev != "<", extend the window, update result, increment r, and set prev = "<".
- Otherwise, reset: move l to r - 1 (or r if elements are equal), clear prev.
Return res.

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        l, r, res, prev = 0, 1, 1, ""

        while r < len(arr):
            if arr[r - 1] > arr[r] and prev != ">":
                res = max(res, r - l + 1)
                r += 1
                prev = ">"
            elif arr[r - 1] < arr[r] and prev != "<":
                res = max(res, r - l + 1)
                r += 1
                prev = "<"
            else:
                r = r + 1 if arr[r] == arr[r - 1] else r
                l = r - 1
                prev = ""

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

5. Iteration

Intuition

We can simplify the sliding window approach by just counting consecutive valid comparisons. We track the current count of alternating comparisons. When we see a comparison that properly alternates from the previous one, we increment the count. Otherwise, we reset to 1 (or 0 if elements are equal). The final answer is the maximum count plus one.

Algorithm

Initialize res = 0, cnt = 0, and sign = -1 (no previous comparison).
For each adjacent pair from index 0 to n - 2:
- If arr[i] > arr[i+1]: if the previous sign was 0 (increase), increment cnt; otherwise reset cnt = 1. Set sign = 1.
- If arr[i] < arr[i+1]: if the previous sign was 1 (decrease), increment cnt; otherwise reset cnt = 1. Set sign = 0.
- If equal: reset cnt = 0 and sign = -1.
- Update res = max(res, cnt).
Return res + 1 (to account for the element count, not comparison count).

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        n = len(arr)
        res = cnt = 0
        sign = -1

        for i in range(n - 1):
            if arr[i] > arr[i + 1]:
                cnt = cnt + 1 if sign == 0 else 1
                sign = 1
            elif arr[i] < arr[i + 1]:
                cnt = cnt + 1 if sign == 1 else 1
                sign = 0
            else:
                cnt = 0
                sign = -1

            res = max(res, cnt)

        return res + 1

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Forgetting to Handle Equal Adjacent Elements

When two adjacent elements are equal, the turbulent pattern breaks completely. A common mistake is treating equality as either an increase or decrease, or failing to reset the count. Equal elements should reset your tracking variables since no valid turbulent subarray can contain adjacent equal elements.

Miscounting Array Length vs Comparison Count

The turbulent subarray length is the number of elements, not the number of comparisons. If you track comparison counts, remember that n comparisons correspond to n + 1 elements. Many solutions return a result that is off by one because they confuse these two quantities.

Not Initializing Result to Handle Single-Element Arrays

A single-element array is a valid turbulent subarray of length 1. If your solution only updates the result when finding valid comparisons, it may return 0 for single-element inputs. Always initialize your result to at least 1 to handle this edge case correctly.