Longest Turbulent Subarray - Leetcode Solution

Problem Statement:

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 is odd, and

  • arr[k] < arr[k + 1] when k is even.

• Or, for i <= k < j:

  • arr[k] > arr[k + 1] when k is even, and

  • arr[k] < arr[k + 1] when k is odd.

Solution:

The brute force approach would be to find all possible subarrays and check each subarray if it is turbulent or not. But this approach would take O(n^3) time complexity, which is not efficient for large arrays.

So, let's try to come up with a more efficient approach. We can use a sliding window approach to find the longest turbulent subarray.

We can start at the beginning of the array and keep track of the length of the current turbulent subarray. We can also keep track of the last comparison sign (>, < or =) and the current comparison sign for each pair of adjacent elements.

If the current comparison sign is different from the previous comparison sign, we can update the length of the current turbulent subarray and continue.

If the current comparison sign is the same as the previous comparison sign, we can reset the length of the current turbulent subarray to be 2 (since we have found a new turbulent subarray with length 2).

Let's see the implementation:

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

        # For the first two elements
        # Initialize the length to 2 if they are different
        # Otherwise, initialize the length to 1
        length = 2 if arr[0] != arr[1] else 1
        last_sign = -1
        if arr[0] < arr[1]:
            last_sign = 1
        
        max_length = length
        
        # Slide the window by comparing adjacent pairs
        for i in range(1, n-1):
            curr_sign = -1
            if arr[i] < arr[i+1]:
                curr_sign = 1
            
            if curr_sign == last_sign:
                length = 2
            else:
                length += 1
                
            last_sign = curr_sign
            
            max_length = max(max_length, length)
        
        return max_length

Time Complexity: O(n)

Space Complexity: O(1)

So, this sliding window approach is much more efficient than the brute force approach.

1