3105. Longest Strictly Increasing or Strictly Decreasing Subarray - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

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.

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).

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 (increment inc) and reset dec to 1.
If nums[i] < nums[i-1], then the decreasing sequence continues (increment dec) and reset inc to 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):

Python3

. . . .

Java Code (Single-Pass Approach):

Java

. . . .

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 where nums[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 where nums[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):

Python3

. . . .

Java Code (Two-Pass Approach):

Java

. . . .

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.

TAGS

leetcode

CONTRIBUTOR

Design Gurus Team