MediumNo. 0978
Longest Turbulent Subarray — LeetCode 978 Python Solution
- Pattern
- Sliding Window
- Topics
- Array, Dynamic Programming, Sliding Window
- Reading time
- 2 min
- Source
- leetcode.com
The 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.
Example
- Input
- arr = [9,4,2,10,7,8,8,1,9]
- Output
- 5
- Explanation
- arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
Python solution
class Solution:
def maxTurbulenceSize(self, arr: List[int]) -> int:
ans = f = g = 1
for a, b in pairwise(arr):
ff = g + 1 if a < b else 1
gg = f + 1 if a > b else 1
f, g = ff, gg
ans = max(ans, f, g)
return ansComplexity
- Time
- O(n)where n is the length of the array
- Space · auxiliary
- O(1)
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 978. Longest Turbulent Subarray is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0413 | Arithmetic Slices | Medium |
| 0689 | Maximum Sum of 3 Non-Overlapping Subarrays | Hard |
| 1031 | Maximum Sum of Two Non-Overlapping Subarrays | Medium |
| 1425 | Constrained Subsequence Sum | Hard |
| 1493 | Longest Subarray of 1's After Deleting One Element | Medium |
| 0975 | Odd Even Jump | Hard |
Frequently asked questions
- How hard is LeetCode 978. Longest Turbulent Subarray?
LeetCode 978. Longest Turbulent Subarray is rated Medium on LeetCode.
- What is the time complexity of LeetCode 978. Longest Turbulent Subarray?
The Python solution on this page runs in O(n), where n is the length of the array.
- What is the space complexity of LeetCode 978. Longest Turbulent Subarray?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 978. Longest Turbulent Subarray cover?
LeetCode 978. Longest Turbulent Subarray is tagged Array, Dynamic Programming and Sliding Window on LeetCode.