Count Strictly Increasing Subarrays

Table of Contents

Leetcode 2393. Count Strictly Increasing Subarrays

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 <= 10⁵
1 <= nums[i] <= 10⁶

Source: Leetcode 2393. Count Strictly Increasing Subarrays

Solution

We can solve this problem by running two nested loops and counting strictly increasing subarrays. But that will give us an O(N²) time complexity which we do not want.

There is a better approach.

To apply that, we need to understand the fact that, for any element in an array, if we count how many contiguous elements before that element is passed, we can know the number of contiguous subarrays starting from some point up to that element.

Sounds complex?

Let’s examine this fact by looking at the below image. Let’s say we have a variable increment_so_far initialized by 1 at the beginning.

Now, we will go from index 1 up to the end of the array as long as we find an element is strictly greater than it’s previous element. Also we will increment increment_so_far by 1 when that condition is fulfilled.

At index 1, 3 is > 1, so we do increment_so_far += 1 or increment_so_far = 2 now.

At index 2, 5 > 3, we again do increment_so_far += 1 or increment_so_far = 3 now.

Looking at the below image you see, how the updated value of increment_so_far tells us how many distinct contiguous subarrays are there starting from index 0 to index 2. There are three arrays, i.e. [5], [3,5] and [1,3,5] which are strictly increasing, contiguous and unique.

Leetcode 2393. Count Strictly Increasing Subarrays

Let’s practice this idea by simulating a test case from the problem description.

Let’s say, we have an array as below. We initialize increment_so_far = 1 and result = 1. Why increment_so_far = 1? Because, if there is no increasing subsequence, we have to add an element’s count considering it a single element array. Why result = 1? If there is only one element in the array, the program will not go into the loop, so we should have a result ready for that edge case.

Now, let’s start with index 1. At this point, nums[1] > nums[0]. So, we increment increment_so_far by 1 and update our result.

After that, at index 2. At this point, nums[2] > nums[1]. So, we increment increment_so_far by 1 and update our result.

At index 3. At this point, nums[3] is NOT > nums[2]. So, we reinitialize increment_so_far = 1 and update our result.

The process will continue until we reach end of the array.

Code

class Solution {
public:
    long long countSubarrays(vector<int>& nums) {
        long long result = 1;
        long long increment_so_far = 1;

        for(int i = 1; i < nums.size(); i++)
        {
            if(nums[i] > nums[i - 1])
                increment_so_far += 1;
            else
                increment_so_far = 1;
            
            result += increment_so_far;
        }
        return result;
    }
};

Time and Space Complexity

We are looping through the entire array once. So, the time complexity is essentially the length of the array or O(N) where N = array length. We are not using any extra space that can change size by the input size. So, we have an O(1) space complexity.

Conclusion

Hope you enjoyed the solution. Please write in the comment section if you didn’t like it or you have any suggestion to improve it.

Till our next post, Happy coding! 😀

Bonus – System Design!

ByteByteGo is by far the best system design resource found on the internet. They are growing like crazy!

We suggest you checkout their course if you really want to dive deep in system design and want to have a better interview.

Here is the link: ByteByteGo!

Disclaimer: this is a genuine suggestion, but we have some benefits too! We get commission if you buy their course. However, there are other courses online which we do not promote. Because we promote only things that are the best in our opinion and those we really feel like helpful for our audience.