⚡Flashcard Drill➔
NeetCode #779LC-978MediumGreedyNC 250
← Back to All Problems

#779 · #978 · Longest Turbulent Subarray(最长湍流子数组)

📌 Problem Statement & Constraints

A subarray is turbulent if the comparison sign between adjacent elements alternates (<, >, <, ... or >, <, >, ...). Return the length of the longest turbulent subarray of arr. Constraints: 1 <= arr.length <= 4 * 10^4, 0 <= arr[i] <= 10^9.

💡 Core Algorithmic Approaches

  1. Track two lengths: up, the longest turbulent subarray ending at the current index with a rising last step, and down, with a falling last step.
  2. If arr[i] > arr[i-1], then up = down + 1 and down resets to 1.
  3. Symmetrically, if arr[i] < arr[i-1], then down = up + 1 and up resets to 1.
  4. Equal adjacent values break the alternation, so both counters reset to 1.

💻 Benchmark Python3 Implementation

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        res = 1
        up = down = 1
        for i in range(1, len(arr)):
            if arr[i] > arr[i - 1]:
                up = down + 1
                down = 1
            elif arr[i] < arr[i - 1]:
                down = up + 1
                up = 1
            else:
                up = down = 1          # equal values break the run
            res = max(res, up, down)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass.
💾 Space Complexity
O(1): three scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the equality case: arr[i] == arr[i-1] must reset both counters, otherwise a run through equal values is wrongly extended.
  • Using a single counter: the two directions must be tracked separately because the next step depends on the previous direction.
  • Returning 0 for an empty array: the length is at least 1, and a single element is turbulent with length 1.
  • Comparing with two indices back: the alternation is defined on adjacent pairs only.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems