Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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:
i <= k < j:
arr[k] > arr[k + 1] when k is odd, andarr[k] < arr[k + 1] when k is even.i <= k < j:
arr[k] > arr[k + 1] when k is even, andarr[k] < arr[k + 1] when k is odd.Example 1:
Input: arr = [9,4,2,10,7,8,8,1,9] Output: 5 Explanation: arr[1] > arr[2] < arr[3] > 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 * 1040 <= arr[i] <= 109Problem summary: 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 <= k < j: arr[k] > arr[k + 1] when k is odd, and arr[k] < arr[k + 1] when k is even. Or, for i <= k < j: arr[k] > arr[k + 1] when k is even, and arr[k] < arr[k + 1] when k is odd.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Dynamic Programming · Sliding Window
[9,4,2,10,7,8,8,1,9]
[4,8,12,16]
[100]
maximum-subarray)longest-alternating-subarray)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #978: Longest Turbulent Subarray
class Solution {
public int maxTurbulenceSize(int[] arr) {
int ans = 1, f = 1, g = 1;
for (int i = 1; i < arr.length; ++i) {
int ff = arr[i - 1] < arr[i] ? g + 1 : 1;
int gg = arr[i - 1] > arr[i] ? f + 1 : 1;
f = ff;
g = gg;
ans = Math.max(ans, Math.max(f, g));
}
return ans;
}
}
// Accepted solution for LeetCode #978: Longest Turbulent Subarray
func maxTurbulenceSize(arr []int) int {
ans, f, g := 1, 1, 1
for i, x := range arr[1:] {
ff, gg := 1, 1
if arr[i] < x {
ff = g + 1
}
if arr[i] > x {
gg = f + 1
}
f, g = ff, gg
ans = max(ans, max(f, g))
}
return ans
}
# Accepted solution for LeetCode #978: Longest Turbulent Subarray
class Solution:
def maxTurbulenceSize(self, arr: List[int]) -> int:
ans = f = g = 1
for a, b in pairwise(arr):
ff = g + 1 if a < b else 1
gg = f + 1 if a > b else 1
f, g = ff, gg
ans = max(ans, f, g)
return ans
// Accepted solution for LeetCode #978: Longest Turbulent Subarray
impl Solution {
pub fn max_turbulence_size(arr: Vec<i32>) -> i32 {
let mut ans = 1;
let mut f = 1;
let mut g = 1;
for i in 1..arr.len() {
let ff = if arr[i - 1] < arr[i] { g + 1 } else { 1 };
let gg = if arr[i - 1] > arr[i] { f + 1 } else { 1 };
f = ff;
g = gg;
ans = ans.max(f.max(g));
}
ans
}
}
// Accepted solution for LeetCode #978: Longest Turbulent Subarray
function maxTurbulenceSize(arr: number[]): number {
let f = 1;
let g = 1;
let ans = 1;
for (let i = 1; i < arr.length; ++i) {
const ff = arr[i - 1] < arr[i] ? g + 1 : 1;
const gg = arr[i - 1] > arr[i] ? f + 1 : 1;
f = ff;
g = gg;
ans = Math.max(ans, f, g);
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.
Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.
Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.
Fix: Shrink in a `while` loop until the invariant is valid again.