Count Strictly Increasing Subarrays solution and explanation
3 more videos on this problem
2393. Count Strictly Increasing Subarrays (Leetcode Medium)Programming Live with Larry · 5:31 · 616 views
Leetcode 2393. Count Strictly Increasing Subarrays - DPCode-Yao · 8:12 · 479 views
Leetcode 2393. Count Strictly Increasing Subarrays - Python tutorialCode with Carter · 11:14 · 390 views
2393. Count Strictly Increasing Subarrays - Week 5/5 Leetcode September ChallengeProgramming Live with Larry · 10:24 · 240 views
The problem
You are given an array nums consisting of positive integers.
Return the number of subarrays of nums that are in strictly increasing order.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,3,5,4,4,6] Output: 10 Explanation: The strictly increasing subarrays are the following: - Subarrays of length 1: [1], [3], [5], [4], [4], [6]. - Subarrays of length 2: [1,3], [3,5], [4,6]. - Subarrays of length 3: [1,3,5]. The total number of subarrays is 6 + 3 + 1 = 10.
Example 2:
Input: nums = [1,2,3,4,5] Output: 15 Explanation: Every subarray is strictly increasing. There are 15 possible subarrays that we can take.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 106
Approach overview
Problem Overview: You get an integer array nums. The task is to count how many contiguous subarrays are strictly increasing. A subarray is valid if every next element is greater than the previous one. Single-element subarrays count because they are trivially increasing.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
Start every subarray at index i and extend it to the right while the sequence remains strictly increasing. For each new index j, check whether nums[j] > nums[j-1]. If the condition holds, the subarray nums[i..j] is valid and contributes to the count. The moment the increasing property breaks, stop extending that start position and move to the next i. This method literally enumerates every possible starting point and grows it forward. It is simple and useful when you want a straightforward implementation, but the nested iteration leads to O(n²) time in the worst case when the array is fully increasing.
Approach 2: Increasing Run Counting (Enumeration Optimization) (O(n) time, O(1) space)
Instead of checking every subarray individually, observe that strictly increasing subarrays appear inside continuous increasing runs. Suppose a run has length L. The number of strictly increasing subarrays inside that run equals L * (L + 1) / 2. Walk through the array once and track the length of the current increasing streak. If nums[i] > nums[i-1], extend the streak. Otherwise, reset the streak to length 1. Each step contributes exactly the current streak length to the total count, because every new element forms new subarrays ending at that position. This reduces the work to a single pass over the array.
This pattern appears frequently in array problems where properties depend on adjacent comparisons. It can also be viewed as a lightweight dynamic programming state where dp[i] represents the length of the increasing subarray ending at index i. The summation of all dp[i] values gives the answer. The formula used to count subarrays inside a run comes from simple math on consecutive segments.
Recommended for interviews: Interviewers expect the linear run-counting approach. Starting with the brute force method demonstrates you understand the definition of increasing subarrays. Then optimize by recognizing that consecutive increasing segments can be aggregated, reducing the complexity from O(n²) to O(n). The final solution uses constant extra space and a single traversal, which is the optimal implementation.
Solution
We can enumerate the number of strictly increasing subarrays ending at each element and then sum them up.
We use a variable cnt to record the number of strictly increasing subarrays ending at the current element, initially cnt = 1. Then we traverse the array starting from the second element. If the current element is greater than the previous element, then cnt can be incremented by 1. Otherwise, cnt is reset to 1. At this point, the number of strictly increasing subarrays ending at the current element is cnt, and we add it to the answer.
After the traversal, return the answer.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
class Solution:
def countSubarrays(self, nums: List[int]) -> int:
ans = cnt = 1
for x, y in pairwise(nums):
if x < y:
cnt += 1
else:
cnt = 1
ans += cnt
return ansclass Solution {
public long countSubarrays(int[] nums) {
long ans = 1, cnt = 1;
for (int i = 1; i < nums.length; ++i) {
if (nums[i - 1] < nums[i]) {
++cnt;
} else {
cnt = 1;
}
ans += cnt;
}
return ans;
}
}class Solution {
public:
long long countSubarrays(vector<int>& nums) {
long long ans = 1, cnt = 1;
for (int i = 1; i < nums.size(); ++i) {
if (nums[i - 1] < nums[i]) {
++cnt;
} else {
cnt = 1;
}
ans += cnt;
}
return ans;
}
};function countSubarrays(nums: number[]): number {
let [ans, cnt] = [1, 1];
for (let i = 1; i < nums.length; ++i) {
if (nums[i - 1] < nums[i]) {
++cnt;
} else {
cnt = 1;
}
ans += cnt;
}
return ans;
}func countSubarrays(nums []int) int64 {
ans, cnt := 1, 1
for i, x := range nums[1:] {
if nums[i] < x {
cnt++
} else {
cnt = 1
}
ans += cnt
}
return int64(ans)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Useful for understanding the problem or when array size is small |
| Increasing Run Counting (Linear Enumeration) | O(n) | O(1) | Best general solution for large arrays and interview settings |
| DP Interpretation (Track length ending at i) | O(n) | O(1) | When explaining the solution using dynamic programming terminology |
Frequently asked questions
Is Count Strictly Increasing Subarrays easy or hard?
The problem is typically rated Medium because recognizing the increasing run pattern is the key insight. The implementation itself is straightforward once you realize that each index contributes the length of the current increasing streak.
How to solve Count Strictly Increasing Subarrays in O(n)?
Maintain a variable representing the length of the current strictly increasing subarray ending at index i. If nums[i] > nums[i-1], increase the streak length; otherwise reset it to 1. Add the streak length to the total at each step. This counts all valid subarrays ending at every index in a single pass.
What is the best approach for Count Strictly Increasing Subarrays?
The optimal approach scans the array once and tracks the length of the current strictly increasing run. Each element contributes the length of the run ending at that index to the answer. This method runs in O(n) time and uses O(1) extra space, making it the expected interview solution.
What data structure is used in Count Strictly Increasing Subarrays?
The solution primarily uses basic array traversal. No advanced data structures are required. The algorithm relies on tracking a running counter for the current increasing streak and accumulating results during the pass.
What is the time complexity of Count Strictly Increasing Subarrays?
The optimal solution runs in O(n) time because the array is traversed exactly once while maintaining the length of the current increasing streak. A naive enumeration approach can take O(n²) time if it checks every possible starting position and extends the subarray forward.
Count Strictly Increasing Subarrays Python or Java solution approach?
In both Python and Java, the logic is identical: iterate through the array, maintain a streak length for increasing elements, and add it to the result each iteration. This produces an O(n) time and O(1) space implementation in any language.
Is Count Strictly Increasing Subarrays asked at Google, Amazon, or Meta?
Problems involving counting increasing subarrays or sequences frequently appear in interviews at companies like Amazon and Google because they test array traversal, pattern recognition, and simple dynamic programming optimizations.