Count Strictly Increasing Subarrays - Solution & Explanation
Problem Statement
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).
Code
Python
Java
C++
Go
TypeScript
Detailed 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 |
Video Solution
2393. Count Strictly Increasing Subarrays (Leetcode Medium) • Programming Live with Larry • 616 views views
Watch 3 more video solutions →Frequently Asked Questions
Is Count Strictly Increasing Subarrays easy or hard?
How to solve Count Strictly Increasing Subarrays in O(n)?
What is the best approach for Count Strictly Increasing Subarrays?
What data structure is used in Count Strictly Increasing Subarrays?
What is the time complexity of Count Strictly Increasing Subarrays?
Count Strictly Increasing Subarrays Python or Java solution approach?
Is Count Strictly Increasing Subarrays asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Count Strictly Increasing Subarrays with our built-in code editor and test cases.
Practice on FleetCode