Longest Turbulent Subarray

medium dynamic programming sliding window array

Problem

A subarray is turbulent if the comparison sign flips between every pair of adjacent elements (greater, then less, then greater, …). Given an integer array arr, return the length of the longest turbulent subarray.

Inputarr = [9, 4, 2, 10, 7, 8, 8, 1, 9]

Output5

arr[1..5] = [4, 2, 10, 7, 8] alternates: 4>2<10>7<8, giving length 5.

arr (comma-separated)

def max_turbulence_size(arr):
    n = len(arr)
    best = 1
    up = down = 1
    for i in range(1, n):
        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

function maxTurbulenceSize(arr) {
  const n = arr.length;
  let best = 1, up = 1, down = 1;
  for (let i = 1; i < n; 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, up, down);
  }
  return best;
}

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

int maxTurbulenceSize(vector<int>& arr) {
    int n = (int)arr.size();
    int best = 1, up = 1, down = 1;
    for (int i = 1; i < n; 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 = max(best, max(up, down));
    }
    return best;
}

Explanation

A turbulent run is one where the comparison sign keeps flipping: up, down, up, down. We can find the longest one in a single pass by tracking, at each step, two running streak lengths instead of re-scanning.

We keep up = the length of the turbulent run ending here whose last move was a rise, and down = the run ending here whose last move was a fall. These two take turns extending each other.

At each new element we compare it to the previous one. If it rose (arr[i] > arr[i-1]), this rise must follow a fall, so up = down + 1 and down resets to 1. If it fell, then down = up + 1 and up resets. If they are equal, the streak breaks and both reset to 1.

After each step we update best with the larger of up and down. This works because a valid turbulent run alternates, so each new sign can only build on the streak that ended with the opposite sign.

Example: in [9,4,2,10,7,8,8,1,9], the slice [4,2,10,7,8] alternates 4>2<10>7<8, letting up/down climb to length 5, the answer.

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