978. Longest Turbulent Subarray

MediumArrayDynamic ProgrammingSliding Window
Leetcode Link

Problem Description

The problem provides us with an integer array named arr, and our goal is to find the length of the longest turbulent subarray. A turbulent subarray is defined uniquely by its characteristic that the inequality signs between consecutive elements change or "flip" from one pair to the next. Concretely, a subarray is turbulent if for any two adjacent elements within it, one is greater than the next and the next after that is less than its predecessor, or vice versa; this pattern alternates throughout the subarray.

To put it another way, if the indices of the subarray are from i to j, then for the index k within i and j-1, two conditions are defined:

  1. When k is odd, arr[k] should be greater than arr[k + 1], and when k is even, arr[k] should be less than arr[k + 1].
  2. Or alternatively, when k is odd, arr[k] should be less than arr[k + 1], and when k is even, arr[k] should be greater than arr[k + 1].

Intuition

When approaching this problem, we consider that a turbulent subarray can start at any index and the conditions for a sequence of elements to be turbulent depend solely on the relationship between adjacent elements. Thus, one way to solve this is by iterating through the array and tracking the length of the current turbulent subarray as we go.

The intuition behind the solution lies in a sliding window or two-pointer approach, where we track the current and maximum lengths of valid subarrays. However, we can optimize this strategy by keeping track of the last two comparisons (whether the last was '>' or '<') which can be done with counters that reset when the pattern is broken.

In the provided solution, two variables f and g are used to keep track of the length of two types of turbulent subarrays, one where the first comparison is '<' and the other where the first comparison is '>'. If the current pair of elements continue the turbulence condition, we increment the appropriate counter (f or g), otherwise, we reset it to 1 (the current pair itself can be the beginning of a new subarray). ans is used to keep track of the maximum size found so far.

We iterate through the array using the pairwise utility, which gives us adjacent pairs of elements for easy comparison. For each pair, using the comparison result, we update f and g, then update ans to hold the maximum of ans, f, and g. At the end of the iteration, ans contains the length of the largest turbulent subarray.

The solution leverages a dynamic and continuous update of variables to reflect the current state of the subarray being checked, thus arriving at the final answer without needing to store any intermediate subarrays or additional complex data structures.

Learn more about Dynamic Programming and Sliding Window patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How does merge sort divide the problem into subproblems?

Solution Approach

The implementation of the solution through the provided Python code uses a straightforward approach, mainly utilizing iteration and simple condition checks without the need for additional data structures beyond simple variables. Here’s how it works:

Variables:

  • ans: To keep track of the maximum subarray size found during iteration.
  • f: To track the length of turbulent subarrays where the first condition (arr[k] < arr[k + 1] when k is even, and arr[k] > arr[k + 1] when k is odd) holds true.
  • g: To track the length of turbulent subarrays where the second condition (arr[k] > arr[k + 1] when k is even, and arr[k] < arr[k + 1] when k is odd) holds true.

Iteration:

  • The code uses the pairwise function to create a windowed pair of array elements (a, b) for each adjacent pair in arr.
  • On each iteration step, we compare the elements a and b in the tuple to determine the continuation or the end of a turbulent subarray.

Condition checks and Updates:

  • ff and gg are temporary variables used to calculate the potential new lengths of f and g.
  • If a < b and we are considering the odd index for k, f should be incremented, since the condition arr[k] > arr[k + 1] must hold true for k being even; otherwise, f resets to 1 (subarray starts anew).
  • Conversely, if a > b for an even index, g should be incremented, as the condition arr[k] < arr[k + 1] must hold true for an odd k; otherwise, g resets to 1.
  • After each comparison, f and g are updated with the values from ff and gg, respectively.
  • ans is updated with the maximum value between ans, f, and g.

Return Value:

  • After the loop completes, the value of ans denotes the longest turbulent subarray that can be found in arr.

This solution approach relies on dynamically updating counters and checking each pair once. It avoids the need for complex data structures or algorithms. Due to its simplicity and only using iteration and basic arithmetic operations, the overall time complexity is O(n), where n is the number of elements in arr.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Example Walkthrough

Let's illustrate the solution approach with a small example using the array arr = [9, 4, 2, 10, 7, 8, 8, 1, 9].

  1. Initialize ans = 1, f = 1, and g = 1 because the minimum length of a turbulent subarray is 1 (a single element).

  2. Begin iterating from the start of the array using the pairwise function:

    • First pair (9, 4): since 9 > 4, set ff = 1 and gg = f + 1. Now, g becomes 2 (g = gg), because this pair meets the second condition.
    • Next pair (4, 2): 4 > 2, increment g to 3 (g = g + 1), f resets to 1.
    • Next pair (2, 10): now 2 < 10, so we increment f to g + 1, which is now 4, and reset g to 1.
    • Continue with this pattern for subsequent pairs.

  3. At each step, update ans to the maximum of ans, f, and g to ensure it always holds the maximum subarray length found so far.

Following through with the example sequence:

  • After processing (10, 7), f is reset to 1 since 10 > 7, g = f + 1 = 2, and ans is updated to max(ans, f, g) = 4.
  • After (7, 8), f = g + 1 = 3, g is reset to 1, update ans.
  • After (8, 8), both f and g reset to 1, because the elements are equal and that does not meet any turbulent condition.
  • After (8, 1), g = f + 1 = 2, f is reset to 1, update ans.
  • After (1, 9), f = g + 1 = 3, g is reset to 1, update ans which remains 4, since f is not greater than the current ans.
  1. Finally, the iteration ends and we return ans, which is still 4, representing the longest turbulent subarray [4, 2, 10, 7].

This example showcases the elegance and simplicity of the solution. Without storing any subarrays or using complex structures, the algorithm dynamically keeps track of the state and updates it with each element pair. Overall, this clever approach ensures optimal performance with linear time complexity, only passing through the array once.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxTurbulenceSize(self, arr: List[int]) -> int:
5        # Initialize the maximum length of a turbulent subarray as 1.
6        max_length = increasing = decreasing = 1
7      
8        # Iterate over the array in pairs to check for turbulence.
9        for i in range(len(arr) - 1):
10            # Get the current and next element.
11            current, next_element = arr[i], arr[i + 1]
12          
13            # Temporarily store the new length for an increasing and decreasing sequence.
14            temp_inc = decreasing + 1 if current < next_element else 1
15            temp_dec = increasing + 1 if current > next_element else 1
16          
17            # Update the current length of increasing and decreasing sequences.
18            increasing, decreasing = temp_inc, temp_dec
19          
20            # Update the maximum length if we found a longer turbulent sequence.
21            max_length = max(max_length, increasing, decreasing)
22      
23        # Return the maximum length of turbulent subarray found.
24        return max_length
25
1class Solution {
2    public int maxTurbulenceSize(int[] arr) {
3        int maxLength = 1; // This will store the maximum length of the turbulence.
4        int incLength = 1; // This will store the current increasing turbulence length.
5        int decLength = 1; // This will store the current decreasing turbulence length.
6
7        // Iterate through the array starting from the second element.
8        for (int i = 1; i < arr.length; ++i) {
9            // Determine the new length of increasing turbulence if the current pair is turbulent,
10            // otherwise reset the length to 1.
11            int nextIncLength = arr[i - 1] < arr[i] ? decLength + 1 : 1;
12            // Do the same for decreasing turbulence.
13            int nextDecLength = arr[i - 1] > arr[i] ? incLength + 1 : 1;
14          
15            // Update the current turbulence lengths.
16            incLength = nextIncLength;
17            decLength = nextDecLength;
18          
19            // Update the maximum length found so far.
20            maxLength = Math.max(maxLength, Math.max(incLength, decLength));
21        }
22
23        // Return the maximum turbulence length found.
24        return maxLength;
25    }
26}
27
1#include <vector>
2#include <algorithm> // for max function
3
4class Solution {
5public:
6    // Returns the length of the maximum size turbulent subarray of `arr`.
7    int maxTurbulenceSize(vector<int>& arr) {
8        // Initialize the answer to 1, since the minimum turbulent subarray has a length of 1
9        int max_length = 1; 
10      
11        // Initialize counters for increasing and decreasing sequences
12        // `current_inc` = length of the current subarray where arr[i - 1] < arr[i]
13        // `current_dec` = length of the current subarray where arr[i - 1] > arr[i]
14        int current_inc = 1, current_dec = 1; 
15      
16        // Loop from the second element to the end of the array
17        for (int i = 1; i < arr.size(); ++i) {
18            // If the current element is greater than the previous, increment the increasing counter,
19            // otherwise reset it to 1 (a subarray of length 1 starts with just the current element)
20            int next_inc = arr[i - 1] < arr[i] ? current_dec + 1 : 1;
21          
22            // If the current element is less than the previous, increment the decreasing counter,
23            // otherwise reset it to 1 (a subarray of length 1 starts with just the current element)
24            int next_dec = arr[i - 1] > arr[i] ? current_inc + 1 : 1;
25          
26            // Update the current counters with computed next values
27            current_inc = next_inc;
28            current_dec = next_dec;
29          
30            // Update max_length with the longer of the current increasing and decreasing sequences
31            max_length = max({max_length, current_inc, current_dec});
32        }
33      
34        // Return the maximum length of a turbulent subarray in `arr`
35        return max_length;
36    }
37};
38
1function maxTurbulenceSize(arr: number[]): number {
2    // Initializing variables to track the lengths of turbulent sequences
3    let increasingSequenceLength = 1; // Tracks length of increasing sequence
4    let decreasingSequenceLength = 1; // Tracks length of decreasing sequence
5    let maxSequenceLength = 1; // Tracks the maximum length found
6
7    // Iterate through the array starting from the second element
8    for (let i = 1; i < arr.length; ++i) {
9        // If the current element is greater than the previous,
10        // then the current sequence of 'increasingSequenceLength' can extend
11        // the 'decreasingSequenceLength' sequence by 1.
12        // Otherwise, reset 'increasingSequenceLength' as a new sequence starts.
13        let tempIncreasingLength = arr[i - 1] < arr[i] ? decreasingSequenceLength + 1 : 1;
14
15        // Similarly, if the current element is less than the previous,
16        // then the current sequence of 'decreasingSequenceLength' can extend
17        // the 'increasingSequenceLength' sequence by 1.
18        // Otherwise, reset 'decreasingSequenceLength' as a new sequence starts.
19        let tempDecreasingLength = arr[i - 1] > arr[i] ? increasingSequenceLength + 1 : 1;
20
21        // Update the 'increasingSequenceLength' and 'decreasingSequenceLength' with new lengths
22        increasingSequenceLength = tempIncreasingLength;
23        decreasingSequenceLength = tempDecreasingLength;
24
25        // Update 'maxSequenceLength' to hold the max
26        // between itself and the two sequence lengths
27        maxSequenceLength = Math.max(maxSequenceLength, increasingSequenceLength, decreasingSequenceLength);
28    }
29
30    // Return the maximum turbulence size found in the array
31    return maxSequenceLength;
32}
33
Not Sure What to Study? Take the 2-min Quiz：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Time and Space Complexity

Time Complexity

The time complexity of the code is primarily governed by the single for loop that iterates through the pairwise elements of the array arr. In Python, the pairwise utility creates an iterator that aggregates elements from each iterable sequence. Considering an input array of size n, there will be n - 1 iterations (since pairwise generates tuples of two consecutive elements).

Within the for loop, there are constant time operations like comparisons, assignments, and a call to the max function with three arguments. These operations contribute O(1) time complexity for each iteration.

Therefore, the total time complexity of this algorithm is O(n).

Space Complexity

The space complexity of the algorithm is determined by the extra space used besides the input array. In this case, only a constant number of integer variables (ans, f, g, ff, and gg) are used. No auxiliary data structures that scale with the input size are utilized.

Thus, the space complexity is O(1), which means it uses a constant amount of space regardless of the input array size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the relationship between a tree and a graph?

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Sliding Window Maximum

https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫