Maximum Length of Semi-Decreasing Subarrays

Maximum Length of Semi-Decreasing Subarrays

What is this problem about?

The Maximum Length of Semi-Decreasing Subarrays coding problem asks you to find the longest contiguous subarray where the first element is strictly greater than the last element — in other words, a subarray that "starts higher than it ends." This is called semi-decreasing because it only constrains the endpoints, not every pair of adjacent elements.

Why is this asked in interviews?

Google includes this problem to test candidates' understanding of monotonic stacks applied in a non-standard way. The brute-force O(n²) approach is trivial to state; the challenge lies in achieving O(n log n) or O(n) using a stack. Candidates who can identify that the relevant left endpoints form a decreasing stack, and the relevant right endpoints form an increasing stack, demonstrate strong algorithmic intuition.

Algorithmic pattern used

The solution uses a monotonic stack approach.

1. Build a decreasing stack of potential left endpoints: iterate left to right, push index i if nums[i] is greater than the current stack top's value (i.e., keep only indices whose values form a strictly decreasing sequence from left to right as potential left endpoints for maximum reach).
2. Scan from right to left with the right endpoint. For each right index j, pop from the stack while stack.top() > nums[j] — each such pop gives a valid subarray from the popped index to j, updating the max length.

This ensures each index is processed once: O(n) total.

Example explanation

Array: [3, 1, 4, 1, 5, 2]

• Left stack (decreasing values): Push index 0 (val=3). Index 1 (val=1) < 3, skip. Index 2 (val=4) > 3, push. Index 3 (val=1) < 4, skip. Index 4 (val=5) > 4, push. Index 5 (val=2) < 5, skip.
• Stack (by value): [3 at 0, 4 at 2, 5 at 4].
• Scan right to left: j=5 (val=2). Pop while stack top > 2: pop idx 4 (val=5>2) → len=5-4+1? No, len = j - i + 1 = 5-4+1 = 2. Actually need first element > last: nums[4]=5 > nums[5]=2. Length = 2. Pop idx 2 (val=4>2) → len = 5-2+1=4. Pop idx 0 (val=3>2) → len = 5-0+1=6.
• Maximum length = 6.

Common mistakes candidates make

• Building the wrong type of monotonic stack: Using an increasing stack for left endpoints misses valid long subarrays.
• Not scanning right-to-left for right endpoints: Scanning left-to-right for right endpoints pairs incorrectly with the left stack.
• Computing length incorrectly: Length = j - i + 1 where i is the popped left index and j is the current right index.

Interview preparation tip

For the Array Monotonic Stack Sorting Stack interview pattern, remember that "semi-decreasing" constraints (start > end) are a monotonic stack classic. Build the left stack as strictly decreasing-values, then sweep right-to-left as the right pointer. This two-pass technique appears in many "longest subarray with endpoint constraint" problems.