3105. Longest Strictly Increasing or Strictly Decreasing Subarray
- Array
TIME
O(n)
SPACE
O(1)
Intuition
A strictly increasing subarray ending at i extends the one ending at i - 1 exactly when nums[i] > nums[i - 1]; otherwise it starts over at length 1. The same holds for decreasing with <. So two running lengths are enough, and the answer is the largest value either one ever reaches.
Approach
- Start with
inc = dec = best = 1(a single element counts as both). - For each
ifrom 1:nums[i] > nums[i - 1]:inc += 1,dec = 1nums[i] < nums[i - 1]:dec += 1,inc = 1- equal: both reset to 1, since neither run can include an equal pair
- After each step,
best = max(best, inc, dec).
Complexity
- Time: O(n)
- Space: O(1)
Edge Cases
- A single element: the answer is 1
- All equal (example 2): every step resets, so the answer stays 1
- An equal pair inside a run (
[1, 2, 2, 3]): it breaks the run, so the answer is 2, not 3 - The whole array is monotonic (example 3): the answer is
n - A run that changes direction (
[1, 3, 2]): the peak element ends one run and starts the next, so the answer is 2
Code
from typing import List
class Solution:
def longestMonotonicSubarray(self, nums: List[int]) -> int:
"""
3105. Longest Strictly Increasing or Strictly Decreasing Subarray
Time: O(n)
Space: O(1)
"""
# inc / dec = length of the strictly increasing / decreasing run ending here.
inc = dec = best = 1
for prev, cur in zip(nums, nums[1:]):
if cur > prev:
inc, dec = inc + 1, 1
elif cur < prev:
inc, dec = 1, dec + 1
else:
inc = dec = 1
best = max(best, inc, dec)
return best/**
* 3105. Longest Strictly Increasing or Strictly Decreasing Subarray
* Time: O(n)
* Space: O(1)
*/
class Solution {
public int longestMonotonicSubarray(int[] nums) {
// inc / dec = length of the strictly increasing / decreasing run ending here.
int inc = 1, dec = 1, best = 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;
}
best = Math.max(best, Math.max(inc, dec));
}
return best;
}
}