algoadvance

You are given an array arr of integers. You need to find the length of the longest subarray that is either strictly increasing or strictly decreasing.

Clarifying Questions:

1. Do the elements of the subarray need to be contiguous?
   • Yes, the subarray should be contiguous.
2. What is the range of values for the elements in the array?
   • The elements could be any integer, positive, negative, or zero.
3. What should be returned if the array is empty or contains one element?
   • If the array is empty, the length should be 0. If the array contains one element, the length should be 1.
4. Can the array contain duplicate elements?
   • Yes, the array can contain duplicate elements, but strictly increasing or decreasing subarrays cannot have consecutive duplicate elements.

Strategy:

To solve this problem, we need to iterate through the array and keep track of the lengths of the currently observed strictly increasing or strictly decreasing subarrays. We can maintain a few state variables:

1. curr_inc_length for the length of the current strictly increasing subarray.
2. curr_dec_length for the length of the current strictly decreasing subarray.
3. max_length to store the maximum length observed so far of either type of subarray.

We will iterate through the array from the second element and for each element, we will:

• Check if it is greater than the previous element (i.e., increasing).
  • If increasing, increment curr_inc_length, reset curr_dec_length to 1.
• Check if it is smaller than the previous element (i.e., decreasing).
  • If decreasing, increment curr_dec_length, reset curr_inc_length to 1.
• If neither, reset both curr_inc_length and curr_dec_length to 1.
• Update max_length accordingly.

Code:

def longest_strictly_inc_or_dec_subarray(arr):
    if not arr:
        return 0
    if len(arr) == 1:
        return 1

    curr_inc_length = 1
    curr_dec_length = 1
    max_length = 1

    for i in range(1, arr.length):
        if arr[i] > arr[i - 1]:
            curr_inc_length += 1
            curr_dec_length = 1
        elif arr[i] < arr[i - 1]:
            curr_dec_length += 1
            curr_inc_length = 1
        else:
            curr_inc_length = 1
            curr_dec_length = 1

        max_length = max(max_length, curr_inc_length, curr_dec_length)

    return max_length

# Example usage:
# arr = [1, 2, 3, 4, 1, 0, -1, -2]
# print(longest_strictly_inc_or_dec_subarray(arr))  # Output: 4

Time Complexity:

• Time Complexity: O(n), where n is the number of elements in the array. We only need one pass through the array to compute the longest subarray length.
• Space Complexity: O(1), as we are using a fixed amount of extra space regardless of the input size.

This solution efficiently finds the length of the longest strictly increasing or strictly decreasing subarray using a single traversal of the input array and constant additional space.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?