Skip to main content
Talentd

Maximum Length of Semi-Decreasing Subarrays - Solution & Explanation

MediumPremiumFree on FleetCodeArrayStackSortingMonotonic Stack9 min readAsked at: Google
Practice this problem

Problem Statement

You are given an integer array nums.

Return the length of the longest semi-decreasing subarray of nums, and 0 if there are no such subarrays.

  • A subarray is a contiguous non-empty sequence of elements within an array.
  • A non-empty array is semi-decreasing if its first element is strictly greater than its last element.

 

Example 1:

Input: nums = [7,6,5,4,3,2,1,6,10,11]
Output: 8
Explanation: Take the subarray [7,6,5,4,3,2,1,6].
The first element is 7 and the last one is 6 so the condition is met.
Hence, the answer would be the length of the subarray or 8.
It can be shown that there aren't any subarrays with the given condition with a length greater than 8.

Example 2:

Input: nums = [57,55,50,60,61,58,63,59,64,60,63]
Output: 6
Explanation: Take the subarray [61,58,63,59,64,60].
The first element is 61 and the last one is 60 so the condition is met.
Hence, the answer would be the length of the subarray or 6.
It can be shown that there aren't any subarrays with the given condition with a length greater than 6.

Example 3:

Input: nums = [1,2,3,4]
Output: 0
Explanation: Since there are no semi-decreasing subarrays in the given array, the answer is 0.

 

Constraints:

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109

Approach Overview

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.

Solution

The problem is essentially finding the maximum length of the inverse pairs. We can use a hash table d to record the index i corresponding to each number x in the array.

Next, we traverse the keys of the hash table in descending order of the numbers. We maintain a number k to keep track of the smallest index that has appeared so far. For the current number x, we can get a maximum inverse pair length of d[x][|d[x]|-1]-k + 1, where |d[x]| represents the length of the array d[x], i.e., the number of times the number x appears in the original array. We update the answer accordingly. Then, we update k to d[x][0], which is the index where the number x first appears in the original array. We continue to traverse the keys of the hash table until all keys are traversed.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ScanO(n²)O(1)Useful for understanding the problem or validating small inputs
Hash Table + SortingO(n log n)O(n)Clear logic using sorted values and index tracking
Monotonic StackO(n)O(n)Optimal approach for large arrays and typical interview expectations

Video Solution

leetcode 2863 [Google Interview Q]. Maximum Length of Semi-Decreasing Subarrays - monotonic stack • Code-Yao • 1,448 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Maximum Length of Semi-Decreasing Subarrays easy or hard?
The problem is rated Medium because the brute force idea is simple but the optimal solution requires recognizing a monotonic stack pattern. Candidates who are comfortable with stack-based array scans usually solve it quickly, while others may initially attempt slower O(n²) solutions.
Maximum Length of Semi-Decreasing Subarrays Python/Java solution
Implementations typically iterate through the array while maintaining candidate indices in a stack or processing sorted value-index pairs. The algorithm works similarly across languages such as Python, Java, C++, Go, and TypeScript because it relies on simple array traversal and stack operations.
How to solve Maximum Length of Semi-Decreasing Subarrays in O(n)?
Use a monotonic decreasing stack of indices. Traverse from left to right and push indices when their values create a decreasing sequence. Then traverse from right to left and compare the current value with indices stored in the stack. Whenever nums[i] > nums[j], compute the length j - i + 1 and pop the index. Each element is processed once, giving O(n) complexity.
What is the best approach for Maximum Length of Semi-Decreasing Subarrays?
The most efficient approach uses a monotonic decreasing stack. First build a stack of candidate starting indices where values strictly decrease. Then scan the array from right to left and match each element with larger values stored in the stack. This method processes each index at most once, resulting in O(n) time and O(n) space.
Is Maximum Length of Semi-Decreasing Subarrays asked at Google/Amazon/Meta?
Problems involving monotonic stacks and maximum distance between indices appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, the pattern of maintaining candidate indices and scanning from the opposite direction is a common interview technique.
What data structure is used in Maximum Length of Semi-Decreasing Subarrays?
Common solutions use arrays, sorting utilities, and a monotonic stack. The stack stores indices that represent potential starting points of semi-decreasing subarrays. Sorting-based approaches may also use hash tables or auxiliary arrays to track index positions.
What is the time complexity of Maximum Length of Semi-Decreasing Subarrays?
The brute force method takes O(n²) time because it checks every pair of indices. A sorting-based method reduces the complexity to O(n log n). The optimal monotonic stack solution runs in O(n) time with O(n) additional space.

Ready to solve this problem?

Practice Maximum Length of Semi-Decreasing Subarrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays