Skip to content

3105. Longest Strictly Increasing or Strictly Decreasing Subarray

Description

You are given an array of integers nums. Return the length of the longest subarray of nums which is either strictly increasing or strictly decreasing.

 

Example 1:

Input: nums = [1,4,3,3,2]

Output: 2

Explanation:

The strictly increasing subarrays of nums are [1], [2], [3], [3], [4], and [1,4].

The strictly decreasing subarrays of nums are [1], [2], [3], [3], [4], [3,2], and [4,3].

Hence, we return 2.

Example 2:

Input: nums = [3,3,3,3]

Output: 1

Explanation:

The strictly increasing subarrays of nums are [3], [3], [3], and [3].

The strictly decreasing subarrays of nums are [3], [3], [3], and [3].

Hence, we return 1.

Example 3:

Input: nums = [3,2,1]

Output: 3

Explanation:

The strictly increasing subarrays of nums are [3], [2], and [1].

The strictly decreasing subarrays of nums are [3], [2], [1], [3,2], [2,1], and [3,2,1].

Hence, we return 3.

 

Constraints:

  • 1 <= nums.length <= 50
  • 1 <= nums[i] <= 50

Solutions

Solution 1: Two Passes

Thinking

The answer is the longest contiguous strictly increasing or strictly decreasing run. Tracking both directions in one pass requires careful resets at turning points and is easy to get wrong.

The array is short enough for two linear scans. Increasing and decreasing runs are independent, so they can be measured separately and compared.

Scan once for strictly rising length and once for strictly falling length, resetting to \(1\) when monotonicity breaks. The larger of the two maxima is the answer.

We first perform a pass to find the length of the longest strictly increasing subarray, and update the answer. Then we perform another pass to find the length of the longest strictly decreasing subarray, and update the answer again.

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def longestMonotonicSubarray(self, nums: List[int]) -> int:
        ans = t = 1
        for i, x in enumerate(nums[1:]):
            if nums[i] < x:
                t += 1
                ans = max(ans, t)
            else:
                t = 1
        t = 1
        for i, x in enumerate(nums[1:]):
            if nums[i] > x:
                t += 1
                ans = max(ans, t)
            else:
                t = 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int longestMonotonicSubarray(int[] nums) {
        int ans = 1;
        for (int i = 1, t = 1; i < nums.length; ++i) {
            if (nums[i - 1] < nums[i]) {
                ans = Math.max(ans, ++t);
            } else {
                t = 1;
            }
        }
        for (int i = 1, t = 1; i < nums.length; ++i) {
            if (nums[i - 1] > nums[i]) {
                ans = Math.max(ans, ++t);
            } else {
                t = 1;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestMonotonicSubarray(vector<int>& nums) {
        int ans = 1;
        for (int i = 1, t = 1; i < nums.size(); ++i) {
            if (nums[i - 1] < nums[i]) {
                ans = max(ans, ++t);
            } else {
                t = 1;
            }
        }
        for (int i = 1, t = 1; i < nums.size(); ++i) {
            if (nums[i - 1] > nums[i]) {
                ans = max(ans, ++t);
            } else {
                t = 1;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func longestMonotonicSubarray(nums []int) int {
    ans := 1
    t := 1
    for i, x := range nums[1:] {
        if nums[i] < x {
            t++
            ans = max(ans, t)
        } else {
            t = 1
        }
    }
    t = 1
    for i, x := range nums[1:] {
        if nums[i] > x {
            t++
            ans = max(ans, t)
        } else {
            t = 1
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function longestMonotonicSubarray(nums: number[]): number {
    const n = nums.length;
    let ans = 1;

    for (let i = 1, t1 = 1, t2 = 1; i < n; i++) {
        t1 = nums[i] > nums[i - 1] ? t1 + 1 : 1;
        t2 = nums[i] < nums[i - 1] ? t2 + 1 : 1;
        ans = Math.max(ans, t1, t2);
    }

    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function longestMonotonicSubarray(nums) {
    const n = nums.length;
    let ans = 1;

    for (let i = 1, t1 = 1, t2 = 1; i < n; i++) {
        t1 = nums[i] > nums[i - 1] ? t1 + 1 : 1;
        t2 = nums[i] < nums[i - 1] ? t2 + 1 : 1;
        ans = Math.max(ans, t1, t2);
    }

    return ans;
}

Comments