Longest Strictly Increasing or Strictly Decreasing Subarray solution and explanation
Google
9 more videos on this problem
Longest Strictly Increasing or Strictly Decreasing Subarray - Leetcode 3105 - PythonNeetCodeIO · 7:28 · 7K views
Longest Strictly Increasing or Strictly Decreasing Subarray | Leetcode 3105 | codestorywithMIKcodestorywithMIK · 15:31 · 4K views
Longest Strictly Increasing or Strictly Decreasing Subarray | Leetcode 3105Techdose · 9:00 · 4K views
3105. Longest Strictly Increasing or Strictly Decreasing Subarray | Array | Sliding WindowAryan Mittal · 9:30 · 3K views
Leetcode | 3105. Longest Strictly Increasing or Strictly Decreasing Subarray | Easy | Java SolutionDeveloper Docs · 7:07 · 456 views
3105. Longest Strictly Increasing or Strictly Decreasing Subarray (Leetcode Easy)Programming Live with Larry · 4:20 · 341 views
3105. Longest Strictly Increasing or Strictly Decreasing Subarray | Weekly Contest 392 | LeetcodeRapid Syntax · 9:21 · 137 views
Daily Leetcode #1770: Feb 03, 2025 - 3105. Longest Strictly Increasing or Strictly Decreasing...Programming Live with Larry · 3:17 · 120 views
3105. Longest Strictly Increasing or Strictly Decreasing Subarray | Array | O(n) | LeetcodeRapid Syntax · 7:21 · 104 views
LeetCode 3105 Longest Strictly Increasing or Strictly Decreasing Subarray | Array EasyCode Harmony · 12:40 · 73 views
The 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.
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 <= 501 <= nums[i] <= 50
Approach overview
Problem Overview: You are given an integer array and need the length of the longest contiguous subarray that is either strictly increasing or strictly decreasing. Adjacent elements must follow the rule a[i] > a[i-1] for increasing or a[i] < a[i-1] for decreasing. Equal values break the streak and start a new subarray.
Approach 1: Two Pointers Approach (O(n) time, O(1) space)
This method treats increasing and decreasing segments as separate windows. Use two pointers to expand a window while the order remains strictly increasing or strictly decreasing. When the condition breaks (for example, nums[i] <= nums[i-1] for increasing), reset the window start and continue scanning. Track the maximum length across both types of segments. The array is traversed once, making this approach efficient and easy to reason about when working with contiguous patterns in array problems.
Approach 2: Single Pass with State Variables (O(n) time, O(1) space)
This approach keeps two running counters: one for the current strictly increasing length and one for the strictly decreasing length. While iterating through the array, update these counters based on the comparison between nums[i] and nums[i-1]. If the current value is greater, increment the increasing counter and reset the decreasing counter; if smaller, do the opposite. If equal, reset both counters to 1. Track the global maximum during the scan. This technique is essentially a lightweight state machine and is common in linear scans over array problems that detect ordered segments.
Recommended for interviews: The single-pass state variable solution is typically what interviewers expect. It shows that you can detect patterns while scanning the array once and maintain minimal state. The two pointers method still demonstrates solid reasoning about contiguous windows and aligns well with problems that resemble two pointers or window-style traversal.
Approach 1: Two Pointers Approach
This approach involves using two pointers or variables to track the length of the current strictly increasing or decreasing subarray as we iterate through the list. We update a variable to keep track of the maximum length encountered. The idea is to compare each element with its previous one to determine whether it's part of an increasing or decreasing sequence.
def longest_strict_subarray(nums):
if len(nums) < 2:
return len(nums)
max_len = 1
inc_len = dec_len = 1
for i in range(1, len(nums)):
if nums[i] > nums[i - 1]:
inc_len += 1
dec_len = 1
elif nums[i] < nums[i - 1]:
dec_len += 1
inc_len = 1
else:
inc_len = dec_len = 1
max_len = max(max_len, inc_len, dec_len)
return max_len
nums = [3, 2, 1]
print(longest_strict_subarray(nums))public class Solution {
public int longestStrictSubarray(int[] nums) {
if (nums.length < 2) return nums.length;
int maxLen = 1, incLen = 1, decLen = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
incLen++;
decLen = 1;
} else if (nums[i] < nums[i - 1]) {
decLen++;
incLen = 1;
} else {
incLen = decLen = 1;
}
maxLen = Math.max(maxLen, Math.max(incLen, decLen));
}
return maxLen;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {3, 2, 1};
System.out.println(solution.longestStrictSubarray(nums));
}
}#include <vector>
#include <iostream>
using namespace std;
int longestStrictSubarray(vector<int>& nums) {
int numsSize = nums.size();
if (numsSize < 2) return numsSize;
int maxLen = 1, incLen = 1, decLen = 1;
for (int i = 1; i < numsSize; i++) {
if (nums[i] > nums[i - 1]) {
incLen++;
decLen = 1;
} else if (nums[i] < nums[i - 1]) {
decLen++;
incLen = 1;
} else {
incLen = decLen = 1;
}
maxLen = max(maxLen, max(incLen, decLen));
}
return maxLen;
}
int main() {
vector<int> nums = {3, 2, 1};
cout << longestStrictSubarray(nums) << endl;
return 0;
}function longestStrictSubarray(nums) {
if (nums.length < 2) return nums.length;
let maxLen = 1, incLen = 1, decLen = 1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
incLen++;
decLen = 1;
} else if (nums[i] < nums[i - 1]) {
decLen++;
incLen = 1;
} else {
incLen = decLen = 1;
}
maxLen = Math.max(maxLen, incLen, decLen);
}
return maxLen;
}
let nums = [3, 2, 1];
console.log(longestStrictSubarray(nums));#include <stdio.h>
int longest_strict_subarray(int* nums, int numsSize) {
if (numsSize < 2) return numsSize;
int maxLen = 1, incLen = 1, decLen = 1;
for (int i = 1; i < numsSize; i++) {
if (nums[i] > nums[i - 1]) {
incLen++;
decLen = 1;
} else if (nums[i] < nums[i - 1]) {
decLen++;
incLen = 1;
} else {
incLen = decLen = 1;
}
if (incLen > maxLen) maxLen = incLen;
if (decLen > maxLen) maxLen = decLen;
}
return maxLen;
}
int main() {
int nums[] = {3, 2, 1};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int result = longest_strict_subarray(nums, numsSize);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int LongestStrictSubarray(int[] nums) {
if (nums.Length < 2) return nums.Length;
int maxLen = 1, incLen = 1, decLen = 1;
for (int i = 1; i < nums.Length; i++) {
if (nums[i] > nums[i - 1]) {
incLen++;
decLen = 1;
} else if (nums[i] < nums[i - 1]) {
decLen++;
incLen = 1;
} else {
incLen = decLen = 1;
}
maxLen = Math.Max(maxLen, Math.Max(incLen, decLen));
}
return maxLen;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] nums = {3, 2, 1};
Console.WriteLine(solution.LongestStrictSubarray(nums));
}
}This Python code checks pairs of values to determine if the current subarray is increasing or decreasing. Counters for each kind are updated accordingly, and the outer scope variable 'max_len' tracks the highest value.
Time Complexity: O(n), where n remains the length of the array.
Space Complexity: O(1), since counter variables do not increase with input size.
Approach 2: Single Pass with State Variables
This approach optimizes further by using a state system to record current sequence types (increasing or decreasing). A single loop maintains these states to update the subarray length dynamically. The idea is similar but consolidates the management of the sequence into a reduced number of operations during comparison.
def longest_strict_subarray_state(nums):
if len(nums) < 2:
return len(nums)
max_len = 1
cur_len = 1
is_increasing = is_decreasing = False
for i in range(1, len(nums)):
if nums[i] > nums[i - 1]:
cur_len = cur_len + 1 if is_increasing else 2
is_increasing = True
is_decreasing = False
elif nums[i] < nums[i - 1]:
cur_len = cur_len + 1 if is_decreasing else 2
is_decreasing = True
is_increasing = False
else:
is_increasing = is_decreasing = False
cur_len = 1
max_len = max(max_len, cur_len)
return max_len
nums = [1, 4, 3, 3, 2]
print(longest_strict_subarray_state(nums))public class Solution {
public int longestStrictSubarrayState(int[] nums) {
if (nums.length < 2) return nums.length;
int maxLen = 1, curLen = 1;
boolean isIncreasing = false, isDecreasing = false;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
curLen = isIncreasing ? curLen + 1 : 2;
isIncreasing = true;
isDecreasing = false;
} else if (nums[i] < nums[i - 1]) {
curLen = isDecreasing ? curLen + 1 : 2;
isDecreasing = true;
isIncreasing = false;
} else {
isIncreasing = false;
isDecreasing = false;
curLen = 1;
}
maxLen = Math.max(maxLen, curLen);
}
return maxLen;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 4, 3, 3, 2};
System.out.println(solution.longestStrictSubarrayState(nums));
}
}#include <vector>
#include <iostream>
using namespace std;
int longestStrictSubarrayState(vector<int>& nums) {
int numsSize = nums.size();
if (numsSize < 2) return numsSize;
int maxLen = 1, curLen = 1;
bool isIncreasing = false, isDecreasing = false;
for (int i = 1; i < numsSize; i++) {
if (nums[i] > nums[i - 1]) {
curLen = isIncreasing ? curLen + 1 : 2;
isIncreasing = true;
isDecreasing = false;
} else if (nums[i] < nums[i - 1]) {
curLen = isDecreasing ? curLen + 1 : 2;
isDecreasing = true;
isIncreasing = false;
} else {
isIncreasing = isDecreasing = false;
curLen = 1;
}
maxLen = max(maxLen, curLen);
}
return maxLen;
}
int main() {
vector<int> nums = {1, 4, 3, 3, 2};
cout << longestStrictSubarrayState(nums) << endl;
return 0;
}function longestStrictSubarrayState(nums) {
if (nums.length < 2) return nums.length;
let maxLen = 1, curLen = 1;
let isIncreasing = false, isDecreasing = false;
for (let i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
curLen = isIncreasing ? curLen + 1 : 2;
isIncreasing = true;
isDecreasing = false;
} else if (nums[i] < nums[i - 1]) {
curLen = isDecreasing ? curLen + 1 : 2;
isDecreasing = true;
isIncreasing = false;
} else {
isIncreasing = isDecreasing = false;
curLen = 1;
}
maxLen = Math.max(maxLen, curLen);
}
return maxLen;
}
let nums = [1, 4, 3, 3, 2];
console.log(longestStrictSubarrayState(nums));#include <stdio.h>
int longest_strict_subarray_state(int* nums, int numsSize) {
if (numsSize < 2) return numsSize;
int maxLen = 1, curLen = 1;
int isIncreasing = 0, isDecreasing = 0;
for (int i = 1; i < numsSize; i++) {
if (nums[i] > nums[i - 1]) {
curLen = isIncreasing ? curLen + 1 : 2;
isIncreasing = 1;
isDecreasing = 0;
} else if (nums[i] < nums[i - 1]) {
curLen = isDecreasing ? curLen + 1 : 2;
isDecreasing = 1;
isIncreasing = 0;
} else {
isIncreasing = isDecreasing = 0;
curLen = 1;
}
if (curLen > maxLen) maxLen = curLen;
}
return maxLen;
}
int main() {
int nums[] = {1, 4, 3, 3, 2};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int result = longest_strict_subarray_state(nums, numsSize);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int LongestStrictSubarrayState(int[] nums) {
if (nums.Length < 2) return nums.Length;
int maxLen = 1, curLen = 1;
bool isIncreasing = false, isDecreasing = false;
for (int i = 1; i < nums.Length; i++) {
if (nums[i] > nums[i - 1]) {
curLen = isIncreasing ? curLen + 1 : 2;
isIncreasing = true;
isDecreasing = false;
} else if (nums[i] < nums[i - 1]) {
curLen = isDecreasing ? curLen + 1 : 2;
isDecreasing = true;
isIncreasing = false;
} else {
isIncreasing = false;
isDecreasing = false;
curLen = 1;
}
maxLen = Math.Max(maxLen, curLen);
}
return maxLen;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] nums = {1, 4, 3, 3, 2};
Console.WriteLine(solution.LongestStrictSubarrayState(nums));
}
}This Python solution makes use of boolean flags to determine and adjust the current sequence's length more nimbly. It maintains a single counter, 'cur_len', updating it dynamically based on the sequence phase.
Time Complexity: O(n), each element evaluated once in a loop.
Space Complexity: O(1), since state management involves limited variables.
Approach 3: Two Passes
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).
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;
}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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two Pointers Approach | Time Complexity: O(n), where n remains the length of the array. |
| Single Pass with State Variables | Time Complexity: O(n), each element evaluated once in a loop. |
| Two Passes | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers | O(n) | O(1) | When you prefer explicit window boundaries while scanning increasing or decreasing segments |
| Single Pass with State Variables | O(n) | O(1) | Best general solution for interviews and competitive programming with minimal logic |
Frequently asked questions
Is Longest Strictly Increasing or Strictly Decreasing Subarray easy or hard?
The problem is classified as Easy because it only requires a linear scan and simple comparisons between adjacent elements. Recognizing that equal values break the sequence and maintaining two counters is the key insight.
Longest Strictly Increasing or Strictly Decreasing Subarray Python/Java solution
Both Python and Java implementations typically use a single loop that updates increasing and decreasing counters based on comparisons with the previous element. The logic is identical across languages and runs in O(n) time with constant extra space.
How to solve Longest Strictly Increasing or Strictly Decreasing Subarray in O(n)?
Traverse the array once and maintain two counters: one for the current strictly increasing sequence and one for the strictly decreasing sequence. If nums[i] > nums[i-1], increase the increasing counter and reset the decreasing counter. If nums[i] < nums[i-1], increase the decreasing counter and reset the increasing counter. Track the maximum value seen during the scan.
What is the best approach for Longest Strictly Increasing or Strictly Decreasing Subarray?
The best approach is a single pass using two state variables that track the current increasing and decreasing streak lengths. As you iterate through the array, update the counters based on comparisons with the previous element. This solution runs in O(n) time with O(1) extra space and is typically the approach interviewers expect.
Is Longest Strictly Increasing or Strictly Decreasing Subarray asked at Google/Amazon/Meta?
Variations of monotonic subarray detection appear in interviews at companies like Amazon, Google, and Meta. Interviewers often test the ability to recognize ordered patterns in arrays and design linear-time scans that maintain minimal state.
What data structure is used in Longest Strictly Increasing or Strictly Decreasing Subarray?
The problem primarily uses a simple array traversal with integer counters. No additional data structures such as stacks, heaps, or hash maps are required. The algorithm relies on comparing adjacent elements and maintaining running counts.
What is the time complexity of Longest Strictly Increasing or Strictly Decreasing Subarray?
The optimal time complexity is O(n) because the array is scanned once from left to right. Each element is compared with the previous element to update increasing or decreasing streak counters. The space complexity remains O(1) since only a few integer variables are maintained.