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.
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 <= 501 <= nums[i] <= 50This approach involves using two pointers or variables to track the length of the current strictly increasing or decreasing subarray as we iterate through the list. We update a variable to keep track of the maximum length encountered. The idea is to compare each element with its previous one to determine whether it's part of an increasing or decreasing sequence.
The C implementation uses a loop to iterate over the array while maintaining two counters for increasing and decreasing sequences. The maximum of these lengths is tracked using 'maxLen'. The solution efficiently updates these counters as it inspects each pair of consecutive elements.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the array, since we are iterating through it once.
Space Complexity: O(1), as we are using a fixed amount of space regardless of input size.
This approach optimizes further by using a state system to record current sequence types (increasing or decreasing). A single loop maintains these states to update the subarray length dynamically. The idea is similar but consolidates the management of the sequence into a reduced number of operations during comparison.
The C implementation manages state variables 'isIncreasing' and 'isDecreasing' to track the current movement in the array without needing separate counters for increasing and decreasing directions. This reduces state management overhead.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), linear pass over array elements.
Space Complexity: O(1), constant space usage due to state variables.
| Approach | Complexity |
|---|---|
| Two Pointers Approach | Time Complexity: O(n), where n is the length of the array, since we are iterating through it once. |
| Single Pass with State Variables | Time Complexity: O(n), linear pass over array elements. |
Longest Strictly Increasing or Strictly Decreasing Subarray - Leetcode 3105 - Python • NeetCodeIO • 6,279 views views
Watch 9 more video solutions →Practice Longest Strictly Increasing or Strictly Decreasing Subarray with our built-in code editor and test cases.
Practice on FleetCode