Longest Strictly Increasing or Strictly Decreasing Subarray - Solution & Explanation
Problem Statement
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] <= 50
Approach Overview
Problem Overview: You are given an integer array and need the length of the longest contiguous subarray that is either strictly increasing or strictly decreasing. Adjacent elements must follow the rule a[i] > a[i-1] for increasing or a[i] < a[i-1] for decreasing. Equal values break the streak and start a new subarray.
Approach 1: Two Pointers Approach (O(n) time, O(1) space)
This method treats increasing and decreasing segments as separate windows. Use two pointers to expand a window while the order remains strictly increasing or strictly decreasing. When the condition breaks (for example, nums[i] <= nums[i-1] for increasing), reset the window start and continue scanning. Track the maximum length across both types of segments. The array is traversed once, making this approach efficient and easy to reason about when working with contiguous patterns in array problems.
Approach 2: Single Pass with State Variables (O(n) time, O(1) space)
This approach keeps two running counters: one for the current strictly increasing length and one for the strictly decreasing length. While iterating through the array, update these counters based on the comparison between nums[i] and nums[i-1]. If the current value is greater, increment the increasing counter and reset the decreasing counter; if smaller, do the opposite. If equal, reset both counters to 1. Track the global maximum during the scan. This technique is essentially a lightweight state machine and is common in linear scans over array problems that detect ordered segments.
Recommended for interviews: The single-pass state variable solution is typically what interviewers expect. It shows that you can detect patterns while scanning the array once and maintain minimal state. The two pointers method still demonstrates solid reasoning about contiguous windows and aligns well with problems that resemble two pointers or window-style traversal.
Approach 1: Two Pointers Approach
This 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.
Complexity
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.
Approach 2: Single Pass with State Variables
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.
Complexity
Time Complexity: O(n), linear pass over array elements.
Space Complexity: O(1), constant space usage due to state variables.
Approach 3: Two Passes
We first perform a pass to find the length of the longest strictly increasing subarray, and update the answer. Then we perform another pass to find the length of the longest strictly decreasing subarray, and update the answer again.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| 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. |
| Two Passes | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers | O(n) | O(1) | When you prefer explicit window boundaries while scanning increasing or decreasing segments |
| Single Pass with State Variables | O(n) | O(1) | Best general solution for interviews and competitive programming with minimal logic |
Video Solution
Longest Strictly Increasing or Strictly Decreasing Subarray - Leetcode 3105 - Python • NeetCodeIO • 7,855 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Longest Strictly Increasing or Strictly Decreasing Subarray easy or hard?
Longest Strictly Increasing or Strictly Decreasing Subarray Python/Java solution
How to solve Longest Strictly Increasing or Strictly Decreasing Subarray in O(n)?
What is the best approach for Longest Strictly Increasing or Strictly Decreasing Subarray?
Is Longest Strictly Increasing or Strictly Decreasing Subarray asked at Google/Amazon/Meta?
What data structure is used in Longest Strictly Increasing or Strictly Decreasing Subarray?
What is the time complexity of Longest Strictly Increasing or Strictly Decreasing Subarray?
Ready to solve this problem?
Practice Longest Strictly Increasing or Strictly Decreasing Subarray with our built-in code editor and test cases.
Practice on FleetCode