Skip to main content

Longest Turbulent Subarray

LeetCode 1020 | Difficulty: Medium​

Medium

Problem Description​

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  arr[k + 1]` when `k` is odd, and

    - `arr[k]  arr[k + 1]` when `k` is even, and

    - `arr[k]  arr[2]  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 * 10^4`

    - `0 <= arr[i] <= 10^9`

**Topics:** `Array`, `Dynamic Programming`, `Sliding Window`

---

## Approach

### Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

:::tip When to use
Finding subarrays/substrings with a property (max length, min length, exact count).
:::

### Dynamic Programming

Break the problem into overlapping subproblems. Define a **state** (what information do you need?), a **recurrence** (how does state[i] depend on smaller states?), and a **base case**. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

:::tip When to use
Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).
:::

---

## Solutions

### Solution 1: C# (Best: 180 ms)

| Metric | Value |
|--------|-------|
| **Runtime** | 180 ms |
| **Memory** | 44.5 MB |
| **Date** | 2020-10-12 |

```csharp title="Solution"
public class Solution {
    public int MaxTurbulenceSize(int[] A) {
        int n = A.Length;
    int[,] state = new int[n,2];
    int maxLen = 0;
    
    for (int i = 1; i < n; i++)
    {
        if(A[i]<A[i-1])
        {
            state[i,0] = state[i-1,1]+1;
            maxLen = Math.Max(maxLen, state[i,0]);
        }
        else if(A[i]>A[i-1])
        {
            state[i,1] = state[i-1,0]+1;
            maxLen = Math.Max(maxLen, state[i,1]);
        }
    }
    
    return maxLen+1;
    }
}

Complexity Analysis​

ApproachTimeSpace
Sliding Window$O(n)$$O(k)$
DP (2D)$O(n × m)$$O(n × m)$

Interview Tips​

Key Points
  • Discuss the brute force approach first, then optimize. Explain your thought process.
  • Clarify what makes a window "valid" and what triggers expansion vs shrinking.
  • Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
  • Consider if you can reduce space by only keeping the last row/few values.