3105. Longest Strictly Increasing or Strictly Decreasing Subarray - Detailed Explanation
Problem Statement
Description:
Given an integer array nums, determine the length of the longest subarray (i.e. contiguous segment) that is strictly increasing or strictly decreasing. A subarray is strictly increasing if every element is greater than its previous one, and strictly decreasing if every element is smaller than its previous one.
Example 1:
- Input:
nums = [1, 3, 5, 4, 2] - Output:
3 - Explanation:
- The subarray
[1, 3, 5]is strictly increasing (length 3). - The subarray
[5, 4, 2]is strictly decreasing (length 3). - Both have maximum length 3.
- The subarray
Example 2:
- Input:
nums = [5, 4, 3, 2, 1, 2, 3, 4, 5] - Output:
5 - Explanation:
- The subarray
[5, 4, 3, 2, 1]is strictly decreasing (length 5). - The subarray
[1, 2, 3, 4, 5]is strictly increasing (length 5).
- The subarray
Constraints:
- 1 ≤ nums.length ≤ 10⁵
- -10⁹ ≤ nums[i] ≤ 10⁹
Intuition and Hints
-
Hint 1:
As you traverse the array, you can maintain a counter for a current strictly increasing subarray and another for a current strictly decreasing subarray. Whenever the trend changes (or an equality occurs), reset the corresponding counter. -
Hint 2:
You can either use a single-pass approach by updating two counters simultaneously or perform two separate passes—one for finding the longest strictly increasing subarray and one for the strictly decreasing subarray—and then take the maximum of the two.
Approaches
Approach 1: Single-Pass Scan (Concurrent Counters)
Explanation:
Iterate over the array while maintaining two counters:
- inc: Length of the current strictly increasing subarray.
- dec: Length of the current strictly decreasing subarray.
At each index:
- If
nums[i] > nums[i-1], then the increasing sequence continues (incrementinc) and resetdecto 1. - If
nums[i] < nums[i-1], then the decreasing sequence continues (incrementdec) and resetincto 1. - If
nums[i] == nums[i-1], reset both counters to 1 (as equality breaks both strictly increasing and strictly decreasing trends).
Keep track of the maximum value among both counters.
- Time Complexity: O(n) – a single pass over the array.
- Space Complexity: O(1) – constant extra space.
Python Code (Single-Pass Approach):
Java Code (Single-Pass Approach):
Approach 2: Two Separate Passes
Explanation:
Alternatively, you can compute the longest strictly increasing subarray in one pass and the longest strictly decreasing subarray in a separate pass. Finally, return the maximum of the two lengths.
-
Steps for Increasing:
Traverse the array, and for every index wherenums[i] > nums[i-1], increment a counter. Reset the counter when the trend breaks. -
Steps for Decreasing:
Similarly, traverse the array, and for every index wherenums[i] < nums[i-1], increment a counter. Reset when the trend breaks. -
Time Complexity: O(n) (each pass is O(n) and there are two passes).
-
Space Complexity: O(1).
Python Code (Two-Pass Approach):
Java Code (Two-Pass Approach):
Complexity Analysis
-
Single-Pass Approach:
- Time Complexity: O(n)
- Space Complexity: O(1)
-
Two-Pass Approach:
- Time Complexity: O(n) (each pass is O(n))
- Space Complexity: O(1)
Common Pitfalls & Edge Cases
- Edge Cases:
- An array with a single element should return 1.
- An array with all equal elements: since no pair is strictly increasing or strictly decreasing, the longest subarray in each case is of length 1.
- Pitfalls:
- Forgetting to reset counters when the trend changes or when equal elements are encountered.
- Not handling empty input arrays properly.
GET YOUR FREE
Coding Questions Catalog
