101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Dynamic Programming Approach - Complex approach
  2. Sliding Window Approach - Complex approach
  3. Count Consecutive Flips Approach - Complex approach

Approach 1: Dynamic Programming Approach

The key insight for solving this problem is to use dynamic programming to track the length of the turbulent subarray ending at each position.

We can define two state variables:

  • inc: the length of the turbulent subarray ending at the current position where the last comparison was increasing (arr[i-1] < arr[i]).
  • dec: the length of the turbulent subarray ending at the current position where the last comparison was decreasing (arr[i-1] > arr[i]).

For each position i, we update these state variables based on the comparison between arr[i-1] and arr[i]:

  • If arr[i-1] < arr[i], we can extend a turbulent subarray that ended with a decreasing comparison, so inc = dec + 1.
  • If arr[i-1] > arr[i], we can extend a turbulent subarray that ended with an increasing comparison, so dec = inc + 1.
  • If arr[i-1] == arr[i], we can't extend any turbulent subarray, so inc = dec = 1.

The maximum length of a turbulent subarray is the maximum value of inc or dec encountered during the iteration.

Algorithm:

  1. Initialize inc = 1 and dec = 1, representing the length of turbulent subarrays ending at the first position.
  2. Initialize maxLength = 1, representing the maximum length of a turbulent subarray found so far.
  3. Iterate through the array starting from the second element (i = 1):
  4. a. If arr[i-1] < arr[i], update inc = dec + 1 and dec = 1.
  5. b. If arr[i-1] > arr[i], update dec = inc + 1 and inc = 1.
  6. c. If arr[i-1] == arr[i], reset inc = dec = 1.
  7. d. Update maxLength = max(maxLength, max(inc, dec)).
  8. Return maxLength as the result.

Time Complexity:

O(n)

Where n is the length of the array. We iterate through the array once, performing constant-time operations at each step.

Space Complexity:

O(1)

We only use a constant amount of extra space regardless of the input size.

Approach 2: Sliding Window Approach

Another approach is to use a sliding window to track the current turbulent subarray. We expand the window as long as the turbulence property is maintained, and reset it when the property is violated.

We can define a variable c to track the comparison result between adjacent elements:

  • c = 0 means the elements are equal.
  • c = 1 means the current element is greater than the previous one.
  • c = -1 means the current element is less than the previous one.

For a turbulent subarray, the value of c should alternate between 1 and -1. If c becomes 0 or doesn't alternate, we need to reset or adjust our window.

Algorithm:

  1. Initialize anchor = 0, representing the start of the current turbulent subarray.
  2. Initialize maxLength = 1, representing the maximum length of a turbulent subarray found so far.
  3. Iterate through the array starting from the second element (i = 1):
  4. a. Calculate the comparison result c between arr[i-1] and arr[i].
  5. b. If c == 0 (elements are equal), reset anchor = i.
  6. c. If i == 1 or c * prev_c != -1 (comparison sign doesn&apos;t flip), reset anchor = i - 1.
  7. d. Update maxLength = max(maxLength, i - anchor + 1).
  8. e. Update prev_c = c for the next iteration.
  9. Return maxLength as the result.

Time Complexity:

O(n)

Where n is the length of the array. We iterate through the array once, performing constant-time operations at each step.

Space Complexity:

O(1)

We only use a constant amount of extra space regardless of the input size.

Approach 3: Count Consecutive Flips Approach

A simpler approach is to count the number of consecutive comparison sign flips as we iterate through the array. Each time the comparison sign flips, we increment our counter. If the sign doesn't flip or elements are equal, we reset or adjust our counter.

This approach is more intuitive and easier to implement, but it achieves the same time and space complexity as the previous approaches.

Algorithm:

  1. Initialize maxLength = 1, representing the maximum length of a turbulent subarray found so far.
  2. Initialize currentLength = 1, representing the length of the current turbulent subarray.
  3. Initialize prevComp = 0, representing the previous comparison result (0 for equal, 1 for increasing, -1 for decreasing).
  4. Iterate through the array starting from the second element (i = 1):
  5. a. Calculate the current comparison result currComp between arr[i-1] and arr[i].
  6. b. If currComp == 0 (elements are equal), reset currentLength = 1.
  7. c. Else if prevComp * currComp >= 0 (comparison sign doesn&apos;t flip), reset currentLength = 2.
  8. d. Else (comparison sign flips), increment currentLength by 1.
  9. e. Update maxLength = max(maxLength, currentLength).
  10. f. Update prevComp = currComp for the next iteration.
  11. Return maxLength as the result.

Time Complexity:

O(n)

Where n is the length of the array. We iterate through the array once, performing constant-time operations at each step.

Space Complexity:

O(1)

We only use a constant amount of extra space regardless of the input size.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function maxTurbulenceSize(arr):
    n = length of arr
    if n == 1:
        return 1
 
    inc = 1  // Length of turbulent subarray ending with increasing comparison
    dec = 1  // Length of turbulent subarray ending with decreasing comparison
    maxLength = 1
 
    for i from 1 to n-1:
        if arr[i-1] < arr[i]:
            inc = dec + 1
            dec = 1
        else if arr[i-1] > arr[i]:
            dec = inc + 1
            inc = 1
        else:  // arr[i-1] == arr[i]
            inc = 1
            dec = 1
 
        maxLength = max(maxLength, max(inc, dec))
 
    return maxLength
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone