Longest Turbulent Subarray

The key idea

Turbulence is about adjacent comparison signs strictly alternating. Walk left to right tracking two running lengths: the longest turbulent run ending here whose last comparison was < (up) and the one whose last comparison was > (down). Each new pair extends the opposite-direction run by one and resets the same-direction one.

Problem

Given an integer array arr, return the length of the longest turbulent subarray of arr.

A subarray is turbulent if the comparison sign between every pair of adjacent elements strictly alternates. Formally, a subarray arr[i], arr[i+1], ..., arr[j] is turbulent when, for each index k in the range i <= k < j, either arr[k] > arr[k+1] when k is odd and arr[k] < arr[k+1] when k is even, or arr[k] < arr[k+1] when k is odd and arr[k] > arr[k+1] when k is even.

Equal adjacent elements break turbulence, since neither < nor > holds. A single element is turbulent on its own with length 1.

Constraints

1 <= arr.length <= 4 * 10^4
0 <= arr[i] <= 10^9

Examples

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

Input: arr = [4,8,12,16] Output: 2

Input: arr = [100] Output: 1

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →