LeetCode Problem 3105

Difficulty: 🟢 Easy
Topics: Array

Solution

LeetCode 3105, Longest Strictly Increasing or Strictly Decreasing Subarray

Problem Understanding

The problem gives us an integer array nums and asks us to find the length of the longest contiguous subarray that is either strictly increasing or strictly decreasing.

A subarray must consist of consecutive elements from the original array. This is important because we cannot skip elements. For example, in [1, 5, 2, 3], the sequence [1, 2, 3] is not a valid subarray because the elements are not contiguous.

A strictly increasing subarray means that every adjacent pair satisfies:

$a_i < a_{i+1}$

A strictly decreasing subarray means that every adjacent pair satisfies:

$a_i > a_{i+1}$

Equal neighboring values break both increasing and decreasing sequences because the comparison must be strict.

The input constraints are very small:

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 50

Since the array length is at most 50, even a quadratic brute force solution would technically pass. However, the problem is fundamentally a linear scan problem, and there is a much cleaner and more efficient approach.

Several edge cases are important:

• Arrays with all equal values, such as [3,3,3]
• Arrays of length 1
• Arrays that are entirely increasing
• Arrays that are entirely decreasing
• Arrays where the trend changes frequently
• Arrays containing repeated values in the middle of a sequence

These situations can easily introduce off by one errors if the increasing and decreasing counters are not updated carefully.

Approaches

Brute Force Approach

The brute force solution checks every possible subarray and determines whether it is strictly increasing or strictly decreasing.

For every starting index i, we try every ending index j. For each subarray nums[i:j+1], we scan through its elements and verify whether:

• every adjacent pair is increasing, or
• every adjacent pair is decreasing

If either condition holds, we update the maximum length.

This approach is correct because it explicitly examines all possible contiguous subarrays and validates each one according to the problem definition.

However, the time complexity becomes inefficient because there are:

• O(n^2) possible subarrays
• each validation may take O(n) time

This leads to an overall complexity of O(n^3).

Even though the constraints are small enough for this to pass, it is unnecessarily expensive.

Optimal Sliding Scan Approach

The key observation is that we do not need to repeatedly recheck old subarrays.

Instead, while scanning the array from left to right, we can continuously track:

• the current length of the strictly increasing run
• the current length of the strictly decreasing run

At each index:

• if nums[i] > nums[i-1], the increasing sequence extends by one
• if nums[i] < nums[i-1], the decreasing sequence extends by one
• if the values are equal, both sequences reset to length 1

This works because every valid monotonic subarray ending at position i depends only on the relationship between nums[i] and nums[i-1].

We never need to revisit earlier elements beyond the current run length.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every subarray explicitly
Optimal	O(n)	O(1)	Single pass while tracking increasing and decreasing streaks

Algorithm Walkthrough

1. Initialize three variables:

• increasing = 1
• decreasing = 1
• best = 1

Each individual element is itself a valid strictly increasing and strictly decreasing subarray of length 1. 2. Iterate through the array starting from index 1. 3. Compare the current element with the previous element. 4. If nums[i] > nums[i-1]:

• extend the increasing streak
• reset the decreasing streak

Specifically:

increasing += 1
decreasing = 1

5. If nums[i] < nums[i-1]:

• extend the decreasing streak
• reset the increasing streak

Specifically:

decreasing += 1
increasing = 1

6. If nums[i] == nums[i-1]:

• both streaks must reset because strict monotonicity is broken

Specifically:

increasing = 1
decreasing = 1

7. After updating the streaks, update the answer:

best = max(best, increasing, decreasing)

8. Continue until the end of the array.
9. Return best.

Why it works

The algorithm maintains an invariant:

• increasing always stores the length of the longest strictly increasing subarray ending at the current index
• decreasing always stores the length of the longest strictly decreasing subarray ending at the current index

Since every monotonic subarray ending at index i depends only on the previous adjacent comparison, updating these counters locally is sufficient. By tracking the maximum value seen during the scan, we guarantee that the final answer is the length of the longest valid monotonic subarray in the entire array.

Python Solution

from typing import List

class Solution:
    def longestMonotonicSubarray(self, nums: List[int]) -> int:
        increasing = 1
        decreasing = 1
        longest = 1

        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                increasing += 1
                decreasing = 1
            elif nums[i] < nums[i - 1]:
                decreasing += 1
                increasing = 1
            else:
                increasing = 1
                decreasing = 1

            longest = max(longest, increasing, decreasing)

        return longest

The implementation starts by initializing the increasing and decreasing streak lengths to 1. This is necessary because every single element forms a valid monotonic subarray.

The loop begins at index 1 because each comparison requires access to the previous element.

Inside the loop, the code compares adjacent elements:

• If the current value is larger, the increasing streak grows while the decreasing streak resets.
• If the current value is smaller, the decreasing streak grows while the increasing streak resets.
• If the values are equal, both streaks reset because strict monotonicity no longer holds.

After each update, the algorithm records the best streak length seen so far.

The solution uses constant extra memory and scans the array exactly once.

Go Solution

func longestMonotonicSubarray(nums []int) int {
	increasing := 1
	decreasing := 1
	longest := 1

	for i := 1; i < len(nums); i++ {
		if nums[i] > nums[i-1] {
			increasing++
			decreasing = 1
		} else if nums[i] < nums[i-1] {
			decreasing++
			increasing = 1
		} else {
			increasing = 1
			decreasing = 1
		}

		if increasing > longest {
			longest = increasing
		}

		if decreasing > longest {
			longest = decreasing
		}
	}

	return longest
}

The Go implementation follows the exact same logic as the Python version.

One minor difference is that Go does not provide a built in max() function for integers, so the code updates longest using explicit conditional checks.

The function assumes the input length is at least 1, which is guaranteed by the constraints.

Worked Examples

Example 1

Input:

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

i	nums[i-1]	nums[i]	Relation	increasing	decreasing	longest
Start	-	-	-	1	1	1
1	1	4	Increasing	2	1	2
2	4	3	Decreasing	1	2	2
3	3	3	Equal	1	1	2
4	3	2	Decreasing	1	2	2

Final answer:

2

Example 2

Input:

nums = [3,3,3,3]

i	nums[i-1]	nums[i]	Relation	increasing	decreasing	longest
Start	-	-	-	1	1	1
1	3	3	Equal	1	1	1
2	3	3	Equal	1	1	1
3	3	3	Equal	1	1	1

Final answer:

1

Example 3

Input:

nums = [3,2,1]

i	nums[i-1]	nums[i]	Relation	increasing	decreasing	longest
Start	-	-	-	1	1	1
1	3	2	Decreasing	1	2	2
2	2	1	Decreasing	1	3	3

Final answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The array is scanned once
Space	O(1)	Only a few integer variables are used

The algorithm performs a constant amount of work for each element in the array. No auxiliary data structures proportional to input size are required, so the extra memory usage remains constant.

Test Cases

from typing import List

class Solution:
    def longestMonotonicSubarray(self, nums: List[int]) -> int:
        increasing = 1
        decreasing = 1
        longest = 1

        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                increasing += 1
                decreasing = 1
            elif nums[i] < nums[i - 1]:
                decreasing += 1
                increasing = 1
            else:
                increasing = 1
                decreasing = 1

            longest = max(longest, increasing, decreasing)

        return longest

solution = Solution()

assert solution.longestMonotonicSubarray([1, 4, 3, 3, 2]) == 2  # mixed trends
assert solution.longestMonotonicSubarray([3, 3, 3, 3]) == 1  # all equal
assert solution.longestMonotonicSubarray([3, 2, 1]) == 3  # fully decreasing
assert solution.longestMonotonicSubarray([1, 2, 3, 4]) == 4  # fully increasing
assert solution.longestMonotonicSubarray([5]) == 1  # single element
assert solution.longestMonotonicSubarray([1, 2, 2, 3]) == 2  # equality breaks streak
assert solution.longestMonotonicSubarray([5, 4, 3, 2, 1]) == 5  # long decreasing run
assert solution.longestMonotonicSubarray([1, 3, 2, 4, 3, 5]) == 2  # alternating trends
assert solution.longestMonotonicSubarray([1, 2, 3, 2, 1]) == 3  # increasing then decreasing
assert solution.longestMonotonicSubarray([10, 9, 8, 8, 7]) == 3  # equality resets decreasing streak

Test	Why
[1,4,3,3,2]	Validates mixed increasing and decreasing runs
[3,3,3,3]	Ensures equal values reset streaks
[3,2,1]	Tests fully decreasing array
[1,2,3,4]	Tests fully increasing array
[5]	Smallest possible input
[1,2,2,3]	Confirms equality breaks monotonicity
[5,4,3,2,1]	Tests long decreasing streak
[1,3,2,4,3,5]	Frequent trend changes
[1,2,3,2,1]	Checks transition between trends
[10,9,8,8,7]	Equality inside a decreasing sequence

Edge Cases

Arrays with All Equal Elements

An array such as [3,3,3,3] is an important edge case because equal adjacent values are neither strictly increasing nor strictly decreasing. A buggy implementation might accidentally allow equality as part of a monotonic run.

This implementation correctly resets both counters whenever two adjacent elements are equal, ensuring the longest valid subarray length becomes 1.

Single Element Arrays

When the input contains only one element, such as [5], there are no adjacent comparisons to make. However, a single element still counts as both a strictly increasing and strictly decreasing subarray of length 1.

The implementation handles this naturally because all counters are initialized to 1 and the loop never executes.

Trend Changes in the Middle

Arrays like [1,2,3,2,1] are tricky because the direction changes partway through the array.

A common bug is forgetting to reset the opposite counter when the direction changes. For example, when transitioning from increasing to decreasing, the increasing streak must reset immediately.

This implementation explicitly resets the unused streak during every comparison, preventing stale values from contaminating future calculations.