LeetCode 2393 - Count Strictly Increasing Subarrays

LeetCode Problem 2393

Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming

Solution

Problem Understanding

The problem asks us to count all strictly increasing subarrays in a given array nums of positive integers. A strictly increasing subarray is a contiguous sequence of numbers where each element is strictly larger than the previous one. The output should be a single integer representing the total number of such subarrays.

The input nums is an array with 1 <= nums.length <= 10^5, and each element is 1 <= nums[i] <= 10^6. These constraints indicate that a brute-force approach iterating over all possible subarrays would be too slow because the number of subarrays in an array of length n is O(n^2). We need an algorithm that runs in linear time or close to it.

Important edge cases include arrays of length 1 (where the only subarray is the element itself), arrays with all equal elements (no subarrays longer than 1), and arrays that are strictly increasing or strictly decreasing.

Approaches

The brute-force approach would generate every possible subarray and check if it is strictly increasing. For each subarray, we would iterate through its elements to verify the strictly increasing property. While correct, this approach is inefficient because for an array of length n, there are O(n^2) subarrays, and checking each subarray requires up to O(n) time. This results in an O(n^3) algorithm, which is not feasible for n up to 10^5.

The key observation for an optimal solution is that strictly increasing subarrays can be counted by their lengths. If we know the length of a maximal strictly increasing subarray starting at a certain index, we can compute the total number of strictly increasing subarrays within it using the formula for the sum of the first k positive integers. Specifically, if a strictly increasing sequence has length L, it contains L * (L + 1) / 2 strictly increasing subarrays. Using a single pass through the array, we can compute this length and accumulate the count efficiently.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(1)	Generate all subarrays and check strictly increasing property
Optimal	O(n)	O(1)	Single pass, counting lengths of increasing sequences and summing subarray counts

Algorithm Walkthrough

1. Initialize a variable count to 0 to store the total number of strictly increasing subarrays.
2. Initialize a variable length to 1, representing the current length of a strictly increasing sequence.
3. Iterate through the array from the second element to the end.
4. For each element, compare it to the previous element. If it is strictly greater, increment length by 1 because the current subarray can be extended.
5. If the current element is not strictly greater than the previous, compute the number of subarrays in the current increasing sequence using the formula length * (length + 1) // 2 and add it to count. Then reset length to 1 to start counting the next increasing sequence.
6. After the loop ends, there may be a remaining increasing sequence, so add its subarray count to count.
7. Return count as the final answer.

Why it works: By maintaining the length of each contiguous strictly increasing segment and using the formula for the sum of the first k integers, we efficiently count all valid subarrays without generating them explicitly. This guarantees correctness because every strictly increasing subarray is part of some maximal increasing sequence.

Python Solution

from typing import List

class Solution:
    def countSubarrays(self, nums: List[int]) -> int:
        count = 0
        length = 1
        
        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                length += 1
            else:
                count += length * (length + 1) // 2
                length = 1
        
        count += length * (length + 1) // 2
        return count

The Python solution maintains a running length of strictly increasing sequences and uses the sum-of-integers formula to count subarrays efficiently. The final addition outside the loop handles the last sequence, which avoids off-by-one errors.

Go Solution

func countSubarrays(nums []int) int64 {
    var count int64 = 0
    length := 1
    
    for i := 1; i < len(nums); i++ {
        if nums[i] > nums[i-1] {
            length++
        } else {
            count += int64(length * (length + 1) / 2)
            length = 1
        }
    }
    
    count += int64(length * (length + 1) / 2)
    return count
}

In Go, we use int64 for count to prevent integer overflow for large input sizes. Otherwise, the logic mirrors the Python solution, iterating through the array and counting the lengths of strictly increasing sequences.

Worked Examples

Example 1: nums = [1,3,5,4,4,6]

Index	nums[i]	length	count
0	1	1	0
1	3	2	0
2	5	3	0
3	4	reset to 1	6 (from length 3: 3*4/2)
4	4	reset to 1	7 (from length 1: 1*2/2)
5	6	2	7
End of loop: add 2*3/2 = 3 → total count = 10

Example 2: nums = [1,2,3,4,5]

Index	nums[i]	length	count
0	1	1	0
1	2	2	0
2	3	3	0
3	4	4	0
4	5	5	0
End of loop: add 5*6/2 = 15 → total count = 15

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array to compute lengths of increasing sequences
Space	O(1)	Only constant variables are used, no extra data structures

The algorithm is efficient and scales linearly with input size, suitable for arrays of length up to 10^5.

Test Cases

# Provided examples
assert Solution().countSubarrays([1,3,5,4,4,6]) == 10  # mixed sequence
assert Solution().countSubarrays([1,2,3,4,5]) == 15    # strictly increasing

# Edge cases
assert Solution().countSubarrays([1]) == 1             # single element
assert Solution().countSubarrays([5,5,5,5]) == 4       # all equal
assert Solution().countSubarrays([5,4,3,2,1]) == 5     # strictly decreasing

# Mixed sequences
assert Solution().countSubarrays([1,2,1,2,3]) == 9
assert Solution().countSubarrays([1,2,3,1,2,3,4]) == 16

Test	Why
[1,3,5,4,4,6]	Checks mixed sequences and resets
[1,2,3,4,5]	Entire array strictly increasing
[1]	Single-element edge case
[5,5,5,5]	All equal elements, only length-1 subarrays valid
[5,4,3,2,1]	Strictly decreasing array, only single-element subarrays
[1,2,1,2,3]	Alternating increasing sequences
[1,2,3,1,2,3,4]	Multiple increasing sequences of varying lengths

Edge Cases

Single element array: The only subarray is the element itself. Both Python and Go solutions initialize length = 1 and handle the end-of-loop addition, returning 1 correctly.

All elements equal: No subarrays longer than length 1 are strictly increasing. The algorithm resets length whenever the current element is not greater than the previous, ensuring that only length-1 subarrays are counted.

Strictly decreasing array: Each element forms a valid subarray of length 1. The algorithm correctly resets length at each step, producing the correct count equal to the array length.

This approach reliably handles all these cases with linear complexity and constant space.