Count Strictly Increasing Subarrays

Problem Statement

In this task, we are given an array of positive integers named nums. Our goal is to determine the total number of contiguous subarrays within nums that exhibit a strictly increasing sequence. Each element of the array nums participates in the formation of subarrays, where a subarray is defined as a continuous slice of the original array.

Examples

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 <= 105
• 1 <= nums[i] <= 106

Approach and Intuition

To solve the problem of counting strictly increasing subarrays, let's delve into the intuition and the approach based on given examples and constraints:

Detailed Steps

1. Understanding Edge Cases: Consider small cases like [1], [1, 2] and [1, 2, 1, 3]. Each offers insight on how to handle single elements (always a valid subarray), pairs (valid if in increasing order), and the reset of count when the sequence isn't strictly increasing.

2. Initial Observations from Examples:

   • Example 1: {1, 3, 5, 4, 4, 6} illustrates a reset in increasing pattern at elements 5 and 4, and again at 4 and 4. This calls for a mechanism to continuously check and reset when the sequence breaks.
   • Example 2: {1, 2, 3, 4, 5} being entirely strictly increasing, provides the sum of all possible subarrays, which is the maximum possibility for an array of its nature.

3. Functionality to Catch Subarrays:

   • Start with each element considering it as a potential beginning of a new subarray.
   • Move forward and count as long as the next element is greater than the current one.
   • When the sequence breaks (or ends), sum up all possible subarrays starting from the first element of the current strictly increasing sequence. This could be calculated using the formula for the sum of first n natural numbers, where n is the length of the current sequence (because every element can be the start of a new subarray).

4. Edge Case Handlings:

   • Single element arrays always have exactly one increasing subarray (the element itself).
   • Arrays of length two require a simple comparison.

Given the constraints (1 <= nums.length <= 105 and 1 <= nums[i] <= 106), the solution needs to efficiently handle large inputs, making the approach of continuously checking and summing subarrays optimal without necessitating a double loop to explicitly evaluate every possible subarray.

Solutions

class Solution {
public:
    long long countIncreasingSubsequences(vector<int>& elements) {
        long long totalSubsequences = 0;
    
        for (int index = 0; index < elements.size(); index++) {
            long lengthOfSubsequence = 1;
    
            while (index + 1 < elements.size() && elements[index] < elements[index + 1]) {
                lengthOfSubsequence++;
                index++;
            }
    
            totalSubsequences += (lengthOfSubsequence * (lengthOfSubsequence + 1)) / 2;
        }
    
        return totalSubsequences;
    }
};