2393. Count Strictly Increasing Subarrays

Problem Description

You are given an array nums with positive integers. The task is to find out how many subarrays within this array are in strictly increasing order. A subarray is defined as a consecutive sequence of elements from the given array.

Intuition

The intuition behind the solution is to use a two-pointer approach to iterate through the array and identify all the consecutive, strictly increasing subarrays. An incrementing counter is maintained to track the length of each found increasing subarray.

As the outer loop moves through the array, the inner loop expands the current subarray window as long as the next element is greater than the previous one, indicating an increasing sequence. When the inner loop finds that the sequence is no longer increasing, it stops, and the number of subarrays that can be formed with the identified sequence is calculated.

To calculate the number of strictly increasing subarrays that fit within the length of the contiguous sequence, we use the formula for the sum of the first n natural numbers, which is n(n + 1) / 2. This formula is applied because every element in the increasing subarray can be the start of a new subarray, and the number of subarrays ending at each element increases by one for each additional element.

Once counted, the outer loop moves to the end of the previously identified increasing subarray to begin the search for the next sequence. This process continues until the end of the array is reached. The solution has linear time complexity since each element is visited only once by the inner loop.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The given solution uses a simple algorithm with the help of two pointers, i and j. The Python code uses a while loop to iterate over the array with its index i. Inside this loop, another while loop is initiated with index j set to i + 1. Here's a breakdown of the approach:

Initialize an answer variable ans to zero. This will keep the count of strictly increasing subarrays.
Start the outer loop with i at zero, and it will run until it reaches the length of nums.
Inside the outer loop, immediately start the inner loop with j = i + 1.
Continue the inner loop as long as j is less than the length of nums and the current element nums[j] is greater than the previous element nums[j - 1] (the condition for a strictly increasing subarray).
If the condition satisfies inside the inner loop, increment j to expand the current window of the increasing subarray.
Calculate the count cnt of consecutive increasing numbers as j - i.
Use the formula (1 + cnt) * cnt // 2 to add the number of subarrays that can be formed within the window i to j - 1 to ans. This formula derives from the sum of the first n natural numbers formula n * (n + 1) / 2, as each element of the subarray can be the starting element for a new subarray, adding to the total count.
Assign i to j to move to the end of the current strictly increasing sequence and then look for the next one in the outer loop.
After the outer loop concludes, return the cumulative count ans as the result.

This approach does not require any additional data structures and relies on a simple calculation and pointer manipulation to arrive at the solution.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution approach with a small example array nums = [1, 2, 3, 1, 2].

Initialize ans to 0. This is our counter for strictly increasing subarrays.
Begin with i = 0. The value at nums[i] is 1.
Start the inner loop by setting j = i + 1, which is 1 (the second element, which has a value of 2).
Now, nums[j] > nums[j - 1] because 2 (at j) is greater than 1 (at i). Hence, there is a strictly increasing subarray from index 0 to index 1.
Continue incrementing j. It becomes 2, and nums[j] is 3 which still satisfies nums[j] > nums[j - 1].
Incrementing j again to 3, we get nums[j] = 1. This is not greater than 3 (the previous value), so the inner loop stops here.
Calculate the count cnt as j - i, which gives 3 - 0 = 3. We've found a strictly increasing subarray of length 3.
We can form (1 + cnt) * cnt // 2, which is (1 + 3) * 3 // 2 = 6 strictly increasing subarrays from index 0 to index 2.
Add 6 to ans. Now, ans is 6.
Move i to j, so i = 3. The value at nums[i] is 1.
Repeat the process with the new value of i. Start the inner loop with j = i + 1, which is 4. We have nums[j] = 2.
Continue as nums[j] > nums[j - 1] (2 > 1), but since j is now pointing to the last element, the inner loop will stop after this.
Calculate the count cnt as 1 because only one pair 1, 2 satisfies the condition of a strictly increasing subarray.
We can form (1 + cnt) * cnt // 2, which is (1 + 1) * 1 // 2 = 1 additional strictly increasing subarray from index 3 to index 4.
Add 1 to ans. Now, ans is 6 + 1 = 7.
There's no more elements beyond j = 4 to check, so we finish iteration.

At the end of this process, we have determined that there are 7 strictly increasing subarrays within nums.

Solution Implementation

1class Solution:
2    def countSubarrays(self, nums: List[int]) -> int:
3        # Initialize the answer and the starting index
4        subarray_count = start_index = 0
5      
6        # Loop over the array to find all increasing subarrays
7        while start_index < len(nums):
8            # Move to the next index to compare with the current element
9            end_index = start_index + 1
10          
11            # Check if the next element is greater than the current
12            # Continue moving end_index as long as we have an increasing subarray
13            while end_index < len(nums) and nums[end_index] > nums[end_index - 1]:
14                end_index += 1
15          
16            # Calculate the length of the current increasing subarray
17            length = end_index - start_index
18          
19            # Compute the number of possible contiguous subarrays in the increasing subarray
20            # and add to the total count
21            subarray_count += (1 + length) * length // 2
22          
23            # Move start_index to the next point to start checking for a new subarray
24            start_index = end_index
25      
26        # Return the total count of increasing subarrays
27        return subarray_count
28

1class Solution {
2    // Method to count strictly increasing contiguous subarrays within an array.
3    public long countSubarrays(int[] nums) {
4        // Initialize count of subarrays as 0
5        long totalSubarrays = 0;
6        // Start index of the current subarray
7        int startIdx = 0;
8        // Total number of elements in the array
9        int arraySize = nums.length;
10
11        // Iterate over the array
12        while (startIdx < arraySize) {
13            // Initialize end index of the current subarray to be just after startIdx
14            int endIdx = startIdx + 1;
15            // Extend the end index until it no longer forms a strictly increasing subarray
16            while (endIdx < arraySize && nums[endIdx] > nums[endIdx - 1]) {
17                endIdx++;
18            }
19            // Calculate the count of increasing subarrays that can be formed between startIdx and endIdx
20            long currentSubarrayCount = endIdx - startIdx;
21            // Use the formula for the sum of first n numbers to calculate combinations
22            totalSubarrays += (currentSubarrayCount + 1) * currentSubarrayCount / 2;
23            // Move the start index to the end index for the next iteration
24            startIdx = endIdx;
25        }
26
27        // Return the total count of strictly increasing subarrays
28        return totalSubarrays;
29    }
30}
31

1class Solution {
2public:
3    long long countSubarrays(vector<int>& nums) {
4        long long count = 0; // This will hold the total count of valid subarrays
5        int start = 0, n = nums.size(); // `start` is the index to mark the beginning of a new subarray
6      
7        // Iterate over the array
8        while (start < n) {
9            int end = start + 1; // `end` is the index for the end of a growing subarray
10          
11            // Extend the subarray until the current element is not greater than the previous one
12            while (end < n && nums[end] > nums[end - 1]) {
13                ++end;
14            }
15          
16            // Calculate the number of possible subarrays within the current valid range
17            int length = end - start; // Length of the current subarray
18            // Use the arithmetic series sum formula to count subarrays: n * (n + 1) / 2
19            count += 1ll * (1 + length) * length / 2;
20          
21            // Move the start for the next potential subarray
22            start = end;
23        }
24      
25        return count; // Return the total count of the subarrays
26    }
27};
28

1function countSubarrays(nums: number[]): number {
2    // Initialize the count of subarrays
3    let count = 0;
4    // Index 'i' is used to iterate through the array with initialized value of 0
5    let i = 0;
6    // 'n' stands for the length of the input array 'nums'
7    const n = nums.length;
8
9    // Loop over the elements of the array using 'i'
10    while (i < n) {
11        // Initialize 'j' for the inner loop as the next index of 'i'
12        let j = i + 1;
13
14        // Inner loop to find increasing consecutive subarray starting at 'i'
15        while (j < n && nums[j] > nums[j - 1]) {
16            ++j; // Increase 'j' if the current element is greater than the previous
17        }
18
19        // Calculate the length of the current increasing subarray
20        const length = j - i;
21
22        // Calculate the count of subarrays for this segment using the formula for sum of first 'length' natural numbers
23        count += ((1 + length) * length) / 2;
24
25        // Set 'i' to 'j' to look for the next segment
26        i = j;
27    }
28
29    // Return the total count of increasing consecutive subarrays
30    return count;
31}
32

Time and Space Complexity

Time Complexity

The given code consists of a while loop that iterates over the length of the array nums. Inside this loop, there is another while loop that continues as long as the current element is greater than the previous element. This inner loop increments j, effectively counting the length of a monotonically increasing subarray starting at index i. The time complexity of this algorithm depends on the number and size of the monotonically increasing subarrays in nums.

In the best-case scenario, when all elements are in decreasing order, the outer loop runs n times (where n is the length of the array), and the inner loop runs only once for each element, thus giving a time complexity of O(n).

In the worst-case scenario, when all elements are in increasing order, the first inner loop runs n-1 times, the second n-2 times, and so on. Therefore, the number of iterations would resemble the sum of the first n-1 integers, which is (n-1)*n/2, resulting in a time complexity of O(n^2) for this scenario.

However, because each element is visited at most twice (once as the end of a previous subarray and once as the beginning of a new subarray), the actual time complexity, in general, is O(n).

Space Complexity

The space complexity of the provided code is O(1). This is because the code uses a constant amount of extra space for variables ans, i, and j, regardless of the input size. There are no additional data structures that grow with the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know