Longest Turbulent Subarray

Problem Statement

The objective is to find the length of the longest subarray within a given integer array arr, where the subarray exhibits turbulent properties. A subarray is considered turbulent if the relationship between consecutive elements alternates between greater than and less than, depending upon the even or odd indexed positions of the elements within the subarray’s overall structure in arr. Specifically, for any part of the subarray arr[i] through arr[j]:

• When an index k is odd:
  • arr[k] > arr[k + 1] and for the next element,
  • arr[k + 1] < arr[k + 2] if k + 1 is even.
• Conversely, when an index k is even:
  • arr[k] < arr[k + 1] and subsequently,
  • arr[k + 1] > arr[k + 2] if k + 1 is odd.

By understanding and identifying this pattern, we need to determine the maximum possible length of such a subarray.

Examples

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

Approach and Intuition

The turbulent subarray requires an alternation in comparison results (greater than or less than) between every adjacent pair. This pattern can be seen as a "zigzag" movement if we visualize the array values in a graph-like structure.

Let's break down the approach based on the examples provided, using the arr values to guide our logic:

• Example 1: arr = [9,4,2,10,7,8,8,1,9]

  • Here, the turbulent subarray starts at position 1 (value 4) and ends at position 5 (value 8), having elements [4, 2, 10, 7, 8] showing a sequence of descends and ascends. This subarray length is 5, matching the required alternating pattern.

• Example 2: arr = [4,8,12,16]

  • The output is 2, which means the longest turbulent subarray is just between two adjacent numbers like [4, 8] or [8, 12]. This is because the entire set just ascends in values, breaking the condition for lengths greater than 2.

• Example 3: arr = [100]

  • With a single element, the maximal turbulent subarray is the element itself, making the length 1 by default.

Observations from examples:

1. Initiation Condition: A valid turbulent subarray needs at least 2 elements (min length is 2 unless the array itself is smaller).
2. Tracking Mechanism:
   • Utilize two variables, say max_length to track the maximum length found so far, and current_length to track the length of the current turbulent sequence.
   • Scan through the array and compare each element to the next.
   • Update current_length based on whether the turbulent condition is met or not, comparing with the previous element relative position (odd/even index).
   • Update max_length with current_length whenever a greater value is found.
3. Termination: If at any point the sequence does not satisfy the turbulent conditions and you were tracking a potential subarray, record its length, reset current_length, and proceed with the next potential starting index.

By analyzing elements in a sequential manner and maintaining optimal tracking and updates of the lengths of turbulent subarrays, this problem can be efficiently tackled ensuring all conditions and constraints are adhered to.

Solutions

class Solution {
    public int longestTurbulentSubarray(int[] inputArray) {
        int size = inputArray.length;
        int maxLength = 1;
        int start = 0;

        for (int index = 1; index < size; ++index) {
            int comp = Integer.compare(inputArray[index-1], inputArray[index]);
            if (comp == 0) {
                start = index;
            } else if (index == size-1 || comp * Integer.compare(inputArray[index], inputArray[index+1]) != -1) {
                maxLength = Math.max(maxLength, index - start + 1);
                start = index;
            }
        }

        return maxLength;
    }
}