Count Strictly Increasing Subarrays - Solution & Explanation

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.