Longest Turbulent Subarray - Practice Coding Problems

Longest Turbulent Subarray - Problem

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

A subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.

More formally, 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 - i is even, and arr[k] < arr[k + 1] when k - i is odd.
OR, for i <= k < j: arr[k] > arr[k + 1] when k - i is odd, and arr[k] < arr[k + 1] when k - i is even.

Input & Output

Example 1 — Basic Turbulent Array

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

› Output: 5

💡 Note: The longest turbulent subarray is [4,2,10,7,8] with pattern: 4 > 2 < 10 > 7 < 8, length = 5

Example 2 — All Equal Elements

$ Input: arr = [4,4,4]

› Output: 1

💡 Note: All elements are equal, so no turbulent subarray exists beyond single elements

Example 3 — Two Elements

$ Input: arr = [100,1]

› Output: 2

💡 Note: A subarray of length 2 with different elements is turbulent: 100 > 1

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with elements to check for turbulent pattern

Find Pattern

Look for alternating > and < comparisons

Return Length

Length of longest turbulent subarray

Key Takeaway

🎯 Key Insight: Use dynamic programming to track sequences ending with increasing/decreasing patterns for O(n) solution

Asked in

A Amazon 35 G Google 28 M Microsoft 22

The key insight is to track turbulent sequences by monitoring when comparison signs alternate. The optimal approach uses dynamic programming with O(n) time and O(1) space, maintaining two states for sequences ending with increasing or decreasing patterns.

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window	O(n)	O(1)	Use a sliding window that expands when turbulent and resets when pattern breaks
Dynamic Programming	O(n)	O(1)	Track the longest turbulent sequences ending with increasing or decreasing patterns
Brute Force	O(n²)	O(1)	Check all possible subarrays to find the longest turbulent one

Sliding Window — Algorithm Steps

Track window start and current comparison direction
Expand window when pattern alternates correctly
Reset window when pattern breaks or elements are equal

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with window of size 1

Expand

Grow window when alternating pattern continues

Reset

Start new window when pattern breaks

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* arr, int n) {
    if (n <= 1) return n;
    
    int maxLen = 1;
    int currentLen = 1;
    
    for (int i = 1; i < n; i++) {
        if (arr[i] == arr[i-1]) {
            currentLen = 1;
        } else if (i == 1 || (arr[i-2] < arr[i-1]) == (arr[i-1] < arr[i])) {
            currentLen = 2;
        } else {
            currentLen++;
        }
        
        if (currentLen > maxLen) {
            maxLen = currentLen;
        }
    }
    
    return maxLen;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int arr[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        arr[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(arr, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array, each element visited once

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for window tracking

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler