Tech Blogs LLD SDE Playbook DSA

Longest Turbulent Subarray

Medium Top 250
Associated Patterns
Greedy Two Pointers
Interviewed At (Company Tags)
GoogleAmazon
External Reference View on LeetCode

Problem Description

Given an integer array arr, return the length of a maximum size turbulent subarray of arr.

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:
    • arr[k] > arr[k+1] when k is even, and arr[k] < arr[k+1] when k is odd.

Formally, the comparison sign between adjacent elements must alternate on each step.

Examples

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] is turbulent.

Example 2:

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

Example 3:

Input: arr = [100] Output: 1

Constraints

  • 1 ≤ arr.length ≤ 4 * 10⁴
  • 0 ≤ arr[i] ≤ 10⁹

Check Sign Alternation with a Sliding Window

Compare adjacent elements arr[i - 1] and arr[i]. We define the “sign” of the comparison as:

  • 1 if arr[i - 1] < arr[i]
  • -1 if arr[i - 1] > arr[i]
  • 0 if arr[i - 1] == arr[i]

We iterate through the array starting from index 1, maintaining the length of the current turbulent subarray currentLength:

  1. If the sign alternates compared to the previous step (e.g. previous sign was 1 and current is -1), increment currentLength.
  2. If they do not alternate but are not equal (e.g. previous sign was 1 and current is also 1), the new turbulent subarray starts at the previous element, so set currentLength = 2.
  3. If they are equal (sign is 0), the current subarray ends, reset currentLength = 1.

Solution: Sign-Tracking Scan

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        if (n < 2) return n;

        int maxLen = 1;
        int currentLen = 1;
        int prevSign = 0; // -1, 0, or 1

        for (int i = 1; i < n; i++) {
            int currentSign = Integer.compare(arr[i], arr[i - 1]);

            if (currentSign == 0) {
                currentLen = 1;
            } else if (prevSign * currentSign < 0) { // signs are opposites
                currentLen++;
            } else { // signs are same, or prevSign was 0
                currentLen = 2;
            }

            maxLen = Math.max(maxLen, currentLen);
            prevSign = currentSign;
        }

        return maxLen;
    }
}
class Solution:
    def maxTurbulenceSize(self, arr: list[int]) -> int:
        n = len(arr)
        if n < 2:
            return n

        max_len = 1
        current_len = 1
        prev_sign = 0

        for i in range(1, n):
            if arr[i] > arr[i - 1]:
                current_sign = 1
            elif arr[i] < arr[i - 1]:
                current_sign = -1
            else:
                current_sign = 0

            if current_sign == 0:
                current_len = 1
            elif prev_sign * current_sign < 0:  # alternating signs
                current_len += 1
            else:
                current_len = 2

            max_len = max(max_len, current_len)
            prev_sign = current_sign

        return max_len
#include <vector>
#include <algorithm>

class Solution {
public:
    int maxTurbulenceSize(std::vector<int>& arr) {
        int n = arr.size();
        if (n < 2) return n;

        int maxLen = 1;
        int currentLen = 1;
        int prevSign = 0;

        for (int i = 1; i < n; i++) {
            int currentSign = (arr[i] > arr[i - 1]) - (arr[i] < arr[i - 1]);

            if (currentSign == 0) {
                currentLen = 1;
            } else if (prevSign * currentSign < 0) {
                currentLen++;
            } else {
                currentLen = 2;
            }

            maxLen = std::max(maxLen, currentLen);
            prevSign = currentSign;
        }

        return maxLen;
    }
};

Complexity Analysis:

  • Time Complexity: O(N) where N is the length of arr.
  • Space Complexity: O(1).

← All Problems