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:
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
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
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)
.
- Generating and checking all subarrays will take
- 🧺 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:
- Initialize Variables: Start by initializing variables to keep track of the current and maximum lengths of increasing (
inc
) and decreasing (dec
) subarrays. - 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.
- 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.
- Update Max Length: Throughout the traversal, continuously update the maximum length encountered for both increasing and decreasing subarrays.
Code
Java
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;
}
}
Python
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)
, wheren
is the length of the arraynums
, as we are iterating through the array once. - 🧺 Space complexity:
O(1)
, as we are using a constant amount of extra space.