Longest Strictly Increasing or Strictly Decreasing Subarray

Easy

Amazon

2 views

Topics:

Arrays

You are given an array of integers nums. Return the length of the longest subarray of nums which is either strictly increasing or strictly decreasing.

For example:

[1,4,3,3,2] should return 2 because the strictly increasing subarrays are [1], [2], [3], [3], [4], and [1,4], and the strictly decreasing subarrays are [1], [2], [3], [3], [4], [3,2], and [4,3]. Thus, the longest is length 2.
[3,3,3,3] should return 1 because the strictly increasing subarrays are [3], [3], [3], and [3], and the strictly decreasing subarrays are [3], [3], [3], and [3]. Thus, the longest is length 1.
[3,2,1] should return 3 because the strictly increasing subarrays are [3], [2], and [1], and the strictly decreasing subarrays are [3], [2], [1], [3,2], [2,1], and [3,2,1]. Thus, the longest is length 3.

Write a function that takes in an array of integers and returns the length of the longest increasing or decreasing subarray.

Longest Strictly Increasing or Strictly Decreasing Subarray

Easy

Amazon

2 views

Topics:

Arrays

You are given an array of integers nums. Return the length of the longest subarray of nums which is either strictly increasing or strictly decreasing.

For example:

[1,4,3,3,2] should return 2 because the strictly increasing subarrays are [1], [2], [3], [3], [4], and [1,4], and the strictly decreasing subarrays are [1], [2], [3], [3], [4], [3,2], and [4,3]. Thus, the longest is length 2.
[3,3,3,3] should return 1 because the strictly increasing subarrays are [3], [3], [3], and [3], and the strictly decreasing subarrays are [3], [3], [3], and [3]. Thus, the longest is length 1.
[3,2,1] should return 3 because the strictly increasing subarrays are [3], [2], and [1], and the strictly decreasing subarrays are [3], [2], [1], [3,2], [2,1], and [3,2,1]. Thus, the longest is length 3.

Write a function that takes in an array of integers and returns the length of the longest increasing or decreasing subarray.

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 return value (or type) if the input array is empty or null?
Can the input array contain duplicate numbers? If so, how should that affect the determination of increasing or decreasing?
What is the range of integer values within the input array? Should I be concerned about potential integer overflow?
Is a single element considered a strictly increasing or decreasing subarray, and if so, what should the length of the longest such subarray be?
If there are multiple subarrays with the same maximum length that satisfy the conditions, can I return the length of any one of them?

Brute Force Solution

Approach

The brute force approach to this problem is all about trying every single possibility. We will look at every possible consecutive group of numbers in the list and check if that group is strictly increasing or strictly decreasing.

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

Start by considering a group of just one number. Is this group increasing or decreasing? It is considered both, so make a note of its length (which is 1).
Next, consider every possible group of two consecutive numbers. For each group, check if the second number is bigger than the first (increasing) or smaller than the first (decreasing). If it is, make a note of the group's length (which is 2). If not, move on.
Then, consider every possible group of three consecutive numbers. Check if each number is bigger (increasing) or smaller (decreasing) than the one before it. If the entire group follows the pattern, remember its length (which is 3). If any part of the group breaks the pattern, discard it.
Continue this process, considering groups of four, five, and so on, until you reach the full length of the original list of numbers. Each time, check if the group of numbers is either strictly increasing or strictly decreasing.
As you go, keep track of the longest group you've found that fits either the increasing or decreasing pattern.
In the end, the longest length you recorded is the answer you're looking for.

Code Implementation

def longest_strictly_increasing_or_decreasing_subarray_brute_force(numbers):
    list_length = len(numbers)
    longest_length = 0

    for starting_index in range(list_length):
        for ending_index in range(starting_index, list_length):
            # Determine the subarray to analyze
            sub_array = numbers[starting_index:ending_index + 1]
            sub_array_length = len(sub_array)

            if sub_array_length > longest_length:
                is_increasing = True
                is_decreasing = True

                # Check if the sub_array is strictly increasing
                for index in range(1, sub_array_length):
                    if sub_array[index] <= sub_array[index - 1]:
                        is_increasing = False
                        break

                # Check if the sub_array is strictly decreasing
                for index in range(1, sub_array_length):
                    if sub_array[index] >= sub_array[index - 1]:
                        is_decreasing = False
                        break

                # Record the current longest length if applicable
                if is_increasing or is_decreasing:
                    longest_length = sub_array_length

    return longest_length

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach iterates through all possible subarrays of the input array of size n. For each starting position, it considers subarrays of length 1 up to n. This means that for each of the n possible starting positions, we potentially iterate up to n times to check if the subarray is strictly increasing or decreasing. Therefore, the total number of operations grows proportionally to n multiplied by n, which is n². Thus, the time complexity is O(n²).

Space Complexity

O(1) – The brute force approach described only uses a few variables to keep track of the current subarray being examined and the maximum length found so far. No auxiliary data structures like lists or hash maps are created. Therefore, the space required remains constant regardless of the size of the input array (N), resulting in O(1) space complexity.

Optimal Solution

Approach

The most efficient way to find the longest increasing or decreasing section is to look at the input in one go. We keep track of the current increasing and decreasing lengths and update the longest one we've seen so far. This way, we don't need to re-check parts of the input.

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

Start by assuming the longest section we've found so far has a length of one (just the first element).
Keep track of two counters: one to count elements in an increasing order and another to count those in a decreasing order.
Go through each element, comparing it to the one before it.
If the current element is bigger than the previous, increase the 'increasing' counter by one. Reset the 'decreasing' counter to one, since the decreasing sequence is broken.
If the current element is smaller than the previous, increase the 'decreasing' counter by one. Reset the 'increasing' counter to one, since the increasing sequence is broken.
If the current element is the same as the previous, reset both 'increasing' and 'decreasing' counters to one, effectively starting new subsequences.
After each comparison, update the longest length found so far with the maximum of the longest length, the increasing counter and the decreasing counter.
At the end, the longest length we've tracked is the length of the longest strictly increasing or strictly decreasing section.

Code Implementation

def find_longest_subarray(input_array):
    array_length = len(input_array)
    if array_length == 0:
        return 0

    longest_subarray_length = 1
    increasing_count = 1
    decreasing_count = 1

    for i in range(1, array_length):
        if input_array[i] > input_array[i - 1]:
            # Increasing sequence continues
            increasing_count += 1

            decreasing_count = 1

        elif input_array[i] < input_array[i - 1]:
            # Decreasing sequence continues
            decreasing_count += 1
            # Reset the increasing_count
            increasing_count = 1

        else:
            # Reset both counts if elements are equal
            increasing_count = 1

            decreasing_count = 1

        # Update the longest length found so far
        longest_subarray_length = max(
            longest_subarray_length,
            increasing_count,
            decreasing_count
        )

    return longest_subarray_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array once. For each element in the array of size n, it performs a constant number of comparisons (with the previous element) and updates counters. The cost of the algorithm is directly proportional to the number of elements in the array, resulting in n operations. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses a fixed number of variables: longest length, increasing counter, and decreasing counter. The space required by these variables does not depend on the input size N. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 as the length of the longest subarray in such cases is zero; handle null arrays gracefully to prevent NullPointerExceptions.
Array with a single element	Return 1, as a single element array is trivially both strictly increasing and strictly decreasing.
Array with two identical elements	Return 1, as neither an increasing nor decreasing subarray of length 2 exists.
Array with many consecutive identical elements	The algorithm should correctly reset the increasing/decreasing subarray length when encountering such sequences.
Array with integer overflow issues (very large numbers)	Use appropriate data types (e.g., long) to prevent integer overflow when comparing elements.
Array where the longest strictly increasing and strictly decreasing subarrays have the same length	The algorithm should return the correct length regardless of whether increasing or decreasing sequence is first.
Input array is very large, leading to memory constraints	The solution should be optimized for space complexity, ideally using O(1) extra space by iterating through array and tracking lengths instead of storing subarrays.
Array with alternating increasing and decreasing sequences	The algorithm should correctly handle the transition between increasing and decreasing sequences and accurately track the longest one.