We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Length of Semi-Decreasing Subarrays

Number: 3158

Difficulty: Medium

Paid? Yes

Companies: Google, TikTok

Problem Description

Given an integer array nums, find the length of the longest contiguous (non‐empty) subarray such that the first element is strictly greater than the last element (i.e. the subarray is “semi-decreasing”). If no such subarray exists, return 0.

Key Insights

  • Only the two endpoints matter; the interior values do not affect whether the subarray is semi-decreasing.
  • For any subarray defined by indices i and j (with i < j), the condition reduces to nums[i] > nums[j].
  • Maximizing the subarray length is equivalent to finding a pair (i, j) with i < j, nums[i] > nums[j] and j-i+1 as large as possible.
  • A monotonic stack can be used to record candidate left endpoints. In our solution we maintain only those indices that are “optimal” – they appear in increasing order with respect to index and (consequently) increasing order in value when we only push a new index if its value is strictly greater than the last candidate’s value.
  • Then for each candidate right endpoint (scanning from the end toward the beginning), we use binary search on the candidate list (restricted to indices less than j) to quickly find the left endpoint with the smallest index that still satisfies nums[i] > nums[j].

Space and Time Complexity

Time Complexity: O(n log n) – building the candidate list takes O(n) and for each of the n indices we potentially perform a binary search (log n). Space Complexity: O(n) – for storing the candidate indices and their corresponding values.

Solution

We first build a candidate “stack” of left indices. The idea is: while iterating from left to right, we add index i only if nums[i] is strictly greater than the value at the last candidate index (or if the candidate list is empty). This is because a candidate with a lower index and a higher value is strictly better when we try to maximize the subarray’s length.

After building the candidate list (which is sorted by index and also by increasing value thanks to our push condition), we iterate from the far right end of the array backward. For each index j (serving as a potential right endpoint), we need to choose a candidate left index that is less than j and has a value greater than nums[j]. Since the candidate values are sorted in ascending order, we can use binary search (on the portion of the candidate list that contains indices < j) to find the leftmost candidate that is greater than nums[j]. The answer is then updated with j - candidate_index + 1 if this width is larger than the current maximum.

A few important notes:

  • If no such candidate is found for any j, the answer remains 0.
  • Even though the subarray length is computed as j - i + 1, a valid subarray must have at least 2 elements.
  • We take “strictly greater” into account in the binary search: even if nums[candidate] equals nums[j] the condition fails.

Code Solutions

# Python solution with detailed line-by-line comments
import bisect

class Solution:
    def longestSemiDecreasingSubarray(self, nums):
        n = len(nums)
        # Candidate stack for left indices: only add an index i if nums[i] is strictly greater than 
        # the last candidate's value. This ensures that:
        # 1. The indices are in increasing order
        # 2. Their corresponding values are in increasing order.
        candidate_indices = []
        for i in range(n):
            # If candidate_indices is empty or we find a new candidate whose value is higher than
            # the last candidate then add it
            if not candidate_indices or nums[i] > nums[candidate_indices[-1]]:
                candidate_indices.append(i)
        # Prepare an array of candidate values for binary search.
        candidate_values = [nums[i] for i in candidate_indices]
        
        max_length = 0
        # For each possible right endpoint, starting from the end (largest j) to the beginning
        for j in range(n-1, -1, -1):
            # Only consider candidate left indices that come before j.
            # Use bisect_right to find count of candidate indices that are <= j-1.
            pos_upper = bisect.bisect_right(candidate_indices, j-1)
            if pos_upper == 0:
                continue  # No candidate left index where i < j
            # In candidate_values[0 ... pos_upper-1], perform a binary search to find the 
            # leftmost candidate with value > nums[j] (the condition for a semi-decreasing subarray).
            lo, hi = 0, pos_upper - 1
            candidate_pos = -1
            while lo <= hi:
                mid = (lo + hi) // 2
                if candidate_values[mid] > nums[j]:
                    candidate_pos = mid
                    hi = mid - 1  # look for a candidate with an even smaller index
                else:
                    lo = mid + 1
            # If we found a valid candidate, update max_length accordingly.
            if candidate_pos != -1:
                candidate_index = candidate_indices[candidate_pos]
                current_length = j - candidate_index + 1
                if current_length > max_length:
                    max_length = current_length
        return max_length
← Back to All Questions