We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Turbulent Subarray

Difficulty: Medium

Problem Description

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.

Key Insights

  • A turbulent subarray alternates between increasing and decreasing elements.
  • We can keep track of the length of the current turbulent subarray while iterating through the array.
  • If two adjacent elements are equal, the turbulent subarray ends.
  • We can determine the turbulence by comparing the signs of differences between adjacent elements.

Space and Time Complexity

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

Solution

To solve the problem, we will use a single pass through the array while maintaining a count of the current turbulent subarray length. We will compare adjacent elements to check if the current element is greater or less than the next one. We will update our maximum length whenever we find a valid turbulent condition. If we encounter equal elements, we reset our count.

Code Solutions

def maxTurbulenceSize(arr):
    n = len(arr)
    if n < 2:
        return n

    max_length = 1
    current_length = 1

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

        max_length = max(max_length, current_length)

    return max_length
← Back to All Questions