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 ofnums
. - 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 ofnums
and the current elementnums[j]
is greater than the previous elementnums[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 asj - i
. - Use the formula
(1 + cnt) * cnt // 2
to add the number of subarrays that can be formed within the windowi
toj - 1
toans
. This formula derives from the sum of the firstn
natural numbers formulan * (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
toj
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 EvaluatorExample Walkthrough
Let's walk through the solution approach with a small example array nums = [1, 2, 3, 1, 2]
.
- Initialize
ans
to0
. This is our counter for strictly increasing subarrays. - Begin with
i = 0
. The value atnums[i]
is1
. - Start the inner loop by setting
j = i + 1
, which is1
(the second element, which has a value of2
). - Now,
nums[j] > nums[j - 1]
because2
(atj
) is greater than1
(ati
). Hence, there is a strictly increasing subarray from index0
to index1
. - Continue incrementing
j
. It becomes2
, andnums[j]
is3
which still satisfiesnums[j] > nums[j - 1]
. - Incrementing
j
again to3
, we getnums[j] = 1
. This is not greater than3
(the previous value), so the inner loop stops here. - Calculate the count
cnt
asj - i
, which gives3 - 0 = 3
. We've found a strictly increasing subarray of length3
. - We can form
(1 + cnt) * cnt // 2
, which is(1 + 3) * 3 // 2 = 6
strictly increasing subarrays from index0
to index2
. - Add
6
toans
. Now,ans
is6
. - Move
i
toj
, soi = 3
. The value atnums[i]
is1
. - Repeat the process with the new value of
i
. Start the inner loop withj = i + 1
, which is4
. We havenums[j] = 2
. - Continue as
nums[j] > nums[j - 1]
(2
>1
), but sincej
is now pointing to the last element, the inner loop will stop after this. - Calculate the count
cnt
as1
because only one pair1, 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 index3
to index4
. - Add
1
toans
. Now,ans
is6 + 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.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!