Scale Engineer

Longest Turbulent Subarray

Med
#0932Time: O(n^3)Space: O(1)
Patterns
Sliding WindowDynamic Programming
Data structures
Array

Prompt

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.

 

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 * 104
  • 0 <= arr[i] <= 109

Approaches

3 approaches with complexity analysis and trade-offs.

This approach is the most straightforward but least efficient. It involves systematically generating every possible contiguous subarray from the input array arr. For each of these subarrays, we perform a check to see if it is turbulent. We keep track of the longest turbulent subarray found so far and return its length after all subarrays have been examined.

Algorithm

  • Initialize maxLength to 1.
  • Use two nested loops, with i for the start and j for the end, to generate all possible subarrays arr[i...j].
  • For each subarray, call a helper function isTurbulent(subarray) to check if it meets the turbulent criteria.
  • The isTurbulent check involves iterating through the subarray and ensuring that for any three consecutive elements a, b, c, it holds that (a > b and b < c) or (a < b and b > c). Also, no two adjacent elements can be equal.
  • If the subarray is turbulent, update maxLength = max(maxLength, length of subarray).
  • After checking all subarrays, return maxLength.

Walkthrough

The brute-force method iterates through all possible start and end points of a subarray. For each subarray, it validates the turbulent property. A subarray is turbulent if the comparison sign flips between each adjacent pair of elements. For example, [a, b, c] is turbulent if a > b and b < c, or if a < b and b > c. This check must hold for the entire subarray. A subarray containing equal adjacent elements, like [a, a], is not turbulent (its longest turbulent part is of length 1).

class Solution {    public int maxTurbulenceSize(int[] arr) {        int maxLen = 1;        for (int i = 0; i < arr.length; i++) {            for (int j = i; j < arr.length; j++) {                // Subarray is arr[i...j]                if (isTurbulent(arr, i, j)) {                    maxLen = Math.max(maxLen, j - i + 1);                }            }        }        return maxLen;    }     // Helper to check if subarray arr[start...end] is turbulent    private boolean isTurbulent(int[] arr, int start, int end) {        int len = end - start + 1;        if (len <= 1) {            return true;        }        for (int k = start; k < end; k++) {            // Check for the alternating sign property            if (k + 1 < end) {                boolean c1 = arr[k] > arr[k+1] && arr[k+1] < arr[k+2];                boolean c2 = arr[k] < arr[k+1] && arr[k+1] > arr[k+2];                if (!c1 && !c2) {                    return false;                }            }            // A subarray of length 2 is turbulent if elements are not equal            if (len == 2 && arr[start] == arr[end]) {                return false;            }        }        return true;    }}

Note: The isTurbulent helper function is complex to implement correctly for all edge cases within a brute-force structure, and the provided snippet is a conceptual illustration.

Complexity

Time

O(n^3)

Space

O(1)

Trade-offs

Pros

  • Conceptually simple and easy to understand.

Cons

  • Extremely inefficient and will result in a 'Time Limit Exceeded' error on large inputs.

  • The logic to correctly check if a subarray is turbulent can be complex to implement without errors.

Solutions

class Solution { public int maxTurbulenceSize ( int [] arr ) { int ans = 1 , f = 1 , g = 1 ; for ( int i = 1 ; i < arr . length ; ++ i ) { int ff = arr [ i - 1 ] < arr [ i ] ? g + 1 : 1 ; int gg = arr [ i - 1 ] > arr [ i ] ? f + 1 : 1 ; f = ff ; g = gg ; ans = Math . max ( ans , Math . max ( f , g )); } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem