Count Strictly Increasing Subarrays
EbayThe 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.
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.
Input: nums = [1,2,3,4,5] Output: 15 Explanation: Every subarray is strictly increasing. There are 15 possible subarrays that we can take.
Consider the array nums = [2, 4, 3, 5, 6]. How many** strictly increasing **subarrays can you find?
- 1 <= nums.length <= 105
- 1 <= nums[i] <= 106
cpp
class Solution {
public:
long long countSubarrays(vector<int>& nums) {
// Your code goes here
}
};java
class Solution {
public long countSubarrays(int[] nums) {
// Your code goes here
}
}python
class Solution:
def countSubarrays(self, nums):
# Your code goes herejavascript
class Solution {
countSubarrays(nums) {
// Your code goes here
}
}csharp
class Solution
{
public long CountSubarrays(int[] nums)
{
// Your code goes here
}
}go
func countSubarrays(nums []int) int64{
}Stuck? Show a way to structure it+
- 01Track the length of the current strictly increasing run.
- 02Extend it when `nums[i] > nums[i-1]`; otherwise reset it to one.
- 03Add the current run length to the answer at every index.
- 04Use a 64-bit accumulator because the count can be quadratic.
Reference answer
Then expect these follow-ups
How would you count non-decreasing subarrays?
Tests: condition adaptation
How would you answer many range queries for this count?
Tests: preprocessing
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question