MiddleCodeOccasionalNot answered yet
Longest strictly monotone contiguous subarray in O(n)
Given an integer array, find the longest strictly increasing OR strictly decreasing contiguous subarray and return its [start, end] indices. For [2,7,5,4,3] the answer is the run 7,5,4,3 at indices [1,4].
Requirements:
- O(n) time, O(1) extra space; do not modify the input.
std::pair<int,int> longestMonotoneRun(const std::vector<int>& a) {
// your code here
}Write the implementation.
Scan once, tracking the current run's start and direction. When the next pair flips direction, start a new run at the previous index; when it is equal, start at the current index. Keep the longest run seen. Equality always breaks a strict run. O(n) time, O(1) space.
- ✗Treating equal adjacent values as extending a strictly monotone run
- ✗Resetting the run start to the current index instead of the previous one on a direction flip
- ✗Off-by-one when the longest run ends at the last element
- →Why must a new run start at the previous index, not the current one?
- →How would the logic change for non-strict (allowing equal) monotonicity?
Contents
Task
Find the longest strictly monotone contiguous subarray in one pass.
Solution
std::pair<int,int> longestMonotoneRun(const std::vector<int>& a) {
if (a.empty()) return {-1, -1};
int bestStart = 0, bestEnd = 0, runStart = 0;
int dir = 0; // +1 up, -1 down, 0 unknown
for (int i = 1; i < static_cast<int>(a.size()); ++i) {
int d = (a[i] > a[i-1]) - (a[i] < a[i-1]); // -1/0/+1
if (d == 0 || (dir != 0 && d != dir)) {
runStart = (d == 0) ? i : i - 1; // equality breaks strict
dir = d;
} else {
dir = d;
}
if (i - runStart > bestEnd - bestStart) { bestStart = runStart; bestEnd = i; }
}
return {bestStart, bestEnd};
}Key points
- A single scan tracks the run direction; a flip or equality resets it.
- On a direction flip the new run starts at the previous index.
- Equality breaks strict monotonicity.
Contents
