3350. Adjacent Increasing Subarrays Detection II.cpp #274
Description
Problem Number
3350
Problem Title
Adjacent Increasing Subarrays Detection II
LeetCode Link
https://leetcode.com/problems/adjacent-increasing-subarrays-detection-ii/description/
Contribution Checklist
- I have written the Approach section.
- I have written the Intuition section.
- I have included a working C++ solution.
- I will raise a PR and ensure the filename follows the convention
[Number]. [Problem Title].cpp.
Approach
Approach:
First, build an array that stores the length of the current increasing streak ending at each position.
Then use binary search on k, the possible subarray length, to find the largest value for which two consecutive increasing parts of size k exist.
This approach is efficient because it relies on precomputed streaks rather than brute-force comparisons.
Complexity:
Time: O(n log n) due to binary search over possible lengths combined with linear checks.
Space: O(n) for storing streak lengths.
Intuition
Intuition:
The goal is to find the longest point in the array where two strictly increasing parts appear one after another. Instead of checking every subarray, we track how long each increasing streak continues and use that to figure out where two valid segments can exist.
Solution in C++
class solution{
public:
bool check(int* inc, int n, int k) {
for (int end1 = k - 1; end1 + k < n; end1++) {
if (inc[end1] >= k && inc[end1 + k] >= k) {
return true;
}
}
return false;
}
int maxIncreasingSubarrays(int* nums, int numsSize) {
int n = numsSize;
int inc[n];
for (int i = 0; i < n; i++) inc[i] = 1;
// Build the increasing streak lengths
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
inc[i] = inc[i - 1] + 1;
}
}
int L = 1, R = n / 2;
int ans = 0;
// Binary search for max k
while (L <= R) {
int mid = L + (R - L) / 2;
if (check(inc, n, mid)) {
ans = mid; // mid works, try bigger k
L = mid + 1;
} else {
R = mid - 1; // mid too big, try smaller k
}
}
return ans;
}
};