LeetCode Problem 2863

Difficulty: 🟡 Medium
Topics: Array, Stack, Sorting, Monotonic Stack

Solution

LeetCode 2863 - Maximum Length of Semi-Decreasing Subarrays

Problem Understanding

The problem gives us an integer array nums and asks for the length of the longest contiguous subarray whose first element is strictly greater than its last element.

A subarray is any contiguous segment of the array. For a subarray nums[i...j] to be considered semi-decreasing, the following condition must hold:

$$nums[i] > nums[j]$$

Importantly, nothing else matters. The elements in between do not need to be sorted, decreasing, or follow any particular pattern. Only the first and last elements are relevant.

For example, in the subarray [61,58,63,59,64,60], the sequence fluctuates up and down, but it is still valid because the first element 61 is greater than the last element 60.

The task is therefore equivalent to finding the maximum distance (j - i + 1) such that:

$$i < j \quad \text{and} \quad nums[i] > nums[j]$$

If no such pair exists, we return 0.

The constraints are important:

• 1 <= nums.length <= 10^5
• Values can be as small as -10^9 and as large as 10^9

An array of size 10^5 immediately rules out quadratic algorithms. Any O(n^2) solution will time out. This strongly suggests that we need an O(n log n) or O(n) solution.

Several edge cases are important:

• Arrays that are strictly increasing, such as [1,2,3,4], should return 0.
• Arrays that are strictly decreasing should return the entire array length.
• Duplicate values require careful handling because the condition is strictly greater, not greater than or equal to.
• Very small arrays, especially length 1, cannot contain valid subarrays because a subarray must contain at least two elements to have distinct first and last positions.

Approaches

Brute Force Approach

The most direct solution is to check every possible subarray.

For every starting index i, we iterate through every ending index j > i. If nums[i] > nums[j], then the subarray nums[i...j] is semi-decreasing, and we update the maximum length.

This works because it explicitly examines every candidate subarray and verifies the condition exactly as defined.

However, there are O(n^2) possible subarrays. With n = 10^5, this becomes approximately 10^10 comparisons in the worst case, which is far too slow.

Optimal Approach

The key observation is that we only care about pairs of indices (i, j) where:

$$nums[i] > nums[j]$$

and we want to maximize:

$$j - i + 1$$

This resembles problems involving maximum width intervals and monotonic stacks.

We can preprocess candidate starting positions using a monotonic decreasing stack.

The idea is:

• Build a stack of indices whose values form a strictly decreasing sequence.
• These indices are the best candidates for the left endpoint because they contain progressively smaller minimum values.
• Then scan from right to left and try to match each right endpoint with the farthest valid left endpoint.

If nums[stack[-1]] > nums[j], then we found a valid semi-decreasing subarray.

Because the stack is monotonic, once a match is found, we can safely pop indices that can no longer produce a better answer later.

This gives an O(n) solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every possible subarray
Optimal	O(n)	O(n)	Uses a monotonic decreasing stack

Algorithm Walkthrough

1. Create an empty stack that will store indices.
2. Traverse the array from left to right.
3. For each index i, push it onto the stack only if:

• the stack is empty, or
• nums[i] is smaller than the value at the index currently on top of the stack.

This ensures the stack stores indices whose values are strictly decreasing. 4. The stack now represents candidate left boundaries for semi-decreasing subarrays. 5. Initialize answer = 0. 6. Traverse the array from right to left using index j. 7. While the stack is not empty and:

$$nums[stack[-1]] > nums[j]$$

we found a valid semi-decreasing subarray. 8. Compute its length:

$$j - stack[-1] + 1$$ 9. Update the maximum answer. 10. Pop the stack top after processing it.

This is safe because any future right endpoint will be farther left, producing a shorter subarray. 11. Continue until the scan finishes. 12. Return the final answer.

Why it works

The monotonic stack stores only indices that could potentially produce the longest valid subarray. If an earlier index has a larger or equal value than a later index, the later index is never better because it produces shorter subarrays.

During the right-to-left scan, once an index satisfies the condition for some j, using it again with a smaller future j would only decrease the length. Therefore it can be removed permanently.

This guarantees every index is pushed and popped at most once, producing a linear-time algorithm.

Python Solution

from typing import List

class Solution:
    def maxSubarrayLength(self, nums: List[int]) -> int:
        n = len(nums)

        # Monotonic decreasing stack of indices
        stack = []

        for i in range(n):
            if not stack or nums[i] < nums[stack[-1]]:
                stack.append(i)

        answer = 0

        # Traverse from right to left
        for j in range(n - 1, -1, -1):
            while stack and nums[stack[-1]] > nums[j]:
                answer = max(answer, j - stack[-1] + 1)
                stack.pop()

        return answer

The implementation begins by building a monotonic decreasing stack of indices. The stack only stores indices whose values are strictly smaller than all previous stored values.

For example, if the array is:

[7, 6, 5, 4, 3]

the stack becomes:

[0, 1, 2, 3, 4]

because each new value is smaller than the previous one.

However, for:

[7, 8, 6, 5]

the stack becomes:

[0, 2, 3]

because index 1 with value 8 is not useful. Index 0 already has a larger value and produces longer subarrays.

The second loop scans from right to left. For each right endpoint j, we repeatedly check whether the stack top satisfies:

nums[stack[-1]] > nums[j]

If it does, we update the answer and remove that index permanently.

Each index enters and leaves the stack at most once, which ensures linear complexity.

Go Solution

func maxSubarrayLength(nums []int) int {
	n := len(nums)

	stack := []int{}

	// Build monotonic decreasing stack
	for i := 0; i < n; i++ {
		if len(stack) == 0 || nums[i] < nums[stack[len(stack)-1]] {
			stack = append(stack, i)
		}
	}

	answer := 0

	// Traverse from right to left
	for j := n - 1; j >= 0; j-- {
		for len(stack) > 0 && nums[stack[len(stack)-1]] > nums[j] {
			length := j - stack[len(stack)-1] + 1

			if length > answer {
				answer = length
			}

			stack = stack[:len(stack)-1]
		}
	}

	return answer
}

The Go implementation follows exactly the same algorithm as the Python version.

The stack is implemented using a slice of integers. Pushing is done with append, and popping is done by reslicing:

stack = stack[:len(stack)-1]

Go integers safely handle the problem constraints because the largest possible subarray length is only 10^5.

Unlike Python, Go does not have built-in max functions for integers, so the code uses an explicit comparison before updating answer.

Worked Examples

Example 1

Input:

nums = [7,6,5,4,3,2,1,6,10,11]

Step 1: Build Monotonic Stack

Index	Value	Stack After Processing
0	7	[0]
1	6	[0,1]
2	5	[0,1,2]
3	4	[0,1,2,3]
4	3	[0,1,2,3,4]
5	2	[0,1,2,3,4,5]
6	1	[0,1,2,3,4,5,6]
7	6	unchanged
8	10	unchanged
9	11	unchanged

Final stack:

[0,1,2,3,4,5,6]

Step 2: Scan From Right to Left

j	nums[j]	Valid Pops	Best Length
9	11	none	0
8	10	none	0
7	6	pop 6	2
6	1	none	2
5	2	none	2
4	3	none	2
3	4	none	2
2	5	none	2
1	6	none	2
0	7	pop 5,4,3,2,1,0	8

Final answer:

8

Example 2

Input:

nums = [57,55,50,60,61,58,63,59,64,60,63]

Stack Construction

Index	Value	Stack
0	57	[0]
1	55	[0,1]
2	50	[0,1,2]
3	60	unchanged
4	61	unchanged
5	58	unchanged
6	63	unchanged
7	59	unchanged
8	64	unchanged
9	60	unchanged
10	63	unchanged

Final stack:

[0,1,2]

Right-to-Left Scan

At j = 9, value 60:

• 57 > 60 is false
• 55 > 60 is false
• 50 > 60 is false

At j = 7, value 59:

• 57 > 59 false
• 55 > 59 false
• 50 > 59 false

At j = 5, value 58:

• 57 > 58 false
• 55 > 58 false
• 50 > 58 false

At j = 1, value 55:

• 57 > 55 true
• length = 1 - 0 + 1 = 2

The best answer eventually becomes:

6

from subarray:

[61,58,63,59,64,60]

Example 3

Input:

nums = [1,2,3,4]

Stack Construction

Only index 0 enters the stack because all later values are larger.

stack = [0]

Right-to-Left Scan

For every j:

nums[0] > nums[j]

is never true.

Therefore:

answer = 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index is pushed and popped at most once
Space	O(n)	The stack may store up to all indices

The algorithm is linear because the monotonic stack guarantees that no index is processed more than twice, once when inserted and once when removed. This avoids the quadratic behavior of checking all subarrays individually.

Test Cases

from typing import List

class Solution:
    def maxSubarrayLength(self, nums: List[int]) -> int:
        n = len(nums)

        stack = []

        for i in range(n):
            if not stack or nums[i] < nums[stack[-1]]:
                stack.append(i)

        answer = 0

        for j in range(n - 1, -1, -1):
            while stack and nums[stack[-1]] > nums[j]:
                answer = max(answer, j - stack[-1] + 1)
                stack.pop()

        return answer

sol = Solution()

assert sol.maxSubarrayLength([7,6,5,4,3,2,1,6,10,11]) == 8
# example 1

assert sol.maxSubarrayLength([57,55,50,60,61,58,63,59,64,60,63]) == 6
# example 2

assert sol.maxSubarrayLength([1,2,3,4]) == 0
# strictly increasing array

assert sol.maxSubarrayLength([4,3,2,1]) == 4
# entire array is valid

assert sol.maxSubarrayLength([5]) == 0
# single element array

assert sol.maxSubarrayLength([5,5,5,5]) == 0
# equal values do not satisfy strict inequality

assert sol.maxSubarrayLength([10,1]) == 2
# smallest valid subarray

assert sol.maxSubarrayLength([1,10]) == 0
# two elements but invalid

assert sol.maxSubarrayLength([-1,-2,-3]) == 3
# negative numbers

assert sol.maxSubarrayLength([3,1,2]) == 3
# valid subarray spans entire array

assert sol.maxSubarrayLength([9,8,7,10,11,6]) == 6
# optimal subarray includes large middle values

assert sol.maxSubarrayLength([100,1,100,1,100,1]) == 6
# alternating highs and lows

Test Summary

Test	Why
[7,6,5,4,3,2,1,6,10,11]	Validates standard decreasing pattern
[57,55,50,60,61,58,63,59,64,60,63]	Validates mixed fluctuations
[1,2,3,4]	Ensures no valid subarray returns 0
[4,3,2,1]	Entire array should be selected
[5]	Smallest input size
[5,5,5,5]	Strict inequality handling
[10,1]	Smallest valid semi-decreasing subarray
[1,10]	Two-element invalid case
[-1,-2,-3]	Handles negative values correctly
[3,1,2]	Entire array valid despite middle fluctuations
[9,8,7,10,11,6]	Best subarray includes larger middle elements
[100,1,100,1,100,1]	Stress test for repeated patterns

Edge Cases

Strictly Increasing Arrays

An array like [1,2,3,4,5] is important because no valid semi-decreasing subarray exists. A careless implementation might incorrectly allow equal or increasing endpoints.

The algorithm handles this correctly because the condition:

nums[left] > nums[right]

never becomes true, so the answer remains 0.

Arrays With Duplicate Values

Arrays such as [5,5,5,5] can cause bugs if the implementation mistakenly uses >= instead of >.

The problem requires strict inequality. The implementation explicitly checks:

nums[stack[-1]] > nums[j]

so duplicates are correctly rejected.

Entire Array Is Valid

For arrays like [9,8,7,6], the optimal answer is the entire array length.

Some implementations accidentally stop early or only consider local decreases. This solution correctly computes:

4

because the leftmost index remains in the stack until matched with the farthest valid right endpoint.