Problem

You are given an array nums consisting of positive integers.

Return _the number ofsubarrays of _nums that are instrictly increasing order.

A subarray is a contiguous part of an array.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3

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^5
  • 1 <= nums[i] <= 10^6

Solution

Method 1 – Sliding Window (Counting Lengths)

Intuition

A strictly increasing subarray can be counted by tracking the length of the current increasing segment. For each element, if it is greater than the previous, extend the segment; otherwise, reset. The number of strictly increasing subarrays ending at each position is equal to the length of the current segment.

Approach

  1. Initialize ans = 0 and len = 1.
  2. Iterate through the array from index 0 to n-1:
    1. If i == 0 or nums[i] <= nums[i-1], reset len = 1.
    2. Else, increment len by 1.
    3. Add len to ans.
  3. Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    long long countSubarrays(vector<int>& nums) {
        long long ans = 0, len = 1;
        for (int i = 0; i < nums.size(); ++i) {
            if (i == 0 || nums[i] <= nums[i-1]) len = 1;
            else len++;
            ans += len;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func countSubarrays(nums []int) int64 {
    ans, l := int64(0), 1
    for i := 0; i < len(nums); i++ {
        if i == 0 || nums[i] <= nums[i-1] {
            l = 1
        } else {
            l++
        }
        ans += int64(l)
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public long countSubarrays(int[] nums) {
        long ans = 0;
        int len = 1;
        for (int i = 0; i < nums.length; i++) {
            if (i == 0 || nums[i] <= nums[i-1]) len = 1;
            else len++;
            ans += len;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun countSubarrays(nums: IntArray): Long {
        var ans = 0L
        var len = 1
        for (i in nums.indices) {
            if (i == 0 || nums[i] <= nums[i-1]) len = 1
            else len++
            ans += len
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def countSubarrays(self, nums: list[int]) -> int:
        ans = 0
        l = 1
        for i in range(len(nums)):
            if i == 0 or nums[i] <= nums[i-1]:
                l = 1
            else:
                l += 1
            ans += l
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn count_subarrays(nums: Vec<i32>) -> i64 {
        let mut ans = 0i64;
        let mut len = 1i64;
        for i in 0..nums.len() {
            if i == 0 || nums[i] <= nums[i-1] {
                len = 1;
            } else {
                len += 1;
            }
            ans += len;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    countSubarrays(nums: number[]): number {
        let ans = 0, len = 1;
        for (let i = 0; i < nums.length; i++) {
            if (i === 0 || nums[i] <= nums[i-1]) len = 1;
            else len++;
            ans += len;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), since we scan the array once.
  • 🧺 Space complexity: O(1), only a few variables are used.