Maximum Length of Semi-Decreasing Subarrays - Solution & Explanation

Problem Overview: You are given an integer array nums. A subarray is semi-decreasing if the first element of the subarray is strictly greater than the last element. The task is to return the maximum length of such a subarray.

The key observation: for any pair of indices i < j, the subarray nums[i..j] is valid when nums[i] > nums[j]. The problem becomes finding the largest distance between two indices that satisfy this condition.

Approach 1: Brute Force Scan (O(n²) time, O(1) space)

Check every possible subarray. For each starting index i, iterate j from i+1 to the end and verify whether nums[i] > nums[j]. If the condition holds, update the maximum length j - i + 1. This approach directly follows the definition of a semi-decreasing subarray and is useful for validating edge cases or small inputs. However, the nested loop leads to O(n²) time complexity, which becomes too slow for large arrays.

Approach 2: Hash Table + Sorting (O(n log n) time, O(n) space)

Sort the array values while keeping their original indices. While iterating through the sorted values, maintain the smallest index seen so far for larger elements. For a current value nums[j], you want the earliest index i such that nums[i] > nums[j]. Sorting groups numbers by value, which makes it easy to process larger elements first and store their indices in a hash table or auxiliary structure. Each step computes a candidate length j - i + 1. Sorting dominates the complexity at O(n log n), and additional storage requires O(n) space. This approach is intuitive if you are comfortable with sorting based transformations.

Approach 3: Monotonic Stack (O(n) time, O(n) space)

A more efficient strategy uses a decreasing stack of indices. Traverse the array from left to right and push an index onto the stack whenever it forms a strictly decreasing sequence of values. The stack now stores candidate starting points where the value is relatively large. Next, traverse the array from right to left. For each index j, repeatedly check the top of the stack while nums[stack.top()] > nums[j]. Each valid pair produces a subarray length j - stack.top() + 1, and the index is popped because any future j would only produce a shorter length. This technique relies on the same idea used in many monotonic stack problems and processes each index at most once, giving O(n) time.

Recommended for interviews: Start by describing the brute force idea to demonstrate understanding of the condition nums[i] > nums[j]. Then move to the monotonic stack optimization. Interviewers typically expect the O(n) solution because it shows familiarity with array scanning patterns and stack-based optimizations.