Problem Description

You are given an integer array nums.

Your task is to find the length of the longest semi-decreasing subarray in nums. If no such subarray exists, return 0.

Key definitions:

• A subarray is a contiguous sequence of elements from the array (cannot be empty)
• A semi-decreasing subarray has its first element strictly greater than its last element

For example:

• If we have subarray [5, 3, 2], it's semi-decreasing because 5 > 2 (first > last)
• If we have subarray [3, 4, 1], it's semi-decreasing because 3 > 1 (first > last)
• If we have subarray [2, 2], it's NOT semi-decreasing because 2 is not strictly greater than 2
• A single element [5] is NOT semi-decreasing (needs at least 2 elements to compare first and last)

The goal is to find the maximum possible length among all semi-decreasing subarrays in the given array.

Intuition

The key insight is that for a semi-decreasing subarray, we need the first element to be strictly greater than the last element. This means we're looking for pairs of indices (i, j) where i < j and nums[i] > nums[j].

To maximize the length of such a subarray, we want to maximize j - i + 1. This suggests we should try to find pairs where i is as small as possible and j is as large as possible, while maintaining the condition nums[i] > nums[j].

Let's think about this differently: for each value in the array, we can track all positions where it appears. If we process values from largest to smallest, we can maintain the following strategy:

1. For a larger value, we want to use its leftmost occurrence as the starting point of a potential subarray
2. For a smaller value, we want to use its rightmost occurrence as the ending point of a potential subarray

Why does this work? When we process values in descending order:

• We first encounter larger values that can serve as starting points
• As we move to smaller values, they can potentially be endpoints for subarrays starting with any previously seen larger value
• By keeping track of the minimum starting index seen so far (k), we can calculate the maximum subarray length ending at the current value

For example, if we have value 10 at index 2 and value 5 at index 7, the subarray from index 2 to 7 has length 7 - 2 + 1 = 6, and it's semi-decreasing because 10 > 5.

This approach transforms the problem from checking all possible subarrays (which would be O(n²)) to a more efficient solution using sorting and tracking minimum indices.

Learn more about Stack, Sorting and Monotonic Stack patterns.

Solution Approach

Let's walk through the implementation step by step:

Step 1: Build a Hash Table

d = defaultdict(list)
for i, x in enumerate(nums):
    d[x].append(i)

We create a hash table d where each key is a value from the array, and the corresponding value is a list of all indices where that number appears. For example, if nums = [3, 1, 3, 2, 1], then d would be {3: [0, 2], 1: [1, 4], 2: [3]}.

Step 2: Sort and Process Values in Descending Order

ans, k = 0, inf
for x in sorted(d, reverse=True):

We initialize:

• ans to track the maximum subarray length found
• k to inf (infinity) to track the minimum starting index seen so far

We then iterate through the unique values in descending order. This ensures we process larger values before smaller ones.

Step 3: Calculate Maximum Length for Current Value

ans = max(ans, d[x][-1] - k + 1)

For the current value x:

• d[x][-1] gives us the rightmost (last) occurrence of x
• This position can serve as the ending point of a semi-decreasing subarray
• The subarray would start at index k (the minimum index from all larger values seen so far)
• The length would be d[x][-1] - k + 1
• We update ans if this length is larger

Step 4: Update Minimum Starting Index

k = min(k, d[x][0])

After processing value x, we update k to include the leftmost occurrence of x (which is d[x][0]). This ensures that when we process smaller values later, they can potentially form subarrays starting from this position.

Example Walkthrough: Consider nums = [5, 3, 5, 2, 3, 1]:

• d = {5: [0, 2], 3: [1, 4], 2: [3], 1: [5]}
• Process values in order: 5, 3, 2, 1
  • Value 5: ans = max(0, 2 - inf + 1) = 0, k = 0
  • Value 3: ans = max(0, 4 - 0 + 1) = 5, k = 0
  • Value 2: ans = max(5, 3 - 0 + 1) = 5, k = 0
  • Value 1: ans = max(5, 5 - 0 + 1) = 6, k = 0
• Final answer: 6 (subarray from index 0 to 5)

The time complexity is O(n log n) due to sorting, and space complexity is O(n) for the hash table.

Example Walkthrough

Let's trace through the algorithm with nums = [7, 2, 5, 2, 7, 1, 4]:

Step 1: Build the hash table

d = {7: [0, 4], 2: [1, 3], 5: [2], 1: [5], 4: [6]}

Each value maps to its indices in the array.

Step 2: Sort values in descending order

sorted values: [7, 5, 4, 2, 1]

Step 3: Process each value

Initialize: ans = 0, k = inf

• Process value 7:

  • Rightmost index of 7: d[7][-1] = 4
  • Calculate length: 4 - inf + 1 → not valid (k is still inf)
  • Update ans = 0
  • Update k = min(inf, d[7][0]) = min(inf, 0) = 0

• Process value 5:

  • Rightmost index of 5: d[5][-1] = 2
  • Calculate length: 2 - 0 + 1 = 3 (subarray from index 0 to 2: [7, 2, 5])
  • Since nums[0]=7 > nums[2]=5, this is valid!
  • Update ans = max(0, 3) = 3
  • Update k = min(0, d[5][0]) = min(0, 2) = 0

• Process value 4:

  • Rightmost index of 4: d[4][-1] = 6
  • Calculate length: 6 - 0 + 1 = 7 (subarray from index 0 to 6: [7, 2, 5, 2, 7, 1, 4])
  • Since nums[0]=7 > nums[6]=4, this is valid!
  • Update ans = max(3, 7) = 7
  • Update k = min(0, d[4][0]) = min(0, 6) = 0

• Process value 2:

  • Rightmost index of 2: d[2][-1] = 3
  • Calculate length: 3 - 0 + 1 = 4 (subarray from index 0 to 3: [7, 2, 5, 2])
  • Since nums[0]=7 > nums[3]=2, this is valid!
  • Update ans = max(7, 4) = 7
  • Update k = min(0, d[2][0]) = min(0, 1) = 0

• Process value 1:

  • Rightmost index of 1: d[1][-1] = 5
  • Calculate length: 5 - 0 + 1 = 6 (subarray from index 0 to 5: [7, 2, 5, 2, 7, 1])
  • Since nums[0]=7 > nums[5]=1, this is valid!
  • Update ans = max(7, 6) = 7
  • Update k = min(0, d[1][0]) = min(0, 5) = 0

Final Answer: 7

The longest semi-decreasing subarray is [7, 2, 5, 2, 7, 1, 4] with length 7, where the first element (7) is strictly greater than the last element (4).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The algorithm consists of the following steps:

1. Building a dictionary where each element maps to a list of its indices: This requires iterating through the array once, taking O(n) time.
2. Sorting the dictionary keys in descending order: The dictionary has at most n unique keys (in the worst case, all elements are unique), so sorting takes O(n × log n) time.
3. Iterating through the sorted keys to compute the maximum subarray length: This iteration goes through each unique key once, taking O(n) time in the worst case.

The dominant operation is the sorting step, resulting in an overall time complexity of O(n × log n).

Space Complexity: O(n)

The space usage comes from:

1. The dictionary d that stores lists of indices for each unique element: In the worst case where all elements are the same, we store n indices for one key. In the best case where all elements are unique, we store n keys with one index each. Either way, the total space used is O(n).
2. The sorted list of keys: This contains at most n elements, requiring O(n) space.
3. Variables ans and k: These use O(1) space.

Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Initial Value of min_start_index

The Problem: A common mistake is initializing min_start_index to 0 instead of infinity. This would incorrectly assume there's always a valid starting position at index 0, even before processing any values.

Why It's Wrong: When processing the largest value first, we need to check if there's a valid semi-decreasing subarray. If min_start_index is initialized to 0, we might incorrectly calculate a length for subarrays where the first element equals the last element (not strictly greater).

Incorrect Code:

min_start_index = 0  # Wrong initialization
for value in sorted(value_to_indices, reverse=True):
    max_length = max(max_length, value_to_indices[value][-1] - min_start_index + 1)
    # This would give wrong answer for arrays like [3, 3, 3]

Correct Approach:

min_start_index = float('inf')  # Correct initialization
# Now when processing the largest value, min_start_index - value_to_indices[value][-1] + 1 
# will be negative (since inf - any_number + 1 > 0), so max_length stays 0

Pitfall 2: Not Handling Arrays with All Same Elements

The Problem: When all elements in the array are identical (e.g., [5, 5, 5, 5]), there can be no semi-decreasing subarray since we need the first element to be strictly greater than the last.

Why It Matters: Without proper initialization of min_start_index to infinity, the code might incorrectly return a non-zero length for such arrays.

Test Case to Verify:

nums = [5, 5, 5, 5]
# Expected output: 0
# With wrong initialization, might return 4

Pitfall 3: Forgetting the "+1" in Length Calculation

The Problem: Computing the subarray length as end_index - start_index instead of end_index - start_index + 1.

Example:

# Wrong: 
max_length = max(max_length, value_to_indices[value][-1] - min_start_index)

# Correct:
max_length = max(max_length, value_to_indices[value][-1] - min_start_index + 1)

For a subarray from index 2 to index 5, the length should be 4 (indices 2, 3, 4, 5), not 3.

Pitfall 4: Processing Values in Ascending Order

The Problem: Processing values in ascending order (smallest to largest) instead of descending order would completely break the algorithm logic.

Why It's Wrong: The algorithm relies on maintaining the minimum index from all larger values seen so far. If we process in ascending order, we'd be tracking indices from smaller values, which cannot form valid semi-decreasing subarrays with the current value as the ending element.

Incorrect Code:

for value in sorted(value_to_indices):  # Wrong: ascending order
    # This would look for subarrays where first element < last element

Correct Code:

for value in sorted(value_to_indices, reverse=True):  # Correct: descending order
    # This correctly looks for subarrays where first element > last element