Problem

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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3
4
5
6

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:

1
2
3
4
5
6

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

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Generate all subarrays

Here is the approach:

  • Generate every possible subarray of the given array nums
  • For each subarray, we need to check if it is strictly increasing or strictly decreasing.
  • And the length of the longest valid subarray will be the answer

Pseudocode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def longest_monotonic_subarray(nums):
    ans = 0

    # Iterate over all possible starting indices
    for i in range(len(nums)):
        # Iterate over all possible ending indices
        for j in range(start, len(nums)):
            subarray = nums[i:j+1]

            # Check if the subarray is strictly increasing or decreasing
            if is_strictly_increasing(subarray) or is_strictly_decreasing(subarray):
                # Update max_length if this subarray is longer
                ans = max(ans, len(subarray))
    
    return max_length

def is_strictly_increasing(subarray):
    for i in range(len(subarray) - 1):
        if subarray[i] >= subarray[i + 1]:
            return False
    return True

def is_strictly_decreasing(subarray):
    for i in range(len(subarray) - 1):
        if subarray[i] <= subarray[i + 1]:
            return False
    return True

Complexity

  • ⏰ Time complexity: O(n^3)
    • Generating and checking all subarrays will take O(n^2), and
    • checking each subarray for being strictly increasing or decreasing will take O(n).
  • 🧺 Space complexity: O(1)

Method 2 - Maintain the increasing and decreasing subarray size counter

To solve the problem of finding the length of the longest subarray that is either strictly increasing or strictly decreasing in an array of integers nums, follow this updated approach:

  1. Initialize Variables: Start by initializing variables to keep track of the current and maximum lengths of increasing (inc) and decreasing (dec) subarrays.
  2. Iterate through the Array: Traverse the array and compare each element with the previous one to determine if the current subarray is increasing or decreasing.
  3. Update Lengths:
    • If the current element is greater than the previous one (indicating an increase), increment the length of the increasing subarray and reset the length of the decreasing subarray.
    • If the current element is less than the previous one (indicating a decrease), increment the length of the decreasing subarray and reset the length of the increasing subarray.
    • If the current element is equal to the previous one, reset both lengths to 1.
  4. Update Max Length: Throughout the traversal, continuously update the maximum length encountered for both increasing and decreasing subarrays.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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

class Solution:
    def longestMonotonicSubarray(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        inc = 1
        dec = 1
        ans = 1
        
        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                inc += 1
                dec = 1
            elif nums[i] < nums[i - 1]:
                dec += 1
                inc = 1
            else:
                inc = 1
                dec = 1
            ans = max(ans, inc, dec)
        
        return ans

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the array nums, as we are iterating through the array once.
  • 🧺 Space complexity: O(1), as we are using a constant amount of extra space.