Longest Turbulent Subarray

TARGET DECK: Leetcode FILE TAGS: Medium

---

Intuition

• Instead of comparing just the current element in your window with the previous one, compare 3 elements at a time.
• This is because in every case, when you have < >, or > <, then the current element is a valid element within the
• Each time, you reset left to the previous right position (so move up by that amount).
• Also each time, you move right to the maximally possible position of zigzagging.

Complexity

Runtime

$O(N)$

Space

$O(1)$

Code

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        left = 0
        right = 1
        n = len(arr)
        max_window = 1
        while right < n:
            # Check for duplicates
            while left < n - 1 and arr[left] == arr[left + 1]:
                left += 1
            while right < n - 1 and (arr[right - 1] < arr[right] > arr[right + 1] or \
                arr[right - 1] > arr[right] < arr[right + 1]):
                right += 1
            max_window = max(max_window, right - left + 1)
            left = right
            right += 1
 
        return max_window

Notes

Cards

START Basic Front: Longest Turbulent Subarray Back: Compare 3 elements at a time.

END

---

References

Longest Turbulent Subarray