Longest Turbulent Subarray (LeetCode 978)
You get an integer array arr. A subarray is a run of numbers that sit next to each other. A subarray is turbulent when its steps alternate: every step goes up or down, and each step goes the other way from the step before it.
Return the length of the longest turbulent subarray. A single number is a turbulent subarray of length 1.
Worked Examples
arr = [9,4,2,10,7,8,8,1,9]5[4, 2, 10, 7, 8] goes down, up, down, up. The equal pair 8, 8 ends it, and [8, 1, 9] has length 3.arr = [4,8,12,16]2arr = [100]1⚖️Formal Constraints & Bounds
1 <= arr.length <= 4 * 1040 <= arr[i] <= 109
Core Insight
A run is turbulent only if each step goes the other way from the step before, so keep two lengths per position, one for runs whose last step went up and one for runs whose last step went down: a step up extends the run that ended with a step down, and an equal step restarts both.
Real-World Scenario & Production Applications
A price that keeps swinging, such as a sensor reading that rises, falls, rises again: the longest stretch of strict swings is the longest turbulent subarray, and one flat reading or one second rise in a row breaks it.
Step-by-Step Execution Trace Table
Trace of Example 1: arr = [9, 4, 2, 10, 7, 8, 8, 1, 9]. up = down = best = 1.
i | Step | up | down | best |
|---|---|---|---|---|
| 1 | 9 to 4, down | 1 | 2 | 2 |
| 2 | 4 to 2, down | 1 | 2 | 2 |
| 3 | 2 to 10, up | 3 | 1 | 3 |
| 4 | 10 to 7, down | 1 | 4 | 4 |
| 5 | 7 to 8, up | 5 | 1 | 5 |
| 6 | 8 to 8, equal | 1 | 1 | 5 |
| 7 | 8 to 1, down | 1 | 2 | 5 |
| 8 | 1 to 9, up | 3 | 1 | 5 |
At i = 2 the second step down cannot extend the run, so down restarts from up + 1 = 2. At i = 6 the equal step restarts both lengths.
| 1 | up = down = best = 1 |
| 2 | for i in range(1, len(arr)): |
| 3 | step up: up, down = down + 1, 1; step down: up, down = 1, up + 1; equal: up = down = 1 |
| 4 | best = max(best, up, down) |
| 5 | return best |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A subarray is turbulent when its steps alternate: up, down, up, down, or the other way around. Kadane's Algorithm keeps the best run ending here. For this problem the run needs one more piece of information: the direction of its last step, because the next step must go the other way. So this variant keeps two lengths per position, up and down.
➗ What Is Added To Kadane
Kadane's Algorithm chooses between extending the run and starting fresh. This variant extends the run only when the new step flips the direction, and starts fresh at length 2 or 1 otherwise. The state is split by the direction of the last step.
🔑 The Key Idea in the Code
A step up extends down, not up: up, down = down + 1, 1. Extending the wrong length would count two steps in the same direction as turbulent.
Extending the same direction:
up, down = up + 1, 1for a step up counts two steps up in a row as turbulent. A step up extends the run whose last step went down.Treating an equal step as a step down:
arr[i] == arr[i - 1]is neither up nor down, so both runs restart at 1.Tracking only one of the two lengths: the longest run may end with a step up or with a step down, so
besttakes the larger of both.Forgetting that a single number counts: the smallest answer is 1, so
up,downandbeststart at 1, not 0.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The longest subarray whose steps alternate": a best value over contiguous runs, like Kadane's Algorithm, but a run can only grow when the new step goes the opposite way from its last step. That means the state must remember the direction of the last step.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
up is the length of the longest turbulent subarray ending at arr[i] whose last step went up, and down is the same for a last step down. A step up gives up = down + 1, down = 1. A step down gives down = up + 1, up = 1. An equal step gives both 1.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Kadane's Algorithm and the direction of the last step as extra state. A turbulent run can only grow when the next step goes the other way, so I keep up and down, the longest turbulent run ending at the current number whose last step went up or down. A step up gives up equals down plus one and resets down to one. A step down is the mirror. An equal step is neither, so both go back to one. I keep the largest of up and down in best. That is one pass, order N time and order 1 space.
Complexity & Mathematical Proof
O(N)
Look at the loop. for i in range(1, len(arr)) visits each neighbouring pair once. Each visit does one comparison, one assignment of up and down, and one max, which is constant work. That is N - 1 steps, so time is O(N).
O(1)
The code keeps three variables, up, down and best, whatever the length of arr is. There is no table and no recursion, so space is O(1).
Derivation Progression
for i in range(1, len(arr)) visits each neighbouring pair once.
1 = O(1)
One comparison, one assignment of up and down, and one max.
N - 1 = O(N)
Pairs times a constant amount of work.
Variable Definitions
Length of arr
Longest turbulent subarray ending here whose last step went up
Longest turbulent subarray ending here whose last step went down
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(1): the variables up, down and best
O(1): one integer
Boundary Best / Worst Cases
: the loop always visits every pair.
.
: the same count.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "each step goes the other way from the step before". A best length over contiguous runs is Kadane's Algorithm, and the alternating rule means the state must remember the direction of the last step.
and values up to . A loop over all start positions with an inner scan is steps in the worst case. One pass is . Only comparisons are used, so large values need no special handling.
Equal neighbours are neither up nor down, so they must reset both lengths. Comparing arr[i] with arr[i - 2] instead of using the direction of the last step makes the code harder to check and misses the case of an equal pair.
Longest Turbulent Subarray (LeetCode 978)
You get an integer array arr. A subarray is a run of numbers that sit next to each other. A subarray is turbulent when its steps alternate: every step goes up or down, and each step goes the other way from the step before it.
Return the length of the longest turbulent subarray. A single number is a turbulent subarray of length 1.
Worked Examples
arr = [9,4,2,10,7,8,8,1,9]5[4, 2, 10, 7, 8] goes down, up, down, up. The equal pair 8, 8 ends it, and [8, 1, 9] has length 3.arr = [4,8,12,16]2arr = [100]1⚖️Formal Constraints & Bounds
1 <= arr.length <= 4 * 1040 <= arr[i] <= 109
Core Insight
A run is turbulent only if each step goes the other way from the step before, so keep two lengths per position, one for runs whose last step went up and one for runs whose last step went down: a step up extends the run that ended with a step down, and an equal step restarts both.
Real-World Scenario & Production Applications
A price that keeps swinging, such as a sensor reading that rises, falls, rises again: the longest stretch of strict swings is the longest turbulent subarray, and one flat reading or one second rise in a row breaks it.
Step-by-Step Execution Trace Table
Trace of Example 1: arr = [9, 4, 2, 10, 7, 8, 8, 1, 9]. up = down = best = 1.
i | Step | up | down | best |
|---|---|---|---|---|
| 1 | 9 to 4, down | 1 | 2 | 2 |
| 2 | 4 to 2, down | 1 | 2 | 2 |
| 3 | 2 to 10, up | 3 | 1 | 3 |
| 4 | 10 to 7, down | 1 | 4 | 4 |
| 5 | 7 to 8, up | 5 | 1 | 5 |
| 6 | 8 to 8, equal | 1 | 1 | 5 |
| 7 | 8 to 1, down | 1 | 2 | 5 |
| 8 | 1 to 9, up | 3 | 1 | 5 |
At i = 2 the second step down cannot extend the run, so down restarts from up + 1 = 2. At i = 6 the equal step restarts both lengths.
| 1 | up = down = best = 1 |
| 2 | for i in range(1, len(arr)): |
| 3 | step up: up, down = down + 1, 1; step down: up, down = 1, up + 1; equal: up = down = 1 |
| 4 | best = max(best, up, down) |
| 5 | return best |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A subarray is turbulent when its steps alternate: up, down, up, down, or the other way around. Kadane's Algorithm keeps the best run ending here. For this problem the run needs one more piece of information: the direction of its last step, because the next step must go the other way. So this variant keeps two lengths per position, up and down.
➗ What Is Added To Kadane
Kadane's Algorithm chooses between extending the run and starting fresh. This variant extends the run only when the new step flips the direction, and starts fresh at length 2 or 1 otherwise. The state is split by the direction of the last step.
🔑 The Key Idea in the Code
A step up extends down, not up: up, down = down + 1, 1. Extending the wrong length would count two steps in the same direction as turbulent.
Extending the same direction:
up, down = up + 1, 1for a step up counts two steps up in a row as turbulent. A step up extends the run whose last step went down.Treating an equal step as a step down:
arr[i] == arr[i - 1]is neither up nor down, so both runs restart at 1.Tracking only one of the two lengths: the longest run may end with a step up or with a step down, so
besttakes the larger of both.Forgetting that a single number counts: the smallest answer is 1, so
up,downandbeststart at 1, not 0.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The longest subarray whose steps alternate": a best value over contiguous runs, like Kadane's Algorithm, but a run can only grow when the new step goes the opposite way from its last step. That means the state must remember the direction of the last step.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
up is the length of the longest turbulent subarray ending at arr[i] whose last step went up, and down is the same for a last step down. A step up gives up = down + 1, down = 1. A step down gives down = up + 1, up = 1. An equal step gives both 1.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Kadane's Algorithm and the direction of the last step as extra state. A turbulent run can only grow when the next step goes the other way, so I keep up and down, the longest turbulent run ending at the current number whose last step went up or down. A step up gives up equals down plus one and resets down to one. A step down is the mirror. An equal step is neither, so both go back to one. I keep the largest of up and down in best. That is one pass, order N time and order 1 space.
Complexity & Mathematical Proof
O(N)
Look at the loop. for i in range(1, len(arr)) visits each neighbouring pair once. Each visit does one comparison, one assignment of up and down, and one max, which is constant work. That is N - 1 steps, so time is O(N).
O(1)
The code keeps three variables, up, down and best, whatever the length of arr is. There is no table and no recursion, so space is O(1).
Derivation Progression
for i in range(1, len(arr)) visits each neighbouring pair once.
1 = O(1)
One comparison, one assignment of up and down, and one max.
N - 1 = O(N)
Pairs times a constant amount of work.
Variable Definitions
Length of arr
Longest turbulent subarray ending here whose last step went up
Longest turbulent subarray ending here whose last step went down
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(1): the variables up, down and best
O(1): one integer
Boundary Best / Worst Cases
: the loop always visits every pair.
.
: the same count.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "each step goes the other way from the step before". A best length over contiguous runs is Kadane's Algorithm, and the alternating rule means the state must remember the direction of the last step.
and values up to . A loop over all start positions with an inner scan is steps in the worst case. One pass is . Only comparisons are used, so large values need no special handling.
Equal neighbours are neither up nor down, so they must reset both lengths. Comparing arr[i] with arr[i - 2] instead of using the direction of the last step makes the code harder to check and misses the case of an equal pair.