Longest Strictly Increasing or Strictly Decreasing Subarray Solution
Longest Strictly Increasing or Strictly Decreasing Subarray solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Longest Strictly Increasing or Strictly Decreasing Subarray is an easy coding problem on arrays, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums, return the length of the longest contiguous subarray that is either strictly increasing or strictly decreasing.
A single element counts as both.
Example 1
Input: nums = [1,4,3,3,2]
Output: 2
Explanation: [1,4] is increasing and [4,3] and [3,2] are decreasing; nothing longer works because of the repeated 3.
Example 2
Input: nums = [3,3,3,3]
Output: 1
Explanation: Equal neighbours break both kinds of run, so only single elements qualify.
Example 3
Input: nums = [3,2,1]
Output: 3
Explanation: The whole array is strictly decreasing.
Constraints
1 <= nums.length <= 501 <= nums[i] <= 50
Hints for Longest Strictly Increasing or Strictly Decreasing Subarray
Hint 1
A strictly increasing subarray can always be extended as long as the next element is larger — think in terms of maximal runs.
Hint 2
Walk the array once, keeping the length of the increasing run and of the decreasing run that end at the current index.
Hint 3
When
nums[i] > nums[i - 1]the increasing run grows and the decreasing run restarts at1; the opposite for<; both restart on equality.
How to solve Longest Strictly Increasing or Strictly Decreasing Subarray
Track two run lengths ending at each index — one for strictly increasing, one for strictly decreasing. Each step either extends a run or resets it to 1, and the answer is the largest value either reaches.
Approach
- Set
inc = dec = best = 1. - For each
i >= 1: ifnums[i] > nums[i - 1], theninc += 1anddec = 1; ifnums[i] < nums[i - 1], thendec += 1andinc = 1; otherwise both become1. - Update
best = max(best, inc, dec)and return it.
Why it works
inc at index i is exactly the length of the longest strictly increasing subarray ending at i: it can extend the one ending at i - 1 precisely when nums[i] > nums[i - 1]. The same holds for dec, and every candidate subarray ends somewhere, so the maximum over all i is the answer.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Equal neighbours break both runs — "strictly" means
[3,3]is neither increasing nor decreasing. - Start
bestat1: a one-element array is a valid answer of length 1.
Reference solution
Python
from typing import List
def longestMonotonicSubarray(nums: List[int]) -> int:
inc = dec = best = 1
for i in range(1, len(nums)):
if nums[i] > nums[i - 1]:
inc, dec = inc + 1, 1
elif nums[i] < nums[i - 1]:
inc, dec = 1, dec + 1
else:
inc = dec = 1
best = max(best, inc, dec)
return bestJava
public static int longestMonotonicSubarray(int[] nums) {
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;
}C++
int longestMonotonicSubarray(vector<int>& nums) {
int inc = 1, dec = 1, best = 1;
for (size_t i = 1; i < nums.size(); 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 = max(best, max(inc, dec));
}
return best;
}JavaScript
var longestMonotonicSubarray = function(nums) {
var inc = 1, dec = 1, best = 1;
for (var 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, inc, dec);
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays