Vultr DocsLatest Content

Longest Strictly Increasing or Strictly Decreasing Subarray

Updated on 05 June, 2025
Longest Strictly Increasing or Strictly Decreasing Subarray header image

Problem Statement

Given an array of integers nums, your task is to determine the length of the longest subarray where the numbers are either in strictly increasing order or strictly decreasing order. A strictly increasing or decreasing subarray must have elements where each subsequent element is respectively greater or less than its predecessor. The challenge lies in identifying the longest subsequence where such a condition holds true without interruptions.

Examples

Example 1

Input:

nums = [1,4,3,3,2]

Output:

2

Explanation:

The strictly increasing subarrays of `nums` are `[1]`, `[2]`, `[3]`, `[3]`, `[4]`, and `[1,4]`.

The strictly decreasing subarrays of `nums` are `[1]`, `[2]`, `[3]`, `[3]`, `[4]`, `[3,2]`, and `[4,3]`.

Hence, we return `2`.

Example 2

Input:

nums = [3,3,3,3]

Output:

1

Explanation:

The strictly increasing subarrays of `nums` are `[3]`, `[3]`, `[3]`, and `[3]`.

The strictly decreasing subarrays of `nums` are `[3]`, `[3]`, `[3]`, and `[3]`.

Hence, we return `1`.

Example 3

Input:

nums = [3,2,1]

Output:

3

Explanation:

The strictly increasing subarrays of `nums` are `[3]`, `[2]`, and `[1]`.

The strictly decreasing subarrays of `nums` are `[3]`, `[2]`, `[1]`, `[3,2]`, `[2,1]`, and `[3,2,1]`.

Hence, we return `3`.

Constraints

  • 1 <= nums.length <= 50
  • 1 <= nums[i] <= 50

Approach and Intuition

The aim is to find the longest subarray with strictly increasing or strictly decreasing values from a given array of integers. To achieve this, one needs to track the lengths of such subarrays as the array is traversed.

Key Steps:

  1. Initialize two variables, max_len_incr and max_len_decr, to hold the max lengths of strictly increasing and decreasing subarrays found during the traversal.
  2. Initialize another two variables, current_incr and current_decr, to hold the ongoing lengths of the current strictly increasing and decreasing subarrays.
  3. Loop through the array nums from the second element:
    • Compare the current element with the previous element:
      • If it's greater, update current_incr (increment by 1), and reset current_decr to 1 (as the sequence breaks).
      • If it's lesser, update current_decr (increment by 1), and reset current_incr to 1 (since the sequence breaks).
      • If neither condition is met (elements are equal), reset both current_incr and current_decr to 1.
    • Update max_len_incr and max_len_decr accordingly if current_incr or current_decr exceeds their values.
  4. The result is the maximum value between max_len_incr and max_len_decr, which gives the longest strictly monotonic subarray length.

Example Walk-throughs:

  • Example 1: nums = [1,4,3,3,2]

    • As you move from 1 to 4, current_incr increases.
    • From 4 to 3, the sequence starts to decrease leading to a swap from an increasing to a decreasing pattern.
    • This pattern resets, and by the end, the longest strictly increasing or decreasing subarray has a length of 2.

  • Example 2: nums = [3,3,3,3]

    • There are no increasing or decreasing trends beyond single elements due to all elements being the same. Thus, the longest length is 1.

  • Example 3: nums = [3,2,1]

    • A strictly decreasing pattern from start to end, yielding the full array length 3 as the result.

By approaching this problem systematically, iterating through the array while monitoring increasing and decreasing sequences, we can efficiently find the longest subarray that meets the criteria.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    int longestMonotoneSubarray(vector<int>& array) {
        int increase = 1, decrease = 1;
        int maxLen = 1;
    
        for (int i = 0; i < array.size() - 1; i++) {
            if (array[i + 1] > array[i]) {
                increase++;
                decrease = 1;
            } else if (array[i + 1] < array[i]) {
                decrease++;
                increase = 1;
            } else {
                increase = 1;
                decrease = 1;
            }
            maxLen = max(maxLen, max(increase, decrease));
        }
        return maxLen;
    }
};

This C++ code defines a solution to find the length of the longest strictly increasing or strictly decreasing subarray within a given array of integers.

  • The class Solution includes the function longestMonotoneSubarray which takes a vector<int>& representing the array.

  • Two main variables, increase and decrease, track the lengths of the current increasing and decreasing subarrays, respectively.

  • Another variable, maxLen, keeps record of the maximum length found during the traversal of the array.

  • Iterate through the array using a for loop. For each pair of adjacent elements:

    • If the next element is greater than the current element, increment the increase counter and reset the decrease counter.

    • If the next element is less than the current element, increment the decrease counter and reset the increase counter.

    • If elements are equal or if it's the first pair of elements being compared, reset both increase and decrease to 1.

    • Update maxLen by taking the maximum value among maxLen, increase, and decrease.

  • At the end of the array traversal, return maxLen which will be the length of the longest subarray that is either strictly increasing or strictly decreasing.

This approach ensures efficiency by only requiring a single pass through the input array, with a time complexity of O(n), where n is the number of elements in the array. The additional space complexity is O(1), using only a few auxiliary variables for tracking purposes.

java 
class Solution {
    
    public int findLongestMonotoneSequence(int[] data) {
        int increasingSeqLength = 1, decreasingSeqLength = 1;
        int maxSeqLength = 1;
    
        for (int i = 0; i < data.length - 1; i++) {
            if (data[i + 1] > data[i]) {
                increasingSeqLength++;
                decreasingSeqLength = 1; 
            } else if (data[i + 1] < data[i]) {
                decreasingSeqLength++;
                increasingSeqLength = 1;
            } else {
                increasingSeqLength = 1;
                decreasingSeqLength = 1;
            }
    
            maxSeqLength = Math.max(maxSeqLength, Math.max(increasingSeqLength, decreasingSeqLength));
        }
        return maxSeqLength;
    }
}

This Java solution aims to find the length of the longest strictly increasing or strictly decreasing subarray within a given array. The approach involves tracking the length of the current increasing and decreasing sequences simultaneously, and updating the maximum length found accordingly.

  • Start by initializing increasingSeqLength and decreasingSeqLength to 1, assuming the smallest possible subarray has a length of 1.
  • Initialize maxSeqLength to 1, which will store the length of the longest monotone subarray found.
  • Traverse the input array from the first to the penultimate element, using a for loop. Comparisons between consecutive elements determine if the current sequence is increasing or decreasing.
  • If an element is greater than the previous one, increment the increasingSeqLength and reset decreasingSeqLength to 1 to start counting a new decreasing sequence.
  • If an element is less than the previous one, increment the decreasingSeqLength and reset increasingSeqLength to 1 for a new increasing sequence.
  • If elements are equal, reset both increasingSeqLength and decreasingSeqLength to 1.
  • At each iteration, compute the maximum sequence length by comparing maxSeqLength with both increasingSeqLength and decreasingSeqLength.
  • Finally, return maxSeqLength as the result, which represents the length of the longest monotone subarray found in the input array.

This method ensures efficient calculation with a time complexity of O(n), where n is the number of elements in the data array, as it requires just a single pass through the array.

python 
class Solution:
    def longestContinuousSegment(self, array: list[int]) -> int:
        increase_run = decrease_run = longest_run = 1
    
        for index in range(1, len(array)):
            if array[index] > array[index - 1]:
                increase_run += 1
                decrease_run = 1
            elif array[index] < array[index - 1]:
                decrease_run += 1
                increase_run = 1
            else:
                increase_run = decrease_run = 1
    
            longest_run = max(longest_run, increase_run, decrease_run)
    
        return longest_run

In this Python solution, you determine the length of the longest strictly increasing or strictly decreasing subarray within a list of integers. This problem can effectively highlight trends within sequences, useful in data analysis contexts.

The logic operates as follows:

  • Initiate counters for increasing (increase_run) and decreasing sequences (decrease_run), and also for the longest sequence found so far (longest_run), each set to 1.

  • Iterate over each element in the array starting from the second element.

    • Compare the current element to the previous one.

      • If the current element is greater, it indicates an increasing sequence; increment increase_run and reset decrease_run.

      • If it's lesser, it indicates a decreasing sequence; increment decrease_run and reset increase_run.

      • If neither, reset both runs as the sequence has neither strictly increased nor decreased at this point.

    • Update longest_run to hold the maximum value among itself, increase_run, and decrease_run.

  • Return the value of longest_run as the length of the longest continual segment of either strictly increasing or decreasing numbers.

This approach effectively tracks trends with a time complexity of O(n) due to a single pass through the array, making it optimal for larger datasets. The implementation leverages direct comparisons and simple arithmetic to maintain and update runs, resulting in an elegant and efficient solution for trend detection.

Comments