Longest Turbulent Subarray

MEDIUM✓ CHIP-TIMEDLC #978 — FULL STATEMENT ↗

The drill: Find the longest run of consecutive elements where the comparisons zig-zag — each step must flip between climbing and dropping compared to the step before. A flat or repeated direction ends the run.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of integers arrives, and the goal is measuring the longest contiguous stretch where consecutive comparisons strictly alternate between climbing and dropping — up, then down, then up again, with no two same-direction steps back to back.

A stretch of just one element always counts as turbulent on its own, since there's no comparison yet to break. The moment two consecutive elements are equal, or the direction repeats instead of flipping, that particular run ends there.

Only the length of the longest such alternating stretch is needed, not its starting position or the actual values inside it.

EX 01

arr = [4, 8, 2, 9, 1, 7, 7, 3]

→ 6

RUN BREAKS AT THE REPEATED 7

EX 02

arr = [5, 5, 5, 5]

→ 1

CONSTANT ARRAY, NO DIRECTION EVER CHANGES

EX 03

arr = [1, 2, 3, 4, 5]

→ 2

STRICTLY INCREASING — ONLY ADJACENT PAIRS QUALIFY

the array always holds at least one element
values can repeat, including exact ties between neighbors
a single element alone always counts as a turbulent run of length one
only the longest run's length is reported, not its position

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Checking every subarray for the alternating pattern directly re-examines the whole run each time. What could you carry forward from position i to i+1 instead of re-scanning from the start?

HINT 2 THE STRUCTURE

At each position ask only one thing: does this step continue an alternation that the OTHER direction left off, or does it break it? Two small numbers — the best run ending here going up, and the best run ending here going down — are enough to answer that.

HINT 3 ONE STEP FROM THE ANSWER

up[i] = down[i-1] + 1 when arr[i] > arr[i-1] (otherwise reset to 1); down[i] mirrors it for arr[i] < arr[i-1]. An equal pair resets both to 1. The answer is the largest value either counter ever reaches.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE ZIGZAG COUNTERSPATTERN · ALTERNATING RUN DParr = [4, 8, 2, 9, 1, 7, 7, 3]

UP · DOWN · BEST

up → 1

down → 1

best → 1

STEP 1

Array [4, 8, 2, 9, 1, 7, 7, 3]. up and down both start at 1 — index 0 alone is a turbulent run of length one.

STEP 1 / 9 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/longest-turbulent-subarray.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        up = down = best = 1
        for i in range(1, len(arr)):
            if arr[i] > arr[i - 1]:
                up, down = down + 1, 1
            elif arr[i] < arr[i - 1]:
                down, up = up + 1, 1
            else:
                up = down = 1
            best = max(best, up, down)
        return best

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 12 LN

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        n = len(arr)
        best = 1
        for i in range(n):
            for j in range(i, n):
                if self.isTurbulent(arr[i:j + 1]):
                    best = max(best, j - i + 1)
        return best

    def isTurbulent(self, sub: List[int]) -> bool:
        if len(sub) == 1:
            return True
        signs = []
        for k in range(len(sub) - 1):
            if sub[k] == sub[k + 1]:
                return False
            signs.append(1 if sub[k + 1] > sub[k] else -1)
        for k in range(1, len(signs)):
            if signs[k] == signs[k - 1]:
                return False
        return True

TIME O(N³)SPACE O(1)PYTHON · TRAINING PACE · 22 LN

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int up = 1, down = 1, best = 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 = 1;
                down = 1;
            }
            best = Math.max(best, Math.max(up, down));
        }
        return best;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 19 LN

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        int best = 1;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isTurbulent(arr, i, j)) {
                    best = Math.max(best, j - i + 1);
                }
            }
        }
        return best;
    }

    private boolean isTurbulent(int[] arr, int i, int j) {
        if (i == j) {
            return true;
        }
        Integer prevSign = null;
        for (int k = i; k < j; k++) {
            if (arr[k] == arr[k + 1]) {
                return false;
            }
            int sign = arr[k + 1] > arr[k] ? 1 : -1;
            if (prevSign != null && sign == prevSign) {
                return false;
            }
            prevSign = sign;
        }
        return true;
    }
}

TIME O(N³)SPACE O(1)JAVA · TRAINING PACE · 32 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED