Skip to content

2393. Count Strictly Increasing Subarrays πŸ”’

Description

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

Solutions

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def countSubarrays(self, nums: List[int]) -> int:
        ans = i = 0
        while i < len(nums):
            j = i + 1
            while j < len(nums) and nums[j] > nums[j - 1]:
                j += 1
            cnt = j - i
            ans += (1 + cnt) * cnt // 2
            i = j
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public long countSubarrays(int[] nums) {
        long ans = 0;
        int i = 0, n = nums.length;
        while (i < n) {
            int j = i + 1;
            while (j < n && nums[j] > nums[j - 1]) {
                ++j;
            }
            long cnt = j - i;
            ans += (1 + cnt) * cnt / 2;
            i = j;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    long long countSubarrays(vector<int>& nums) {
        long long ans = 0;
        int i = 0, n = nums.size();
        while (i < n) {
            int j = i + 1;
            while (j < n && nums[j] > nums[j - 1]) {
                ++j;
            }
            int cnt = j - i;
            ans += 1ll * (1 + cnt) * cnt / 2;
            i = j;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func countSubarrays(nums []int) int64 {
    ans := 0
    i, n := 0, len(nums)
    for i < n {
        j := i + 1
        for j < n && nums[j] > nums[j-1] {
            j++
        }
        cnt := j - i
        ans += (1 + cnt) * cnt / 2
        i = j
    }
    return int64(ans)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function countSubarrays(nums: number[]): number {
    let ans = 0;
    let i = 0;
    const n = nums.length;
    while (i < n) {
        let j = i + 1;
        while (j < n && nums[j] > nums[j - 1]) {
            ++j;
        }
        const cnt = j - i;
        ans += ((1 + cnt) * cnt) / 2;
        i = j;
    }
    return ans;
}

Solution 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def countSubarrays(self, nums: List[int]) -> int:
        ans = pre = cnt = 0
        for x in nums:
            if pre < x:
                cnt += 1
            else:
                cnt = 1
            pre = x
            ans += cnt
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public long countSubarrays(int[] nums) {
        long ans = 0;
        int pre = 0, cnt = 0;
        for (int x : nums) {
            if (pre < x) {
                ++cnt;
            } else {
                cnt = 1;
            }
            pre = x;
            ans += cnt;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    long long countSubarrays(vector<int>& nums) {
        long long ans = 0;
        int pre = 0, cnt = 0;
        for (int x : nums) {
            if (pre < x) {
                ++cnt;
            } else {
                cnt = 1;
            }
            ans += cnt;
            pre = x;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func countSubarrays(nums []int) (ans int64) {
    pre, cnt := 0, 0
    for _, x := range nums {
        if pre < x {
            cnt++
        } else {
            cnt = 1
        }
        ans += int64(cnt)
        pre = x
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function countSubarrays(nums: number[]): number {
    let ans = 0;
    let pre = 0;
    let cnt = 0;
    for (const x of nums) {
        if (pre < x) {
            ++cnt;
        } else {
            cnt = 1;
        }
        ans += cnt;
        pre = x;
    }
    return ans;
}

Comments