Builds on Kadane's Algorithm, which you haven’t finished yet.
Kadane's Algorithm with a Direction (Longest Turbulent Subarray)
up and down, and flip them on each step.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.
[4, 2, 10, 7, 8] goes down, up, down, up. The equal pair 8, 8 ends it, and [8, 1, 9] has length 3.Turbulent Subarray
up, down = longest run ending here with a last step up or down ➔ a step up extends down, a step down extends up ➔ keep the best| 1 | def max_turbulence_size(arr: list[int]) -> int: |
| 2 | """Longest Turbulent Subarray: the longest run whose steps alternate between up and down. |
| 3 | Time: O(N) | Space: O(1) |
| 4 | """ |
| 5 | # up, down: the length of the longest turbulent subarray ending at the current number whose last step went up, or went down; best: the longest seen |
| 6 | up = down = best = 1 |
| 7 | for i in range(1, len(arr)): |
| 8 | # 1. Flip The Direction Or Restart: |
| 9 | # A step up extends the run whose last step went down, a step down extends the run whose last step went up, and an equal step restarts both. |
| 10 | if arr[i] > arr[i - 1]: |
| 11 | up, down = down + 1, 1 |
| 12 | elif arr[i] < arr[i - 1]: |
| 13 | up, down = 1, up + 1 |
| 14 | else: |
| 15 | up = down = 1 |
| 16 | |
| 17 | # 2. Track The Best: |
| 18 | # Every turbulent subarray ends at some index, so the largest length seen at any index is the answer. |
| 19 | best = max(best, up, down) |
| 20 | |
| 21 | return best |
arr[i - 1] to arr[i], up and down are the lengths of the longest turbulent subarray ending at arr[i] whose last step went up or down, and best is the largest of both seen so far.A run is turbulent only if each step goes the other way from the step before it, so the state must remember the direction of the last step: up and down are the longest turbulent runs ending here whose last step went up or down. A step up gives up, down = down + 1, 1, a step down gives up, down = 1, up + 1, and an equal step is neither, so it gives up = down = 1. The trap is the direction: a step up extends down, not up, because extending up counts two steps up in a row.
See it run
Longest Turbulent Subarray, step by step
up 1down 1best 1
Each column is one index of arr. The rows up and down fill in as the steps run.
arr[i]the number being readarr[i - 1]the number before itupthe longest turbulent run that ends with a step updownthe longest turbulent run that ends with a step down
Start: up = down = best = 1. A single number is a run of length 1.
Gotcha 1 of 3
- The trap
Gotcha 1: Extending the same direction
Mistakeup, down = up + 1, 1Fixup, down = down + 1, 1What happens: A step up must follow a step down, so it extends the run whose last step went down. Extending
upadds a second step up in a row to the run, and a run with two steps up in a row is not turbulent.Example: Longest Turbulent Subarray (LC 978): arr = [4, 8, 12, 16]Mistake: returns 4Fix: returns 2
- A run grows with any next number, so one length is enough and the direction of the last step does not matter, as in Maximum Subarray (LC 53). See Kadane's Algorithm
Deep Dive
Why one length is not enough
A subarray is turbulent when its steps alternate: up, then down, then up, and so on, or the reverse. A step is up when arr[i] > arr[i - 1] and down when arr[i] < arr[i - 1].
In Kadane's Algorithm, a run can grow with any next number. Here a run can grow only if the next step goes the opposite way from the last step of the run. So the run's length alone is not a complete state. The state must also say which way the last step went.
The card keeps two lengths for the subarrays that end at arr[i]. up is the longest turbulent subarray whose last step went up. down is the longest one whose last step went down. The lengths count numbers, so a single number has length 1.
Why the update flips the lengths
Suppose the step from arr[i - 1] to arr[i] goes up. A turbulent subarray can end with this step only if the step before it went down. So the new up is the old down plus 1. The old down is the longest subarray ending at arr[i - 1] with a last step down.
A subarray cannot end at arr[i] with a last step down, because the step into arr[i] went up. So the new down is 1, which is arr[i] alone.
A step down is the mirror image: up, down = 1, up + 1. An equal step is neither up nor down, so no run can cross it. Both lengths restart at 1.
The tuple assignment reads the old up and down on the right side, so the flip is safe.
Trace and the cost
Trace for arr = [9, 4, 2, 10, 7, 8, 8, 1, 9], as arr[i], up, down, best:
4, 1, 2, 2.2, 1, 2, 2.10, 3, 1, 3.7, 1, 4, 4.8, 5, 1, 5.8, 1, 1, 5.1, 1, 2, 5.9, 3, 1, 5.
The answer is 5, from the run [4, 2, 10, 7, 8]. The steps are down, up, down, up.
There are N - 1 steps, and each does constant work. The time is O(N) and the space is O(1).
Edge cases: an array with one number returns 1. An array of equal numbers returns 1. A strictly increasing array such as [4, 8, 12, 16] returns 2, because only one step in a row can be part of a turbulent run.
A related problem with a different state
Longest Mountain in Array (LC 845) also depends on the direction of steps. But a mountain does not alternate. It rises, and then it falls, once. The state is the phase (rising or falling), and a rise after a fall ends the mountain.
So the common idea is only this: when the next step depends on the last step, the state must store the last step's direction.
60-Second Pitch
"A run is turbulent when each step goes the opposite way from the step before it. So the state must remember the direction of the last step. I keep up and down, the longest turbulent runs that end here with a last step up or down. A step up gives up, down = down + 1, 1. A step down gives up, down = 1, up + 1. An equal step sets both to 1. I keep the largest value of either in best. The time is O(N) and the space is O(1)."
Common Questions
- Why does a step up extend
downand notup? A turbulent run alternates. A run that ends with a step up can only be extended by a step down. In the same way, a new step up must come after a run whose last step went down, so it extends
down. Extendingupwould put two steps up in a row.- What happens with equal neighbours?
An equal step is neither up nor down, so no turbulent run can contain it. Both
upanddownrestart at 1. For[9, 9], the answer is 1.- What is the time and space complexity?
O(N)time, because there are N - 1 steps and each does constant work.O(1)space, because onlyup,downandbestexist.- What is the answer for a strictly increasing array?
2, when the array has at least two numbers. Every step goes up, so a run can hold only one step. For
[4, 8, 12, 16], the answer is 2. For one number, the answer is 1.- How does Longest Mountain in Array (LC 845) differ?
A mountain rises and then falls once. It does not alternate. The state is the phase, rising or falling, and a new rise after a fall ends the mountain. The idea of storing the last step's direction is shared, but the update rules are different.
SWE Reasoning
Spot it
- The question asks for the longest unbroken run that follows a rule about the direction of each step.
- The rule compares each step with the step before it, not each number with a fixed value.
- Equal neighbours break the run.
- A brute force checks every start and end in O(N^2) or more.
- One length per position is not enough, because the next step depends on how the last step went.
The invariant, step by step
- Before the loop,
up,downandbestare all 1. One number is a turbulent subarray of length 1. - For each
i, comparearr[i]witharr[i - 1]. - If the step goes up,
upbecomes the olddownplus 1, anddownbecomes 1. - If the step goes down,
downbecomes the oldupplus 1, andupbecomes 1. - If the numbers are equal, both become 1.
best = max(best, up, down)keeps the longest length seen. After the loop,bestis the answer.
Traps
- Same direction.
up + 1after a step up counts two steps up in a row. For[4, 8, 12, 16], the result is 4 instead of 2. - Equal step treated as a direction. Equal neighbours are neither up nor down. For
[9, 9], the result is 2 instead of 1. - Using only one length for
best. The longest run can end with either direction. For[3, 2], usinguponly gives 1 instead of 2. - Starting at 0. A single number is a run of length 1. For
[100], the answer is 1. - Two separate assignments. Writing
up = down + 1and thendown = up + 1uses the newup. Use one tuple assignment.
Practice
Builds on Kadane's Algorithm, which you haven’t finished yet.
Kadane's Algorithm with a Direction (Longest Turbulent Subarray)
up and down, and flip them on each step.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.
[4, 2, 10, 7, 8] goes down, up, down, up. The equal pair 8, 8 ends it, and [8, 1, 9] has length 3.Turbulent Subarray
up, down = longest run ending here with a last step up or down ➔ a step up extends down, a step down extends up ➔ keep the best| 1 | def max_turbulence_size(arr: list[int]) -> int: |
| 2 | """Longest Turbulent Subarray: the longest run whose steps alternate between up and down. |
| 3 | Time: O(N) | Space: O(1) |
| 4 | """ |
| 5 | # up, down: the length of the longest turbulent subarray ending at the current number whose last step went up, or went down; best: the longest seen |
| 6 | up = down = best = 1 |
| 7 | for i in range(1, len(arr)): |
| 8 | # 1. Flip The Direction Or Restart: |
| 9 | # A step up extends the run whose last step went down, a step down extends the run whose last step went up, and an equal step restarts both. |
| 10 | if arr[i] > arr[i - 1]: |
| 11 | up, down = down + 1, 1 |
| 12 | elif arr[i] < arr[i - 1]: |
| 13 | up, down = 1, up + 1 |
| 14 | else: |
| 15 | up = down = 1 |
| 16 | |
| 17 | # 2. Track The Best: |
| 18 | # Every turbulent subarray ends at some index, so the largest length seen at any index is the answer. |
| 19 | best = max(best, up, down) |
| 20 | |
| 21 | return best |
arr[i - 1] to arr[i], up and down are the lengths of the longest turbulent subarray ending at arr[i] whose last step went up or down, and best is the largest of both seen so far.A run is turbulent only if each step goes the other way from the step before it, so the state must remember the direction of the last step: up and down are the longest turbulent runs ending here whose last step went up or down. A step up gives up, down = down + 1, 1, a step down gives up, down = 1, up + 1, and an equal step is neither, so it gives up = down = 1. The trap is the direction: a step up extends down, not up, because extending up counts two steps up in a row.
See it run
Longest Turbulent Subarray, step by step
up 1down 1best 1
Each column is one index of arr. The rows up and down fill in as the steps run.
arr[i]the number being readarr[i - 1]the number before itupthe longest turbulent run that ends with a step updownthe longest turbulent run that ends with a step down
Start: up = down = best = 1. A single number is a run of length 1.
Gotcha 1 of 3
- The trap
Gotcha 1: Extending the same direction
Mistakeup, down = up + 1, 1Fixup, down = down + 1, 1What happens: A step up must follow a step down, so it extends the run whose last step went down. Extending
upadds a second step up in a row to the run, and a run with two steps up in a row is not turbulent.Example: Longest Turbulent Subarray (LC 978): arr = [4, 8, 12, 16]Mistake: returns 4Fix: returns 2
- A run grows with any next number, so one length is enough and the direction of the last step does not matter, as in Maximum Subarray (LC 53). See Kadane's Algorithm
Deep Dive
Why one length is not enough
A subarray is turbulent when its steps alternate: up, then down, then up, and so on, or the reverse. A step is up when arr[i] > arr[i - 1] and down when arr[i] < arr[i - 1].
In Kadane's Algorithm, a run can grow with any next number. Here a run can grow only if the next step goes the opposite way from the last step of the run. So the run's length alone is not a complete state. The state must also say which way the last step went.
The card keeps two lengths for the subarrays that end at arr[i]. up is the longest turbulent subarray whose last step went up. down is the longest one whose last step went down. The lengths count numbers, so a single number has length 1.
Why the update flips the lengths
Suppose the step from arr[i - 1] to arr[i] goes up. A turbulent subarray can end with this step only if the step before it went down. So the new up is the old down plus 1. The old down is the longest subarray ending at arr[i - 1] with a last step down.
A subarray cannot end at arr[i] with a last step down, because the step into arr[i] went up. So the new down is 1, which is arr[i] alone.
A step down is the mirror image: up, down = 1, up + 1. An equal step is neither up nor down, so no run can cross it. Both lengths restart at 1.
The tuple assignment reads the old up and down on the right side, so the flip is safe.
Trace and the cost
Trace for arr = [9, 4, 2, 10, 7, 8, 8, 1, 9], as arr[i], up, down, best:
4, 1, 2, 2.2, 1, 2, 2.10, 3, 1, 3.7, 1, 4, 4.8, 5, 1, 5.8, 1, 1, 5.1, 1, 2, 5.9, 3, 1, 5.
The answer is 5, from the run [4, 2, 10, 7, 8]. The steps are down, up, down, up.
There are N - 1 steps, and each does constant work. The time is O(N) and the space is O(1).
Edge cases: an array with one number returns 1. An array of equal numbers returns 1. A strictly increasing array such as [4, 8, 12, 16] returns 2, because only one step in a row can be part of a turbulent run.
A related problem with a different state
Longest Mountain in Array (LC 845) also depends on the direction of steps. But a mountain does not alternate. It rises, and then it falls, once. The state is the phase (rising or falling), and a rise after a fall ends the mountain.
So the common idea is only this: when the next step depends on the last step, the state must store the last step's direction.
60-Second Pitch
"A run is turbulent when each step goes the opposite way from the step before it. So the state must remember the direction of the last step. I keep up and down, the longest turbulent runs that end here with a last step up or down. A step up gives up, down = down + 1, 1. A step down gives up, down = 1, up + 1. An equal step sets both to 1. I keep the largest value of either in best. The time is O(N) and the space is O(1)."
Common Questions
- Why does a step up extend
downand notup? A turbulent run alternates. A run that ends with a step up can only be extended by a step down. In the same way, a new step up must come after a run whose last step went down, so it extends
down. Extendingupwould put two steps up in a row.- What happens with equal neighbours?
An equal step is neither up nor down, so no turbulent run can contain it. Both
upanddownrestart at 1. For[9, 9], the answer is 1.- What is the time and space complexity?
O(N)time, because there are N - 1 steps and each does constant work.O(1)space, because onlyup,downandbestexist.- What is the answer for a strictly increasing array?
2, when the array has at least two numbers. Every step goes up, so a run can hold only one step. For
[4, 8, 12, 16], the answer is 2. For one number, the answer is 1.- How does Longest Mountain in Array (LC 845) differ?
A mountain rises and then falls once. It does not alternate. The state is the phase, rising or falling, and a new rise after a fall ends the mountain. The idea of storing the last step's direction is shared, but the update rules are different.
SWE Reasoning
Spot it
- The question asks for the longest unbroken run that follows a rule about the direction of each step.
- The rule compares each step with the step before it, not each number with a fixed value.
- Equal neighbours break the run.
- A brute force checks every start and end in O(N^2) or more.
- One length per position is not enough, because the next step depends on how the last step went.
The invariant, step by step
- Before the loop,
up,downandbestare all 1. One number is a turbulent subarray of length 1. - For each
i, comparearr[i]witharr[i - 1]. - If the step goes up,
upbecomes the olddownplus 1, anddownbecomes 1. - If the step goes down,
downbecomes the oldupplus 1, andupbecomes 1. - If the numbers are equal, both become 1.
best = max(best, up, down)keeps the longest length seen. After the loop,bestis the answer.
Traps
- Same direction.
up + 1after a step up counts two steps up in a row. For[4, 8, 12, 16], the result is 4 instead of 2. - Equal step treated as a direction. Equal neighbours are neither up nor down. For
[9, 9], the result is 2 instead of 1. - Using only one length for
best. The longest run can end with either direction. For[3, 2], usinguponly gives 1 instead of 2. - Starting at 0. A single number is a run of length 1. For
[100], the answer is 1. - Two separate assignments. Writing
up = down + 1and thendown = up + 1uses the newup. Use one tuple assignment.