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
- Track two lengths:
up, the longest turbulent subarray ending at the current index with a rising last step, anddown, with a falling last step. - If
arr[i] > arr[i-1], thenup = down + 1anddownresets to 1. - Symmetrically, if
arr[i] < arr[i-1], thendown = up + 1andupresets to 1. - 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.