Longest Turbulent Subarray

Problem

A subarray is turbulent if the comparison sign between each pair of adjacent elements alternates. Find the length of the longest turbulent subarray.

Input:  arr = [9,4,2,10,7,8,8,1,9]
Output: 5   ([4,2,10,7,8])

Python Solution

def max_turbulence_size(arr):
    best = 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
        best = max(best, up, down)
    return best

C++ Solution

int maxTurbulenceSize(vector<int>& arr) {
    int best = 1, up = 1, down = 1;
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] > arr[i - 1]) {
            up = down + 1;
            down = 1;
        } else if (arr[i] < arr[i - 1]) {
            down = up + 1;
            up = 1;
        } else {
            up = down = 1;
        }
        best = max({best, up, down});
    }
    return best;
}

Java Solution

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int best = 1, up = 1, down = 1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[i - 1]) {
                up = down + 1;
                down = 1;
            } else if (arr[i] < arr[i - 1]) {
                down = up + 1;
                up = 1;
            } else {
                up = down = 1;
            }
            best = Math.max(best, Math.max(up, down));
        }
        return best;
    }
}

Complexity

Time: O(n) — one pass, updating two running streak counters per comparison. Space: O(1) — only the up and down streak counters are kept.