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.

Description Hints 6 Solution Video 11:41

2863. Maximum Length of Semi-Decreasing Subarrays

Medium70.5% acceptance1 companyPremium elsewhere, free here

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 <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

First, solve the problem assuming nums contains distinct values.

Hint 2

Make a new array with each element being the pair (nums[i], i) for every i and call it num_ind.

Hint 3

Sort num_ind in decreasing order.

Hint 4

Iterate over num_ind and store a variable that represents the minimum index (i.e. min of num_ind[i].second) that has been iterated until now. Call it min_index

Hint 5

Now if you are currently on pair (nums[x], x), then ans = max(ans, min_index - x).

Hint 6

Now try to remove the first assumption.

11:41

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

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

Input

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

Input

[1,2,3,4]

Your code is saved on this device.Solution