3105. Longest Strictly Increasing or Strictly Decreasing Subarray
EasyView on LeetCode
Time: O(n)
Space: O(1)
Problem Overview
The goal is the longest contiguous stretch that is either strictly rising or strictly falling.
Intuition
The goal is the longest contiguous stretch that is either strictly rising or strictly falling. Equals break both patterns, so a plateau restarts both run lengths at 1. While scanning left to right, one counter tracks the current strictly increasing run and another tracks the current strictly decreasing run. A rise extends the increasing counter and resets the decreasing one. A fall does the opposite. After every step the answer is the larger of those two counters. A single pass is enough because only the active run at the right edge can grow.
Algorithm
- 1Start the answer and both run lengths at 1.
- 2For each adjacent pair, compare the new value with the previous one.
- 3On a rise, grow the increasing run and reset the decreasing run to 1.
- 4On a fall, grow the decreasing run and reset the increasing run to 1.
- 5On an equal pair, reset both runs to 1.
- 6Keep the maximum of the two runs after each step and return it.
Example Walkthrough
Input: nums = [1, 4, 3, 3, 2]
- 1.1 to 4 raises the increasing run to 2. 4 to 3 starts a decreasing run of length 2.
- 2.3 to 3 is equal, so both runs reset to 1.
- 3.3 to 2 starts a decreasing run of length 2. The longest run seen is 2.
Output: 2
Common Pitfalls
- •The subarray must be contiguous. Skipping elements is not allowed.
- •Equal neighbors break both directions. Do not keep either run alive across a plateau.
- •A single element is a valid monotonic subarray of length 1, so the answer is at least 1.
- •Track increasing and decreasing separately. Mixing both directions in one counter would describe a mountain, which is a different problem.
3105.cs
C#
// Approach: Walk the array once while keeping the length of the current
// strictly increasing run and the current strictly decreasing run. A rise
// extends the increasing run and resets the decreasing one, a fall does the
// opposite, and an equal pair resets both. The answer is the longest run
// seen. Every element must be read, so the bound is already tight.
// Time: O(n) Space: O(1)
public class Solution
{
public int LongestMonotonicSubarray(int[] nums)
{
int ans = 1;
int increasing = 1;
int decreasing = 1;
for (int i = 1; i < nums.Length; ++i)
{
if (nums[i] > nums[i - 1])
{
increasing += 1;
decreasing = 1;
}
else if (nums[i] < nums[i - 1])
{
decreasing += 1;
increasing = 1;
}
else
{
increasing = 1;
decreasing = 1;
}
ans = Math.Max(ans, Math.Max(increasing, decreasing));
}
return ans;
}
}Was this solution helpful?
Related Problems
- 4. Median of Two Sorted Arrays(Hard)
- 11. Container With Most Water(Medium)
- 15. 3Sum(Medium)
- 16. 3Sum Closest(Medium)
- 26. Remove Duplicates from Sorted Array(Easy)
- 27. Remove Element(Easy)