#3105

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Longest Strictly Increasing or Strictly Decreasing Subarray

Find the longest subarray in a given array that is either strictly increasing or strictly decreasing.

Problem Statement

Given an array of integers nums, return the length of the longest subarray that is either strictly increasing or strictly decreasing.

A strictly increasing subarray is one where each element is greater than the previous one. Similarly, a strictly decreasing subarray is one where each element is smaller than the previous one.

Examples

Example 1

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

Output: 2

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

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

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

Solution Approach

Iterate and Track Sequences

To solve this problem, iterate through the array while tracking the current length of increasing and decreasing sequences. Every time the sequence changes direction (from increasing to decreasing or vice versa), reset the corresponding counter and check for the maximum length.

Use Two Counters

Use two counters: one for the length of the current increasing subarray and one for the decreasing subarray. Reset the counter whenever the subarray does not follow the desired strictly increasing or decreasing order.

Track Maximum Length

As you iterate through the array, update the maximum length encountered so far whenever the sequence continues increasing or decreasing. Ensure that the maximum value is correctly returned at the end.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity is O(n) because we only need to iterate through the array once, and the space complexity is O(1) as we are only using a few variables to track the current sequence lengths.

What Interviewers Usually Probe

Can the candidate efficiently track and compare sequence lengths during iteration?
Does the candidate correctly identify when to reset sequence tracking?
How well does the candidate handle edge cases, such as arrays with all equal elements?

Common Pitfalls or Variants

Common pitfalls

Failing to track both increasing and decreasing sequences separately.
Incorrectly updating the maximum length during iteration.
Not resetting sequence lengths at the right points when the array changes direction.

Follow-up variants

What if the array contains only one element?
How would the solution change if we had to return the subarray itself rather than just the length?
Can this problem be solved with dynamic programming, and what would be the trade-off?

FAQ

What is the primary pattern for solving the Longest Strictly Increasing or Strictly Decreasing Subarray problem?

The primary pattern is an array-driven solution that involves scanning through the array and tracking strictly increasing and decreasing subarrays.

What is the time complexity of the Longest Strictly Increasing or Strictly Decreasing Subarray problem?

The time complexity is O(n), where n is the length of the array, as we only need to iterate through it once.

How do we handle equal consecutive elements in the array?

Equal consecutive elements break both increasing and decreasing sequences, so the current sequence length must be reset whenever they are encountered.

What are common edge cases for the Longest Strictly Increasing or Strictly Decreasing Subarray problem?

Edge cases include arrays with all equal elements, arrays of length 1, and arrays that are already strictly increasing or decreasing.

What would be a more efficient solution if space complexity were not a constraint?

If space complexity were not a constraint, a dynamic programming approach could be used, but it would increase the space complexity to O(n).

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def longestMonotonicSubarray(self, nums: List[int]) -> int:
        ans = t = 1
        for i, x in enumerate(nums[1:]):
            if nums[i] < x:
                t += 1
                ans = max(ans, t)
            else:
                t = 1
        t = 1
        for i, x in enumerate(nums[1:]):
            if nums[i] > x:
                t += 1
                ans = max(ans, t)
            else:
                t = 1
        return ans

Continue Practicing

#3107 minimum operations to make median of array equal to k #3102 minimize manhattan distances #3108 minimum cost walk in weighted graph