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.

Longest Turbulent Subarray — LeetCode 978 Python Solution

MediumArrayDynamic ProgrammingSliding Window

Problem: #978
Pattern: 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

Python

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 ans

Complexity

Measure	Complexity
Time	O(n), where n is the length of the array
Space	O(1) auxiliary

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.

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.