Jobs

Interviews

Discussions

Longest Turbulent Subarray

#769 Most AskedMedium

Longest Turbulent Subarray #769 Most Asked

Medium

Microsoft

9 views

Topics:

ArraysSliding Windows

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 * 10⁴
0 <= arr[i] <= 10⁹

Try coding it in LeetCode

Longest Turbulent Subarray

#769 Most AskedMedium

Longest Turbulent Subarray #769 Most Asked

Medium

Microsoft

9 views

Topics:

ArraysSliding Windows

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 * 10⁴
0 <= arr[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected data type of the array elements, and what is the range of possible values for those elements?
Can the input array be empty, or can it contain only one element? What should I return in such cases?
What constitutes a 'turbulent' relationship when two adjacent elements are equal?
If multiple longest turbulent subarrays exist, is it acceptable to return any one of them, or is there a preference (e.g., the one that appears first)?
Is the input array read-only, or am I allowed to modify it in place during the process?

Brute Force Solution

Approach

We need to find the longest stretch of numbers that go up and down alternately, like a bumpy road. The brute force way means we'll try every possible stretch to see if it's bumpy and then find the longest one.

Here's how the algorithm would work step-by-step:

Start by looking at just the first number.
Then, look at the first two numbers together. Are they bumpy (one higher than the other)?
Next, look at the first three numbers together. Are they bumpy all the way (alternating higher and lower)?
Keep doing this, adding one more number to the group each time and checking if the whole group is bumpy.
Now, do the same thing but starting from the second number instead of the first.
Then start from the third number, and so on, until you've started from every number.
As you check each group, remember the length of the longest bumpy group you've found so far.
After checking every possible group, the longest bumpy group you remembered is the answer.

Code Implementation

def longest_turbulent_subarray_brute_force(array):
    max_length = 0

    for start_index in range(len(array)): 
        for end_index in range(start_index, len(array)): 
            sub_array = array[start_index : end_index + 1]

            if len(sub_array) <= 1:
                max_length = max(max_length, len(sub_array))
                continue

            is_turbulent = True
            # Check if the current subarray is turbulent.

            for index in range(1, len(sub_array)): 
                if index % 2 == 1: 
                    if sub_array[index] >= sub_array[index - 1]:
                        is_turbulent = False
                        break
                else:
                    if sub_array[index] <= sub_array[index - 1]:
                        is_turbulent = False
                        break

            #Alternative check, different start.
            if not is_turbulent and len(sub_array) > 1:
                is_turbulent = True

                for index in range(1, len(sub_array)): 
                    if index % 2 == 1:
                        if sub_array[index] <= sub_array[index - 1]:
                            is_turbulent = False
                            break
                    else:
                        if sub_array[index] >= sub_array[index - 1]:
                            is_turbulent = False
                            break
            # Update max length if turbulent

            if is_turbulent:

                current_length = len(sub_array)

                max_length = max(max_length, current_length)

    return max_length

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the array starting at each index. For each starting index, it checks all possible subarrays beginning at that index to determine if they are turbulent. In the worst-case scenario, for an array of size n, this involves nested loops: an outer loop that iterates n times and, on average, an inner loop that iterates n/2 times. Therefore, the number of operations approximates n * n/2, simplifying to a time complexity of O(n²).

Space Complexity

O(1) – The brute force approach described does not use any auxiliary data structures like arrays, hashmaps, or lists. It only involves iterating through the input array and comparing adjacent elements within the current subarray under consideration. Thus, the space complexity is constant, independent of the input size N, as it only uses a few variables to track the start and end indices of the subarrays and the maximum length found so far.

Optimal Solution

Approach

The key is to efficiently track the length of turbulent subarrays as we move through the data. We maintain two counts representing the lengths of increasing and decreasing turbulent subarrays ending at the current position. By updating these counts strategically, we avoid redundant calculations.

Here's how the algorithm would work step-by-step:

Think of a 'turbulent' sequence as one where the numbers go up and down, or down and up, like a zigzag.
Start at the beginning of the list of numbers.
Keep track of two things: the length of the current 'up-and-down' sequence, and the length of the current 'down-and-up' sequence. We'll call them the 'increasing' and 'decreasing' counts.
Look at the next number in the list and compare it to the number before it.
If it goes up, it extends the 'decreasing' sequence. Reset the 'increasing' sequence to 1.
If it goes down, it extends the 'increasing' sequence. Reset the 'decreasing' sequence to 1.
If the two numbers are the same, both sequences stop, and both counts become 1.
After each step, remember the longest 'up-and-down' or 'down-and-up' sequence we've seen so far.
Keep going until you reach the end of the list. The longest length you remember is the answer.

Code Implementation

def longestTurbulentSubarray(data):
    increasing_count = 1
    decreasing_count = 1
    max_length = 1

    for i in range(1, len(data)):
        if data[i] > data[i - 1]:
            # Extending decreasing, so reset increasing.
            decreasing_count = increasing_count + 1
            increasing_count = 1

        elif data[i] < data[i - 1]:
            # Extending increasing, so reset decreasing.
            increasing_count = decreasing_count + 1
            decreasing_count = 1

        else:
            # Reset both counts if the numbers are equal.
            increasing_count = 1
            decreasing_count = 1

        max_length = max(max_length, increasing_count, decreasing_count)

    return max_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n exactly once. In each iteration, it performs a constant number of comparisons to update the increasing and decreasing counts and the maximum length. Therefore, the time complexity is directly proportional to the input size, resulting in O(n).

Space Complexity

O(1) – The algorithm maintains two integer variables, 'increasing' and 'decreasing', to track the lengths of the turbulent subarrays. These variables use a constant amount of space regardless of the input array's size, denoted as N. No other data structures that scale with the input are employed. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or Empty Input Array	Return 0 immediately as there's no subarray.
Array with only one element	Return 1 as a single element is technically a turbulent subarray of length 1.
Array with two identical elements	Return 1, as a turbulent subarray requires alternating signs.
Array with two different elements	Return 2, since any two different elements form a turbulent subarray.
Array with all identical values	Return 1, as no two adjacent elements satisfy the turbulent condition.
Array with alternating values (e.g., [1, 2, 1, 2, 1])	The algorithm should correctly identify the entire array as a turbulent subarray and return its length.
Array with consecutive identical values breaking a turbulent sequence	The algorithm should reset the turbulent sequence counter when consecutive identical values are encountered.
Large input array to assess time complexity	The solution should ideally have linear time complexity to handle large arrays efficiently; check that it scales to the maximum constraint size (e.g., 4 * 10^4).

Null or Empty Input Array

How to Handle:

Return 0 immediately as there's no subarray.

Array with only one element

How to Handle:

Return 1 as a single element is technically a turbulent subarray of length 1.

Array with two identical elements

How to Handle:

Return 1, as a turbulent subarray requires alternating signs.

Array with two different elements

How to Handle:

Return 2, since any two different elements form a turbulent subarray.

Array with all identical values

How to Handle:

Return 1, as no two adjacent elements satisfy the turbulent condition.

Array with alternating values (e.g., [1, 2, 1, 2, 1])

How to Handle:

The algorithm should correctly identify the entire array as a turbulent subarray and return its length.

Array with consecutive identical values breaking a turbulent sequence

How to Handle:

The algorithm should reset the turbulent sequence counter when consecutive identical values are encountered.

Large input array to assess time complexity

How to Handle:

The solution should ideally have linear time complexity to handle large arrays efficiently; check that it scales to the maximum constraint size (e.g., 4 * 10^4).

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected data type of the array elements, and what is the range of possible values for those elements?
Can the input array be empty, or can it contain only one element? What should I return in such cases?
What constitutes a 'turbulent' relationship when two adjacent elements are equal?
If multiple longest turbulent subarrays exist, is it acceptable to return any one of them, or is there a preference (e.g., the one that appears first)?
Is the input array read-only, or am I allowed to modify it in place during the process?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at just the first number.
Then, look at the first two numbers together. Are they bumpy (one higher than the other)?
Next, look at the first three numbers together. Are they bumpy all the way (alternating higher and lower)?
Keep doing this, adding one more number to the group each time and checking if the whole group is bumpy.
Now, do the same thing but starting from the second number instead of the first.
Then start from the third number, and so on, until you've started from every number.
As you check each group, remember the length of the longest bumpy group you've found so far.
After checking every possible group, the longest bumpy group you remembered is the answer.

Code Implementation

def longest_turbulent_subarray_brute_force(array):
    max_length = 0

    for start_index in range(len(array)): 
        for end_index in range(start_index, len(array)): 
            sub_array = array[start_index : end_index + 1]

            if len(sub_array) <= 1:
                max_length = max(max_length, len(sub_array))
                continue

            is_turbulent = True
            # Check if the current subarray is turbulent.

            for index in range(1, len(sub_array)): 
                if index % 2 == 1: 
                    if sub_array[index] >= sub_array[index - 1]:
                        is_turbulent = False
                        break
                else:
                    if sub_array[index] <= sub_array[index - 1]:
                        is_turbulent = False
                        break

            #Alternative check, different start.
            if not is_turbulent and len(sub_array) > 1:
                is_turbulent = True

                for index in range(1, len(sub_array)): 
                    if index % 2 == 1:
                        if sub_array[index] <= sub_array[index - 1]:
                            is_turbulent = False
                            break
                    else:
                        if sub_array[index] >= sub_array[index - 1]:
                            is_turbulent = False
                            break
            # Update max length if turbulent

            if is_turbulent:

                current_length = len(sub_array)

                max_length = max(max_length, current_length)

    return max_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Think of a 'turbulent' sequence as one where the numbers go up and down, or down and up, like a zigzag.
Start at the beginning of the list of numbers.
Keep track of two things: the length of the current 'up-and-down' sequence, and the length of the current 'down-and-up' sequence. We'll call them the 'increasing' and 'decreasing' counts.
Look at the next number in the list and compare it to the number before it.
If it goes up, it extends the 'decreasing' sequence. Reset the 'increasing' sequence to 1.
If it goes down, it extends the 'increasing' sequence. Reset the 'decreasing' sequence to 1.
If the two numbers are the same, both sequences stop, and both counts become 1.
After each step, remember the longest 'up-and-down' or 'down-and-up' sequence we've seen so far.
Keep going until you reach the end of the list. The longest length you remember is the answer.

Code Implementation

def longestTurbulentSubarray(data):
    increasing_count = 1
    decreasing_count = 1
    max_length = 1

    for i in range(1, len(data)):
        if data[i] > data[i - 1]:
            # Extending decreasing, so reset increasing.
            decreasing_count = increasing_count + 1
            increasing_count = 1

        elif data[i] < data[i - 1]:
            # Extending increasing, so reset decreasing.
            increasing_count = decreasing_count + 1
            decreasing_count = 1

        else:
            # Reset both counts if the numbers are equal.
            increasing_count = 1
            decreasing_count = 1

        max_length = max(max_length, increasing_count, decreasing_count)

    return max_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or Empty Input Array	Return 0 immediately as there's no subarray.
Array with only one element	Return 1 as a single element is technically a turbulent subarray of length 1.
Array with two identical elements	Return 1, as a turbulent subarray requires alternating signs.
Array with two different elements	Return 2, since any two different elements form a turbulent subarray.
Array with all identical values	Return 1, as no two adjacent elements satisfy the turbulent condition.
Array with alternating values (e.g., [1, 2, 1, 2, 1])	The algorithm should correctly identify the entire array as a turbulent subarray and return its length.
Array with consecutive identical values breaking a turbulent sequence	The algorithm should reset the turbulent sequence counter when consecutive identical values are encountered.
Large input array to assess time complexity	The solution should ideally have linear time complexity to handle large arrays efficiently; check that it scales to the maximum constraint size (e.g., 4 * 10^4).

Null or Empty Input Array

How to Handle:

Return 0 immediately as there's no subarray.

Array with only one element

How to Handle:

Return 1 as a single element is technically a turbulent subarray of length 1.

Array with two identical elements

How to Handle:

Return 1, as a turbulent subarray requires alternating signs.

Array with two different elements

How to Handle:

Return 2, since any two different elements form a turbulent subarray.

Array with all identical values

How to Handle:

Return 1, as no two adjacent elements satisfy the turbulent condition.

Array with alternating values (e.g., [1, 2, 1, 2, 1])

How to Handle:

The algorithm should correctly identify the entire array as a turbulent subarray and return its length.

Array with consecutive identical values breaking a turbulent sequence

How to Handle:

The algorithm should reset the turbulent sequence counter when consecutive identical values are encountered.

Large input array to assess time complexity

How to Handle:

The solution should ideally have linear time complexity to handle large arrays efficiently; check that it scales to the maximum constraint size (e.g., 4 * 10^4).

0/1114 Microsoft questions completed

0/1114 completed