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:
i <= k < j:
arr[k] > arr[k + 1] when k is odd, andarr[k] < arr[k + 1] when k is even.i <= k < j:
arr[k] > arr[k + 1] when k is even, andarr[k] < arr[k + 1] when k is odd.
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]
Example 2:
Input: arr = [4,8,12,16] Output: 2
Example 3:
Input: arr = [100] Output: 1
Constraints:
1 <= arr.length <= 4 * 1040 <= arr[i] <= 109In this approach, a sliding window technique is used to identify the longest turbulent subarray. We maintain two pointers: 'start' and 'end'. Initially, 'start' is set to 0, and 'end' is used to iterate over the array. At each step, we check the relationship between consecutive elements to determine the turbulence. When the pattern breaks, we calculate the length of the turbulent segment and adjust the pointers accordingly.
This C implementation iterates over the array, checking each adjacent pair of elements to determine if they are part of a turbulent sequence. It adjusts the length of the current turbulent subarray accordingly and keeps track of the maximum found so far.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the array, as the solution involves a single pass over the array.
Space Complexity: O(1), as it uses a constant amount of extra space.
This approach utilizes dynamic programming to maintain two arrays: inc and dec, which record the lengths of increasing and decreasing turbulent subarrays that end at each index. The solution updates these values based on the conditions of the current element relative to the previous one, and tracks the global maximum using the values in inc and dec.
This C implementation uses two variables, inc and dec, to manage the lengths of turbulent subarrays. During each iteration, they are updated based on comparisons between current and previous elements.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), as the array is traversed once.
Space Complexity: O(1), minimal additional space is used.
| Approach | Complexity |
|---|---|
| Sliding Window | Time Complexity: O(n), where n is the length of the array, as the solution involves a single pass over the array. |
| Dynamic Programming | Time Complexity: O(n), as the array is traversed once. |
Longest Turbulent Array - Leetcode 978 - Python • NeetCodeIO • 16,191 views views
Watch 9 more video solutions →Practice Longest Turbulent Subarray with our built-in code editor and test cases.
Practice on FleetCode