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.

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.

Examples

Example 1

1
2
3

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

1
2

Input: arr = [4,8,12,16]
Output: 2

Example 3

1
2

Input: arr = [100]
Output: 1

Solution

Method 1 – Sliding Window

Intuition

We use two pointers to maintain a window where the comparison sign flips at every step. If the current comparison does not flip, reset the window.

Approach

  1. Initialize two pointers and a variable for the answer.
  2. For each element, check the comparison sign with the previous element.
  3. If the sign flips, extend the window; otherwise, reset the window.
  4. Track the maximum window size.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size(), ans = 1, l = 0;
        for (int r = 1; r < n; ++r) {
            if (arr[r-1] == arr[r]) l = r;
            else if (r == 1 || (arr[r-2] < arr[r-1] && arr[r-1] > arr[r]) || (arr[r-2] > arr[r-1] && arr[r-1] < arr[r])) {
                // continue
            } else l = r-1;
            ans = max(ans, r-l+1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func maxTurbulenceSize(arr []int) int {
    n, ans, l := len(arr), 1, 0
    for r := 1; r < n; r++ {
        if arr[r-1] == arr[r] {
            l = r
        } else if r == 1 || (arr[r-2] < arr[r-1] && arr[r-1] > arr[r]) || (arr[r-2] > arr[r-1] && arr[r-1] < arr[r]) {
            // continue
        } else {
            l = r-1
        }
        if r-l+1 > ans {
            ans = r-l+1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length, ans = 1, l = 0;
        for (int r = 1; r < n; ++r) {
            if (arr[r-1] == arr[r]) l = r;
            else if (r == 1 || (arr[r-2] < arr[r-1] && arr[r-1] > arr[r]) || (arr[r-2] > arr[r-1] && arr[r-1] < arr[r])) {
                // continue
            } else l = r-1;
            ans = Math.max(ans, r-l+1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun maxTurbulenceSize(arr: IntArray): Int {
        val n = arr.size
        var ans = 1
        var l = 0
        for (r in 1 until n) {
            if (arr[r-1] == arr[r]) l = r
            else if (r == 1 || (arr[r-2] < arr[r-1] && arr[r-1] > arr[r]) || (arr[r-2] > arr[r-1] && arr[r-1] < arr[r])) {
                // continue
            } else l = r-1
            ans = maxOf(ans, r-l+1)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def maxTurbulenceSize(self, arr: list[int]) -> int:
        n, ans, l = len(arr), 1, 0
        for r in range(1, n):
            if arr[r-1] == arr[r]:
                l = r
            elif r == 1 or (arr[r-2] < arr[r-1] and arr[r-1] > arr[r]) or (arr[r-2] > arr[r-1] and arr[r-1] < arr[r]):
                pass
            else:
                l = r-1
            ans = max(ans, r-l+1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn max_turbulence_size(arr: Vec<i32>) -> i32 {
        let n = arr.len();
        let mut ans = 1;
        let mut l = 0;
        for r in 1..n {
            if arr[r-1] == arr[r] {
                l = r;
            } else if r == 1 || (arr[r-2] < arr[r-1] && arr[r-1] > arr[r]) || (arr[r-2] > arr[r-1] && arr[r-1] < arr[r]) {
                // continue
            } else {
                l = r-1;
            }
            ans = ans.max(r-l+1);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    maxTurbulenceSize(arr: number[]): number {
        const n = arr.length
        let ans = 1, l = 0
        for (let r = 1; r < n; ++r) {
            if (arr[r-1] === arr[r]) l = r
            else if (r === 1 || (arr[r-2] < arr[r-1] && arr[r-1] > arr[r]) || (arr[r-2] > arr[r-1] && arr[r-1] < arr[r])) {
                // continue
            } else l = r-1
            ans = Math.max(ans, r-l+1)
        }
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Single pass through arr.
  • 🧺 Space complexity: O(1) — Only a few variables are used.