Problem

You are given an integer array nums.

Return _the length of thelongest semi-decreasing subarray of _nums , and0 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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3
4
5
6

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:

1
2
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^5
  • -109 <= nums[i] <= 10^9

Solution

Method 1 – Two Pointers (Sliding Window)

Intuition

A subarray is semi-decreasing if its first element is strictly greater than its last. For each possible starting index, we can extend the subarray to the right as long as the first element is greater than the current last element, and track the maximum length found.

Approach

  1. Initialize ans = 0.
  2. For each left index from 0 to n-2:
    • For each right index from left+1 to n-1:
      • If nums[left] > nums[right], update ans with right - left + 1.
  3. Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int maxSemiDecreasingLength(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        for (int l = 0; l < n-1; ++l) {
            for (int r = l+1; r < n; ++r) {
                if (nums[l] > nums[r]) ans = max(ans, r-l+1);
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func maxSemiDecreasingLength(nums []int) int {
    n, ans := len(nums), 0
    for l := 0; l < n-1; l++ {
        for r := l+1; r < n; r++ {
            if nums[l] > nums[r] && r-l+1 > ans {
                ans = r-l+1
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int maxSemiDecreasingLength(int[] nums) {
        int n = nums.length, ans = 0;
        for (int l = 0; l < n-1; ++l) {
            for (int r = l+1; r < n; ++r) {
                if (nums[l] > nums[r]) ans = Math.max(ans, r-l+1);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun maxSemiDecreasingLength(nums: IntArray): Int {
        val n = nums.size
        var ans = 0
        for (l in 0 until n-1) {
            for (r in l+1 until n) {
                if (nums[l] > nums[r]) ans = maxOf(ans, r-l+1)
            }
        }
        return ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def maxSemiDecreasingLength(self, nums: list[int]) -> int:
        n = len(nums)
        ans = 0
        for l in range(n-1):
            for r in range(l+1, n):
                if nums[l] > nums[r]:
                    ans = max(ans, r-l+1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn max_semi_decreasing_length(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = 0;
        for l in 0..n-1 {
            for r in l+1..n {
                if nums[l] > nums[r] {
                    ans = ans.max((r-l+1) as i32);
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    maxSemiDecreasingLength(nums: number[]): number {
        const n = nums.length;
        let ans = 0;
        for (let l = 0; l < n-1; ++l) {
            for (let r = l+1; r < n; ++r) {
                if (nums[l] > nums[r]) ans = Math.max(ans, r-l+1);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), since we check all pairs (l, r).
  • 🧺 Space complexity: O(1), only a few variables are used.