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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Turbulent Subarray

Number: 1020

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an integer array arr, find the length of the longest turbulent subarray. A subarray is turbulent if the comparison sign between every two consecutive elements alternates. For example, in a turbulent subarray, if arr[i] > arr[i+1] then arr[i+1] < arr[i+2] must hold, or vice versa.

Key Insights

  • A turbulent subarray requires alternating "greater than" and "less than" comparisons.
  • A sliding window or dynamic programming approach can be used to solve the problem in O(n) time.
  • Reset the subarray length when encountering equal adjacent elements or when the alternating condition fails.
  • Handle the case where the array has only one element.

Space and Time Complexity

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

Solution

We can solve the problem using a dynamic programming / sliding window approach:

  1. If the array has only one element, return 1.
  2. Initialize a variable (currentLength) to keep track of the current turbulent subarray length.
  3. Traverse the array from the second element and:
    • If the current element is equal to the previous element, reset currentLength to 1.
    • Otherwise, if the current and previous comparisons create a valid alternating pattern when compared to the one before them, increment currentLength.
    • If the alternating pattern breaks, reset currentLength to 2 (since the current two elements may start a new turbulent subarray).
  4. Track the maximum length seen during the traversal.

Key trick: Instead of precomputing comparison signs, we check the alternating condition on the fly using the relationship between three consecutive elements.

Code Solutions

# Function to find the length of the longest turbulent subarray.
def maxTurbulenceSize(arr):
    n = len(arr)
    if n == 1:
        return 1

    # Initialize maximum turbulent subarray length and current subarray length.
    maxLength = 1
    currentLength = 1

    # Iterate through the array.
    for i in range(1, n):
        # If current and previous elements are equal, reset the current sequence.
        if arr[i] == arr[i - 1]:
            currentLength = 1
        else:
            # For the first pair or if alternating condition holds with previous comparison.
            if i == 1 or (arr[i - 1] - arr[i - 2]) * (arr[i] - arr[i - 1]) < 0:
                currentLength += 1
            else:
                # Reset: the current pair forms a new turbulent subarray of length 2.
                currentLength = 2
        # Update the maximum observed length.
        maxLength = max(maxLength, currentLength)
    return maxLength

# Example usage:
print(maxTurbulenceSize([9,4,2,10,7,8,8,1,9]))  # Expected output: 5
← Back to All Questions