Introduction
In this problem, we are given an array of integers, and our task is to count the number of strictly increasing subarrays of size ≥ 2.
A subarray is considered strictly increasing if every next element is greater than the previous one:
arr[i] > arr[i - 1]
Instead of checking all possible subarrays (which would be inefficient), we use a smart linear-time approach based on increasing segments.
Key Idea
We do NOT directly count subarrays.
Instead, we:
Break the array into continuous increasing segments
For each segment, calculate how many increasing subarrays it contributes
Formula
If an increasing segment has length L, then number of strictly increasing subarrays is:
L × (L - 1) / 2
Why?
Because every pair of indices inside the segment forms a valid increasing subarray.
Step-by-Step Approach
Step 1: Initialize variables
Step 2: Traverse array
For each element:
len × (len - 1) / 2
Step 3: Handle last segment
After loop ends, add contribution of last segment.
Example
Input:
arr = [1, 4, 5, 3, 7, 9]
Step-by-step:
Step: 1
Element: 1
Condition: start
len: 1
Count: 0
Step: 2
Element: 4
Condition: 4 > 1
len: 2
Count: 0
Step: 3
Element: 5
Condition: 5 > 4
len: 3
Count: 0
Step: 4
Element: 3
Condition: break
len: 1
Count: 3
Step: 5
Element: 7
Condition: 7 > 3
len: 2
Count: 3
Step: 6
Element: 9
Condition: 9 > 7
len: 3
Count: 3
Final addition:
Output:
6
Java Code
class Solution {
public int countIncreasing(int[] arr) {
int n = arr.length;
int len = 1; // length of current increasing segment
int count = 0; // final answer
for (int i = 1; i < n; i++) {
if (arr[i] > arr[i - 1]) {
len++; // extend segment
} else {
// segment ends
count += (len * (len - 1)) / 2;
len = 1;
}
}
// add last segment
count += (len * (len - 1)) / 2;
return count;
}
}
Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Conclusion
This problem demonstrates an important optimization technique:
Instead of checking all subarrays (O(n²)), we reduce it to O(n) by grouping elements into increasing segments.
The key insight is that:
Every increasing segment of length L contributes L × (L - 1) / 2 valid subarrays.
This pattern is widely useful in array-based problems involving: