We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Strictly Increasing or Strictly Decreasing Subarray

Number: 3372

Difficulty: Easy

Paid? No

Companies: Yandex, Bloomberg, Meta, Microsoft, Amazon, Larsen & Toubro

Problem Description

Given an array of integers, find the length of the longest contiguous subarray that is either strictly increasing or strictly decreasing. A strictly increasing subarray means every subsequent element is larger than its previous element, and a strictly decreasing subarray means every subsequent element is smaller than its previous element.

Key Insights

  • The problem focuses on contiguous segments (subarrays), not subsequences.
  • Both strictly increasing and strictly decreasing patterns need to be tracked simultaneously.
  • A single pass through the array suffices by maintaining two counters: one for increasing sequences and one for decreasing sequences.
  • When the current element does not continue the strict order (increasing or decreasing), the respective counter resets to 1.
  • The maximum length seen while iterating is the answer.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the array, as we traverse the array once. Space Complexity: O(1) - only a few extra integer variables are used.

Solution

The solution involves a single traversal of the array. Two counters, "increasing" and "decreasing", are used to maintain the current lengths of strictly increasing and strictly decreasing subarrays, respectively. For each element starting from the second one, check if it is greater than the previous element; if yes, increment the increasing counter, otherwise reset it to 1. Similarly, check if the element is less than the previous element to update the decreasing counter. Throughout the traversal, update the maximum length found among both counters. The data structures used are simple integer variables, and the approach is iterative. This method ensures efficient processing with O(n) time and O(1) additional space.

Code Solutions

# Python solution for computing the longest subarray
def longest_subarray(nums):
    # Edge case: if array is empty, return 0
    if not nums:
        return 0
        
    n = len(nums)
    max_length = 1  # Minimum subarray length is 1 (each element itself)
    increasing = 1  # Tracks length of current increasing subarray
    decreasing = 1  # Tracks length of current decreasing subarray

    # Iterate from the second element to the end of the array
    for i in range(1, n):
        # Check if the current element is strictly greater than the previous element
        if nums[i] > nums[i - 1]:
            increasing += 1
        else:
            increasing = 1  # Reset if not strictly increasing

        # Check if the current element is strictly less than the previous element
        if nums[i] < nums[i - 1]:
            decreasing += 1
        else:
            decreasing = 1  # Reset if not strictly decreasing

        # Update the maximum subarray length found so far
        max_length = max(max_length, increasing, decreasing)
    
    return max_length

# Example usage:
print(longest_subarray([1,4,3,3,2]))  # Expected output: 2
← Back to All Questions